| Download
Der Fermat-Test zeigt, dass M_p für p=257 keine Primzahl ist.
Project: Elementare Zahlentheorie
Path: Mersenne-Zahl.sagews
Views: 152Wir möchten testen, ob die Mersenne-Zahl für eine Primzahl ist. Eine notwendige Bedingung ist, dass eine Primzahl ist. Das ist für der Fall:
True
Jetzt bestimmen wir , eine Zahl mit Dezimalstellen:
231584178474632390847141970017375815706539969331281128078915168015826259279871
Nun führen wir den Fermatschen Primzahltest zur Basis durch:
1
Es gilt also , d.h. die Zahl besteht den Fermat-Test zur Basis . Daraus folgt aber nicht, dass eine Primzahl ist.
Wir führen den Test nun zur Basis durch:
196794375505491229799009947282418342699685882944577157308481034524954229107763
Es gilt also , und damit ist keine Primzahl. Dieser Test dauerte nur ca. 22 Mikrosekunden!
625 loops, best of 3: 22.7 μs per loop
Die Zerlegung von in Primfaktoren zu berechnen dauert viel länger:
535006138814359 * 1155685395246619182673033 * 374550598501810936581776630096313181393
5 loops, best of 3: 23.5 s per loop