Informatiker Board | Algorithmen | Pollard Rho Methode mit Sage

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Pollard Rho Methode mit Sage » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 2 Beiträge

eulerscheZahl

Das liegt daran, dass deine Implementierung nicht passt:
Ich habe mal für n=F2=17 die ersten Werte berechnen lassen:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

x=1 y=1 d=1 i=0
x=0 y=5 d=1 i=1 
x=0 y=14 d=1 i=2
x=0 y=16 d=1 i=3
x=0 y=5 d=1 i=4 //wie i=1
x=0 y=14 d=1 i=5
x=0 y=16 d=1 i=6
x=0 y=5 d=1 i=7 //wie i=1
x=0 y=14 d=1 i=8
x=0 y=16 d=1 i=9
x=0 y=5 d=1 i=10 //wie i=1

Nach der in der Wikipedia genannten Methode kommt man bis n=6 noch flott voran(808 Durchläufe), für F7 habe ich es nach einigem Warten abgebrochen.

die dumme Blondine

Pollard Rho Methode mit Sage

Meine Frage:
Hi,
also wir hatten die Aufgabe eine SAGE- Funktion zu implementieren, in der die Pollard_Rho Methode angewendet wird. Startwert ist x=1, n=1763 und f(x)=x^2+1.
Die Schleifendurchläufe mussten auch mit angegeben werden. So weit, so gut, das haben wir bereits geschafft, alles funktioniert und unsere Übungsleiter meinten auch, dass die Funktion richtig sei.

Nun sollten wir unsere Funktion noch auf die Fermat- Zahlen anwenden, um für $[latex]n\in \left\{ 5,..,12\right\} [/latex]$ alle Primteiler $[latex]\leq 10^{14} [/latex]$ von $[latex]F_{n}[/latex]$ zu berechnen.

Unser Problem ist jetzt, dass unser Programm schon für n=5 zu lange braucht und mittendrin abbricht. Habt ihr eine Idee, wie wir unser Problem lösen können?

Meine Ideen:
Hier einmal unsere Funktion:

def pollard_rho(n,c=1,x=1):
...y = x
...d = 1
...i = 1
...while d == 1:
......x=(n**x+2)%c
......y=(y**2+c)%n
......y=(y**2+c)%n
......d=gcd(abs(x-y),n)
......i=i+1
...return x, y, d, i

und zur Wiederholung die Fermat- Zahlen:
$[latex] F_{n}:=2^{2^{n}}+1\in \mathbb N<br /> F_{5}=4294967297 [/latex]$