Informatiker Board | Suchergebnis

Informatiker Board » Suche » Suchergebnis

» Hallo Gast [Anmelden|Registrieren]

Zeige Beiträge 1 bis 4 von 4 Treffern

Autor

Beitrag

Thema: Pollard Rho Methode mit Sage

die dumme Blondine

Antworten:	1
Hits:	3.858

Pollard Rho Methode mit Sage 15.01.2013 18:27

Forum: Algorithmen

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]$

Thema: Pseuo Zufallszahlen mit Sage

die dumme Blondine

Antworten:	3
Hits:	4.604

19.12.2012 16:48

Forum: Algorithmen

mit ner kleinen Änderung (vgl. http://www.matheboard.de/thread.php?post...866#post1719866) klappts doch smile

Vielen Dank nochmal!

Thema: Pseuo Zufallszahlen mit Sage

die dumme Blondine

Antworten:	3
Hits:	4.604

19.12.2012 15:31

Forum: Algorithmen

Hi,
danke für die Hilfe, aber leider funktioniert das so nicht... traurig

er nimmt das global x=1 nicht. Er lässt die Funktion Pseudo(n) zwar so definieren, wenn man für das n dann aber eine Zahl einsetzt, so zeigt er ein Error.
Schade eigentlich, weil sage mit C und Python verwandt sein soll.

Wenn noch jemand Ideen hat, würden wir uns aber sehr darüber freuen. Leider wird uns sage nicht beigebracht, uns werden nur sehr schwere Aufgaben (im Vergleich zu den letzten Jahren) und das Online- Handbuch zur verfügung gestellt.

LG die dumme Blondine

Thema: Pseuo Zufallszahlen mit Sage

die dumme Blondine

Antworten:	3
Hits:	4.604

Pseuo Zufallszahlen mit Sage 16.12.2012 17:00

Forum: Algorithmen

Meine Frage:
Hi,
dieses Jahr ist Computeralgebra bei uns ganz schwer und meine Freundin und ich kommen bei dem einen Übungsblatt bei der 1. Aufgabe einfach nicht weiter. Aufgaben 2-4 basieren jedoch leider auf 1!

Implementieren Sie eine SAGE-Funktion, die für $[latex]n\in \mathbb N [/latex]$ sukzessive eine Folge [x1,x2...] von
Pseudo-Zufallszahlen in $[latex]\mathbb Z_{n}[/latex]$ generiert, und bei jedem Aufruf das jeweils nächste Folgenglied
zurückgibt. Verwenden Sie dazu folgenden Algorithmus:

Für Parameter $[latex]a\in \mathbb Z_{n}^{*} [/latex]$ und $[latex]b\in \mathbb Z_{n} [/latex]$ und einem Startwert $[latex]x_{0}\in \mathbb Z_{n} [/latex]$ sei $[latex]x_{i}:=ax_{i-1}+b\in \mathbb Z_{n} [/latex]$ für $[latex]i\in \mathbb N [/latex]$ gegeben. Dabei bietet es sich an, das jeweils aktuelle Folgenglied, mit dem SAGE-
Kommando global, als globale Variable zu deklarieren.

Überlegen Sie sich zudem (in Ihrem Arbeitsheft), in welchem Sinne diese Folge zufällig ist.

Meine Ideen:
sage: def pseudo(n):
....:____i=1
....:____x=1
....:____for a in range(0,1):
....:________for b in range(1,n-1):
....:____________x=x*a+b%n
....:____________i=i+1
....:____________return x

das ist unser Ansatz, jedoch gibt es jedes mal nur eine 1 heraus. Wir würden uns sehr freuen, wenn ihr uns da weiterhelfen könntet, da wir als FüBas in dem Kurs doch leicht überfordert sind.

Danke schonmal im Voraus und LG
Die dumme Blondine

Zeige Beiträge 1 bis 4 von 4 Treffern