Ich möchte wissen ob 10^95+1 prim ist - aber mein Gehirn ist schon zu verkalkt dazu

14/12/2012 - 22:51 von Mr Kyanit | Report spam
Faktorisierungsverfahren

Pollard p-1

Theoretischer Hintergrund
Das (p-1)-Verfahren der Primfaktorisierung stammt von Pollard aus dem Jahre 1974. Es ist ein probabilistisches Verfahren, das nur dann erfolgreich verlàuft, wenn für ein Primteiler p einer zusammengesetzten Zahl n, die Zahl p-1 das Produkt relativ kleiner Primfaktoren ist. Genauer gilt: Falls (p,a)=1,

p|n und (p-1)|Q => p| ggt(aQ-1, n)
Das war zu erwarten, denn nach kleinem Fermat ist ap-1 = 1 mod p, daher aQ = 1 mod p.

Implementierung des Verfahrens
Man wàhlt eine Basis a teilerfremd zu n, und den maximalen Exponenten Q hinreichend gross. Man bildet iterativ die Potenzen m=ak (mod n) mit k<=Q in der Hoffnung, dass p|m-1, aber m-1 kein Vielfaches von n ist. Dann ist 1 < ggt(n, m-1) < n ein Teiler von n. Die Potenzen lassen sich wie folgt leicht berechnen:

ak! = (...((a1)2)...)k
Quellcode zu Pollard p-1:
INPUT n;
a = RANDOM(2,..n); m = a; g = 1; i = 1; k = 10000;
WHILE (i < k AND g = 1) DO
i=i+1;
m = mi mod n;
g = ggt(m-1, n);
ENDWHILE
IF 1 < g < n THEN ECHO "Primteiler gefunden: ". g;

Vor- und Nachteile von p-1
Das Problem besteht in der Praxis zum einen darin, dass man p nicht kennt, aber Q von p abhàngt. Setzten wir zum Beispiel Q000! = 2,8 * 1035660, dann werden i.a. Primteiler p von n gefunden, für die p-1 = q1r1 * qsrs mit qiri|Q, insbesondere qi<10000. Das Verfahren kann also nicht garantieren, dass Primteiler gefunden werden, dafür ist es bei Erfolg schneller, als eine systematische Suche. Denn die theoretische Laufzeit ist O(q), wobei q der grösste Primteiler von p-1 ist, insbesondere ist die Laufzeit nicht direkt von der Größe des Primteilers p von n abhàngig.

Betrachten wir dazu ein Beispiel: N^95+1
N = 1095 + 1 = 11 * 9091 * 1812604116731 * 121450506296081 * 909090909090909091 * 4996731930447843676185843959746621491531100801

Die kleinen Primfaktoren sind schnell gefunden, die anderen Primfaktoren finden wir unter folgenden Bedingungen:

Q€9!, weil 1812604116731 = 2 * 5 * 11 * ... * 809 + 1

Q 509!, weil 121450506296081 = 24 * 5 * 13 ... * 20509 + 1

Q33667!, weil 909090909090909091 = 2 * 34 * 5 * ... * 333667 + 1

Den letzen Primfaktor erhalten wir umsonst.
 

Lesen sie die antworten

#1 Leo Baumann
15/12/2012 - 05:33 | Warnen spam
reset():

isprime(10^95+1);

FALSE



Computed with Mupad 3.1.1.

mfG Leo

Ähnliche fragen