Zahlentheoretische Algorithmen

Primzahlpotenzen erkennen

Eine sehr große Zahl n zu faktorisieren ist im Allgemeinen schwierig. Wenn jedoch n eine Primzahlpotenz ist, also n = p^m mit p Primzahl und m Element natürliche Zahlen , dann ist es sehr leicht, die Zahl n zu faktorisieren.

Durch Berechnung von ggt(n, 2ⁿ – 2) lässt sich feststellen, ob die Zahl n eine Primzahlpotenz ist. Das Ergebnis ist in fast allen Fällen sogar bereits der gesuchte Primfaktor p.

Satz: Sei p Primzahl und n = p^m mit m Element natürliche Zahlen . Dann gilt

p | 2ⁿ – 2

Beweis: Für eine Primzahl p mit p ≠ 2 gilt nach dem Satz von Fermat

2^p-1 kongruent 1 (mod p)

Multiplikation mit 2 ergibt

2^p kongruent 2 (mod p)

Für p = 2 gilt diese Kongruenz ebenfalls:

2² kongruent 2 (mod 2)

Mit n = p^m gilt

2ⁿ kongruent 2^{(p^m)} ((...(2^p)^p...)^p 2 (mod p)

Nach Definition von kongruent gilt daher

p | 2ⁿ – 2

Da außerdem gilt

p | n

folgt

p | ggt(n, 2ⁿ – 2)

Es stellt sich heraus, dass sogar

p = ggt(n, 2ⁿ – 2)

gilt, außer für n = 1093^m und n = 3511^m mit m > 1. Bei diesen Zahlen gilt

p² = ggt(n, 2ⁿ – 2)

Es handelt sich bei 1093 und 3511 um die beiden einzigen bekannten Wieferich-Primzahlen. Für eine Wieferich-Primzahl p gilt nicht nur nach dem Satz von Fermat

2^p-1 kongruent 1 (mod p)

sondern sogar

2^p-1 kongruent 1 (mod p²)

Es ist

ggt(n, 2ⁿ – 2) = ggt(n, (2ⁿ – 2) mod n) = ggt(n, 2ⁿ mod n – 2)

Die Funktion factorPrimePower berechnet den Wert ggt(n, 2ⁿ mod n – 2).

Wenn n Zweierpotenz ist, wird in der Funktion z = 0 berechnet; dies führt zu dem Aufruf ggt(n, -2). Das korrekte Ergebnis 2 wird nur dann berechnet, wenn die Funktion ggt so implementiert ist, dass sie negative Zahlen verarbeiten kann. Sicherheitshalber wird hier deshalb |z-2| gebildet.

Falls n Potenz einer Primzahl p ist, so ist der ggt gleich p, außer wenn p Wieferich-Primzahl ist, dann ist der ggt gleich p². Für die beiden bekannten Wieferich-Primzahlen 1091 und 3511 wird dieser Sonderfall im Anschluss behandelt.

# liefert die Primzahl p, wenn n eine Primzahlpotenz ist
def factorPrimePower(n):
    z=modexp(2, n, n)
    p=ggt(n, abs(z-2))   # abs wegen Zweierpotenzen (z=0)
    # Wieferich-Primzahlen behandeln
    if p==1091*1091: 
        return 1091
    if p==3511*3511:
        return 3511
    return p

Um zu testen, ob die Zahl n eine Primzahlpotenz ist, berechnen wir

p=factorPrimePower(n)

und prüfen, ob p Primzahl ist und ob n = p^m für ein m Element natürliche Zahlen gilt.

# gibt true zurueck, wenn n Primzahlpotenz ist
def isPrimePower(n):
    p=factorPrimePower(n)
    if not isPrime(p):
        return False
    # pruefen, ob n=p**m fuer irgendein m
    q=1
    while q<n:
        q*=p
    return q==n

Eine kleine Unsicherheit bleibt: Es könnte sein, dass n Potenz einer noch unbekannten Wieferich-Primzahl ist.

Weiter: