Primzahlpotenzen erkennen

 aufwärts

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

Erkennung von Primzahlpotenzen

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

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

p | 2n – 2

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

2p-1  kongruent  1  (mod p)

Multi­plikation mit 2 ergibt

2p  kongruent  2  (mod p)

Für p = 2 gilt diese Kongruenz ebenfalls:

22  kongruent  2  (mod 2)

Mit n = pm gilt

2n  kongruent  2(pm)  kongruent  ((...(2p)p...)p  kongruent  2   (mod p)

Nach Definition von  kongruent  gilt daher

p | 2n – 2

 

Da außerdem gilt

p | n

folgt

p | ggt(n, 2n – 2)

Es stellt sich heraus, dass sogar

p  =  ggt(n, 2n – 2)

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

p2  =  ggt(n, 2n – 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

2p-1  kongruent  1  (mod p)

sondern sogar

2p-1  kongruent  1  (mod p2)

 

Programm

Es ist

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

Die Funktion factorPrimePower berechnet den Wert ggt(n, 2n 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. Sicherheits­halber 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 p2. 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 Primzahl­potenz ist, berechnen wir

p=factorPrimePower(n)

und prüfen, ob p Primzahl ist und ob n = pm 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:   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.07.2006   Updated: 26.02.2017
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik