AZreferate - Referate und hausaufgaben fur schule.
Referatesuche, Hausarbeiten und Seminararbeiten Kostenlose Online-Dokumente mit Bildern, Formeln und Grafiken. Referate, Facharbeiten, Hausarbeiten und Seminararbeiten findest für Ihre einfache Hausarbeiten.



BetriebstechnikBiographienBiologieChemieDeutschDigitaltechnik
ElectronicaEpochenFertigungstechnikGemeinschaftskundeGeographieGeschichte
InformatikKulturKunstLiteraturManagementMathematik
MedizinNachrichtentechnikPhilosophiePhysikPolitikProjekt
PsychologieRechtSonstigeSportTechnikWirtschaftskunde

Referat Faktorenzerlegung großer Zahlen



mathematik referate

mathematik referate

Faktorenzerlegung großer

Zahlen

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,r welche gilt : f(x)=x²+c (c= 0 ; 2 ) x   x²+c ; y (y²+c)²+c » »» P P y - x )

Als Startwertr x , y , und P wird verwendet.

Schritt:

Schritt:

Schritt:

Setze x=1 y=1 ;P 1

 
Setze x = x c ; y = y²+c) c und P P y - x )

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 entstehenr 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 3 )

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

Hier ein Programmierbeispiel in Q-Basic :

CLS:CLEAR: X= : 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 : Y=(Y +C) +C: GOSUB 0: P=P*(Y-X):GOSUB 1 : V=V+ : IF V>= 5 THEN V=25




LOCATE 0 0:PRINT X LOCATE 6,V:PRINT P; IF P=0 THEN GOTO 9

Y

P":LOCATE 10,V:PRINT X;:LOCATE 23,V:PRINT Y;:




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

13. TE = P

14. RE = N - ( INT ( N / TE ) ) * TE: IF RE=1 THEN T= : GOTO 3

IF RE=0 THEN T=TE: GOTO 17

16. N=TE:TE=RE:GOTO 14

' *****die Lösung

CLS:LOCATE 1 1:PRINT "Zahl ";MO;" u. ";P;" sind durch ";T;" Teilbar ;:BEEP:INPUT"" ;I:GOTO1

' *****eine Primzahl

CLS:LOCATE 1 1:PRINT "Zahl ";MO;"ist eine Primzahl! -oder ein anderes !!c!! prob ";:BEEP:INPUT"" ;I

21. GOTO1 ' * ENDE dieses ©Programs

Hier ein RechenBeispiel:

N 3

=> X

Y

P

c








5





 
N= 43 c=2

1 5 => Primzahl oder c andershlen z.B.: c=2

=> X       Y P

11 8

16 25

15 42

 
ggT(65,143)=13 =>13 143


Antwort : 143 ist durch 3 teilbar.

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äher eingegangen.

Der SQUFOF-Algorithmus von D. Shanks:

Hierfür betigt man die Theorie der Ideale in quadratischen

Zahlkörpern.Näheres : siehe Artikel von Williams.



Referate über:



Datenschutz




Copyright © 2024 - Alle Rechte vorbehalten
AZreferate.com
Verwenden sie diese referate ihre eigene arbeit zu schaffen. Kopieren oder herunterladen nicht einfach diese
# Hauptseite # Kontact / Impressum