Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Miller Rabin test

De test geeft aan dat N=29 is niet samengesteld voor de getuige a=3. Maar voor a=5 is N=29 wel samengesteld.
N-1=28=22 · 7(=m). Wat is waar?

Voor N=643 is er geen getuige a die zegt dat N waarschijnlijk priem is.
N-1=642=22·321
Voor a=3 en a=5 is N samengesteld.
Vraag: voor welke a is N waarschijnlijk priem?

herman
Leerling bovenbouw havo-vwo - maandag 14 januari 2013

Antwoord

28=22·7
57 mod 29=28=29-1.
Aangezien (29-1)2=1 mod 29 geeft de sterke pseudo-priem test niet aan dat 29 samengesteld is.

Geen getuige zal ooit zeggen dat N waarschijnlijk priem is.
Getuigen zeggen alleen maar dat zekere N samengesteld is.
De Miller Rabin test berust erop dat als een voldoend aantal getuigen niet aangeven dat N samengesteld is N waarschijnlijk priem is.

Aangezien 643 priem is zal geen enkele pseudopriem test aangeven dat 643 samengesteld is.
Neem bijvoorbeeld jouw cases:
642=2·321 (en niet 4·321)
a=3:
3321 mod 3=642=643-1.
(643-1)2=1, dus deze getuige geeft niet aan dat 643 samengeteld is

idem: 5321 mod 643=642.
Dus ook 5 geeft niet aan dat 643 samengesteld is.

hk
maandag 14 januari 2013

 Re: Miller Rabin test 

©2001-2024 WisFaq