De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
maandag 14 januari 2013
 Re: Miller Rabin test 



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3