|
|
|
|
|
Zum Referate-Archiv Referat hochladen Newsletter bestellen Klatsch & Tratsch |
|
|
Faktorenzerlegung großer Zahlen
|
|
||
| Zusammenfassung | ||
| Fachbereich: | Mathematik | |
| Woerter | 600 | |
| Kurzbeschreibung | 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... | |
|
|
||
Faktorenzerlegung großer ZahlenFaktorenzerlegunggroßer Zahlen3.) Faktorenzerlegung à laMonte Carlo : Bei der Methode von J. M. Pollard ist es nicht immer möglich bei einerteilbaren Zahl einen Faktor zu finden. Die Suche wird zu einem Glücksspiel.Man untersucht ob es von einer natürlichen Zahl N und einererrechneten 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 wird1 verwendet. 1.Schritt: Setze x=1 ;y=1 ;P=1 2.Schritt: Setze x = x²+c ; y =(y²+c)²+c undP²=P1·( y - x) 3.Schritt: Berechne den ggT von P und N. Fals dasErgebnis = 1 ist , Wiederhole den Vorgang ab dem Schritt 2. Bei allen anderenErgebnissen hat man mit dem ggT den gesuchten Teiler gefunden . !Achtung!: Bei Schritt 2 entstehen für dieVariablen x, y und P große Werte. Man muß daherdie ErgebnissemoduloN nehmen . Fals N selbst der Teiler ist, gibt es zweiMöglichkeiten:N ist eine PrimzahlMan kann die Konstante c verändern (z.B.:von 1 auf2,3,...) Wenn einem die Berechnung des Schrittes3zu Zeitaufwendig ist, kann man dies umgehen, indem man erst nach z.B.: 10 -maliger Wiederholung des 2. Schrittes mit dem3.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 “KonstanteC: ”; C: CLSX=X²+C: GOSUB 9: Y=(Y²+C)²+C: GOSUB 10:P=P*(Y-X):GOSUB 11: V=V+1: IF V>=25 THEN V=25LOCATE 10,0:PRINT “X Y P”:LOCATE10,V:PRINT X;:LOCATE 23,V:PRINT Y;: LOCATE 36,V:PRINT P;IF P=0 THEN GOTO 19IF P=1 THEN GOTO 3INPUT“”;I:GOTO 12GOTO 3X=X-(INT(X/MO))*MO:RETURNY=Y-(INT(Y/MO))*MO:RETURNIF ABS ( P ) < > P THEN P= N - ABS ( P ) : P=P - ( INT ( P / MO ) ) *MO : RETURN‘ *****ggT --ausrechnenTE = P RE = N - ( INT ( N / TE ) ) * TE: IF RE=1 THEN T=1: GOTO 3IF RE=0 THEN T=TE: GOTO 17N=TE:TE=RE:GOTO 14‘ *****die LösungCLS:LOCATE 1,1:PRINT “Zahl ”;MO;“ u. ”;P;“sind durch ”;T;“ Teilbar.”;:BEEP:INPUT”“;I:GOTO1‘ *****eine PrimzahlCLS:LOCATE 1,1:PRINT “Zahl ”;MO;“ist eine Primzahl! -oderein anderes !!c!! prob.”;:BEEP:INPUT”“ ;IGOTO1 ‘ ***** ENDE dieses ©ProgramsHier ein RechenBeispiel: N=143=> X Y P c=1 1 1 1 25 3 5105 14 Faktorenzerlegunggroßer Zahlen3.) Faktorenzerlegung à laMonte Carlo : Bei der Methode von J. M. Pollard ist es nicht immer möglich bei einerteilbaren Zahl einen Faktor zu finden. Die Suche wird zu einem Glücksspiel.Man untersucht ob es von einer natürlichen Zahl N und einererrechneten 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 wird1 verwendet. 1.Schritt: Setze x=1 ;y=1 ;P=1 2.Schritt: Setze x = x²+c ; y =(y²+c)²+c undP²=P1·( y - x) 3.Schritt: Berechne den ggT von P und N. Fals dasErgebnis = 1 ist , Wiederhole den Vorgang ab dem Schritt 2. Bei allen anderenErgebnissen hat man mit dem ggT den gesuchten Teiler gefunden . !Achtung!: Bei Schritt 2 entstehen für dieVariablen x, y und P große Werte. Man muß daherdie ErgebnissemoduloN nehmen . Fals N selbst der Teiler ist, gibt es zweiMöglichkeiten:N ist eine PrimzahlMan kann die Konstante c verändern (z.B.:von 1 auf2,3,...) Wenn einem die Berechnung des Schrittes3zu Zeitaufwendig ist, kann man dies umgehen, indem man erst nach z.B.: 10 -maliger Wiederholung des 2. Schrittes mit dem3.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 “KonstanteC: ”; C: CLSX=X²+C: GOSUB 9: Y=(Y²+C)²+C: GOSUB 10:P=P*(Y-X):GOSUB 11: V=V+1: IF V>=25 THEN V=25LOCATE 10,0:PRINT “X Y P”:LOCATE10,V:PRINT X;:LOCATE 23,V:PRINT Y;: LOCATE 36,V:PRINT P;IF P=0 THEN GOTO 19IF P=1 THEN GOTO 3INPUT“”;I:GOTO 12GOTO 3X=X-(INT(X/MO))*MO:RETURNY=Y-(INT(Y/MO))*MO:RETURNIF ABS ( P ) < > P THEN P= N - ABS ( P ) : P=P - ( INT ( P / MO ) ) *MO : RETURN‘ *****ggT --ausrechnenTE = P RE = N - ( INT ( N / TE ) ) * TE: IF RE=1 THEN T=1: GOTO 3IF RE=0 THEN T=TE: GOTO 17N=TE:TE=RE:GOTO 14‘ *****die LösungCLS:LOCATE 1,1:PRINT “Zahl ”;MO;“ u. ”;P;“sind durch ”;T;“ Teilbar.”;:BEEP:INPUT”“;I:GOTO1‘ *****eine PrimzahlCLS:LOCATE 1,1:PRINT “Zahl ”;MO;“ist eine Primzahl! -oderein anderes !!c!! prob.”;:BEEP:INPUT”“ ;IGOTO1 ‘ ***** ENDE dieses ©ProgramsHier ein RechenBeispiel: N=143=> X Y P c=1 1 1 1 25 3 5105 14 2683 83 105 105 0=> Primzahl oder c anderswählen z.B.: c=2 N=143 c=2 => X Y P 3 11 8 11116 125 123115142 11638 65 ggT(65,143)=13=>13/143 Antwort : 143 ist durch 13 teilbar. 4.) Weitere Algorithmen: Ein weiterer Algorithmus von J. M.Pollard: Es wird ein Teiler p von einer Zahl N gesucht. Er ist gefunden,wenn gilt: p-1 ist nur durch kleine Primfaktoren teilbar. Auf diesen Rechengang wird in dem Artikel von Williams nähereingegangen. Der SQUFOF-Algorithmus von D.Shanks:Hierfür benötigt man die Theorie der Ideale in quadratischen Zahlkörpern.Näheres : siehe Artikel von Williams. |
||
|
Bitte beachten Sie, dass ausschliesslich der Autor fuer die Richtigkeit dieser Angaben verantwortlich ist. |
||
© 1997-2010 ontaps GmbH · Alle Rechte vorbehalten. Ausgewiesene Marken gehören ihren jeweiligen Eigentümern. Durch Benutzung unserer Webseite erkennen Sie unsere AGB an. Wir übernehmen keine Haftung für den Inhalt verlinkter externer Internetseiten.
Allgemeine Geschäftsbedingungen | Impressum