WisFaq!

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=2² · 7(=m). Wat is waar?

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

herman
14-1-2013

Antwoord

28=2²·7
5⁷ mod 29=28=29-1.
Aangezien (29-1)²=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:
3³²¹ mod 3=642=643-1.
(643-1)²=1, dus deze getuige geeft niet aan dat 643 samengeteld is

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

hk
14-1-2013