Mathematik - Faktorenzerlegung großer Zahlen

Alle Kategorien » Mathematik Referate » Faktorenzerlegung großer Zahlen

Faktorenzerlegung großer Zahlen

Kurzzusammenfassung

Faktorenzerlegung großer Zahlen 3.) Faktorenzerlegung à la Monte Carlo : Bei der Methode von J. M. Pollard ist es nicht immer möglich bei einer teilbaren Zahl einen Faktor zu finden. Die Suche wird zu einem Glüc

Fachbereich: Mathematik
Sprache: Deutsch
Wörter: 600
Note: n.v.

Faktorenzerlegung großer Zahlen

Faktorenzerlegung
großer Zahlen
3.) Faktorenzerlegung à la
Monte Carlo :

Bei der Methode von J. M. Pollard ist es nicht immer möglich bei einer
teilbaren Zahl einen Faktor zu finden. Die Suche wird zu einem Glücksspiel.
Man untersucht ob es von einer natürlichen Zahl N und einer
errechneten Zahl P einen größten gemeinsamen Teiler gibt.
P bekommt man, indem zwei neue Variablen (x , y )
einführt, für welche gilt : f(x)=x²+c (c=0;2 )
x x²+c ; y (y²+c)²+c
»»»»
P²=P1·( y - x
)
Als Startwert für x , y , und P wird
1 verwendet.
1.Schritt:
Setze x=1 ;y=1 ;P=1
2.Schritt:
Setze x = x²+c ; y =
(y²+c)²+c und
P²=P1·( y - x
)
3.Schritt:
Berechne den ggT von P und N. Fals das
Ergebnis = 1 ist , Wiederhole den Vorgang ab dem Schritt 2
.
Bei allen anderen
Ergebnissen hat man mit dem ggT den gesuchten Teiler gefunden .

!Achtung!:

Bei Schritt 2 entstehen für die
Variablen x, y und P große Werte. Man muß daher
die Ergebnisse modulo
N nehmen .

Fals N selbst der Teiler ist, gibt es zwei
Möglichkeiten:
N ist eine Primzahl
Man kann die Konstante c verändern (z.B.:von 1 auf
2,3,...)

Wenn einem die Berechnung des Schrittes 3
zu Zeitaufwendig ist, kann man dies umgehen, indem
man erst nach z.B.: 10 -maliger Wiederholung des 2. Schrittes mit dem
3.Schritt beginnt .(Nur sehr
seltener Verlust des Teilers ) .


Hier ein Programmierbeispiel in Q-Basic
:


CLS:CLEAR: X=1: Y=1: P=1: T=1 ‘ **** Programm zur
Faktorenzerlegung von MEISEL Marcus ****
INPUT “zu teilende Zahl (N): ”;N : MO=N: INPUT “Konstante
C: ”; C: CLS
X=X²+C: GOSUB 9: Y=(Y²+C)²+C: GOSUB 10:
P=P*(Y-X):GOSUB 11: V=V+1: IF V>=25 THEN V=25
LOCATE 10,0:PRINT “X Y P”:LOCATE
10,V:PRINT X;:LOCATE 23,V:PRINT Y;: LOCATE 36,V:PRINT P;
IF P=0 THEN GOTO 19
IF P=1 THEN GOTO 3
INPUT “”;I:GOTO 12
GOTO 3
X=X-(INT(X/MO))*MO:RETURN
Y=Y-(INT(Y/MO))*MO:RETURN
IF ABS ( P ) < > P THEN P= N - ABS ( P ) : P=P - ( INT ( P / MO ) ) *
MO : RETURN
‘ *****ggT --ausrechnen
TE = P
RE = N - ( INT ( N / TE [...]

Du musst angemeldet sein, um das komplette Referate anschauen zu können.

Jetzt bei referate.de anmelden

Oder nutze Facebook Share, um das Referat herunterladen zu können.

share

Nach dem Du die Facebook Share Funktion ausgeführt hast aktualisiert sich die Seite automatisch und Du bekommst das komplette Referat zum Download bereit gestellt.