Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download

Der Fermat-Test zeigt, dass M_p für p=257 keine Primzahl ist.

Views: 152

Wir möchten testen, ob die Mersenne-Zahl Mp=2p1M_p = 2^p-1 für p=257p=257 eine Primzahl ist. Eine notwendige Bedingung ist, dass pp eine Primzahl ist. Das ist für p=257p=257 der Fall:

p = 257 p.is_prime()
True

Jetzt bestimmen wir MpM_p, eine Zahl mit 7777 Dezimalstellen:

Mp = 2^p-1 Mp
231584178474632390847141970017375815706539969331281128078915168015826259279871

Nun führen wir den Fermatschen Primzahltest zur Basis a=2a=2 durch:

a = 2 ab = mod(a, Mp) # ab ist die Restklasse von a modulo M_p ab^(Mp-1)
1

Es gilt also 2Mp11(modMp)2^{M_p-1} \equiv 1 \pmod{M_p}, d.h. die Zahl MpM_p besteht den Fermat-Test zur Basis 22. Daraus folgt aber nicht, dass MpM_p eine Primzahl ist.

Wir führen den Test nun zur Basis a=3a=3 durch:

a = 3 ab = mod(a, Mp) ab^(Mp-1)
196794375505491229799009947282418342699685882944577157308481034524954229107763

Es gilt also 3Mp1≢1(modMp)3^{M_p-1}\not\equiv 1\pmod{M_p}, und damit ist MpM_p keine Primzahl. Dieser Test dauerte nur ca. 22 Mikrosekunden!

timeit("ab^(Mp-1)")
625 loops, best of 3: 22.7 μs per loop

Die Zerlegung von MpM_p in Primfaktoren zu berechnen dauert viel länger:

factor(Mp)
535006138814359 * 1155685395246619182673033 * 374550598501810936581776630096313181393
timeit("factor(Mp)")
5 loops, best of 3: 23.5 s per loop