Schnelle Exponentiation < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:50 So 26.10.2014 | | Autor: | Marcel |
| Aufgabe | Hallo,
ich habe mal in Matlab "die schnelle Exponentiation mod N" programmiert.
Die Datei hänge ich einerseits an, zum anderen stelle ich den Code hier
rein. |
Der Grund ist einfach:
Es wäre nett, wenn jemand drüberguckt, ob
1. Der Code so im Wesentlichen funktionsfähig ist.
2. Er hinreichend (Laufzeit)-optimiert ist.
Jeder Verbesserungsvorschlag ist für mich interessant. Daher schonmal Danke
im Voraus.
Hier der Codeteil, den man auch im Anhang findet:
| 1: |
| | 2: | % Anwendung der schnellen Exponentian mod N
| | 3: |
| | 4: | function [result]=Schnelle_Exponentiation_mod_N__V1_0(a,k,N);
| | 5: | % es soll a^k mod N schnell berechnet werden
| | 6: |
| | 7: | % Darstellung des Exponenten k als Binärzahl
| | 8: | bin_k=dec2bin(k);
| | 9: |
| | 10: | % es ist günstiger, diese Darstellung in der Form a_0'*2^0+...+a_m'*2^m
| | 11: | % anstatt a_m*2^0+...+a_0*2^m zu haben
| | 12: |
| | 13: | bin_k_flipped=fliplr(bin_k);
| | 14: | % Die Anzahl der 1en in der binären Darstellung ist FaktorenAnzahl
| | 15: | FaktorenAnzahl=length(find(bin_k_flipped==num2str(1)));
| | 16: |
| | 17: | Faktoren=NaN*ones(1,length(bin_k_flipped));
| | 18: | Faktoren(1)=mod(a,N);
| | 19: | for k=2:length(Faktoren)
| | 20: | Faktoren(k)=mod(Faktoren(k-1)*Faktoren(k-1),N);
| | 21: | end
| | 22: |
| | 23: | Faktoren=Faktoren(find(bin_k_flipped==num2str(1)));
| | 24: | result=1;
| | 25: | while ( ~isempty(Faktoren) )
| | 26: | result=mod(result*Faktoren(1),N);
| | 27: | Faktoren=Faktoren(2:length(Faktoren));
| | 28: | end;
|
P.S. Natürlich kann man das Ganze auch ins "Matlab-Forum" verschieben.
Aber ich denke, auch, wenn es *praktisch* ist, passt die Frage durchaus
auch ins Zahlentheorie-Forum.
![[a]](/images/paperclip.gif "Dateianhänge") Schnelle_Exponentiation_mod_N__V1_0.m
Gruß,
Marcel
Dateianhänge:
Anhang Nr. 1 (Typ: m) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:27 So 26.10.2014 | | Autor: | Marcel |
Hallo nochmal,
nur so als Info:
Auf nicht oder *schlecht* kommentierte Code-Teile dürft ihr natürlich ebenso
eingehen. Ich gehe zwar davon aus, dass die Matlab/Octave-Benutzer hier
sich damit weitesgehend auskennen, aber ich erwarte nicht, dass jeder
sich damit auskennt.
Wenn der Code "zu unüberschaubar" ist, dann dürft ihr auch einfach bei
entsprechenden Stellen, die Euch unklar sind, nachfragen.
Zum Bsp. gibt
find(bin_k_flipped==num2str(1))
die Stellen "in dem (gespiegelten) String-Vektor" an, an denen eine binäre 1 steht.
Bei der Konvertierung einer Zahl mit dec2bin macht Matlab/Octave aus
einer Zahl in Dezimaldarstellung ihre zugehörige Binärdarstellung. Dass ich
mit "num2str(1)" vergleiche, hat damit zu tun, dass diese 0en und 1en,
die man nach der Konvertierung sieht, keine *Numbers* mehr sind (das ist
alles auch nur ein wenig *grob* von mir gesagt - wenn Wert drauf gelegt
wird, suche ich auch passende Fachwörter raus.  )
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:32 Mo 27.10.2014 | | Autor: | Teufel |
Hi!
Wozu berechnest du denn FaktorenAnzahl? Du benötigst diese Zahl nirgendwo! Ansonsten sieht es ok, sollte funktionieren, obwohl ich ihn jetzt nicht getestet habe. Aber so von der Logik her zumindest.
Optimal ist das ganze nicht programmiert, aber es sollte den Job noch effizient genug tun.
Zum Beispiel kann man sich das Spiegeln der Binärdarstellung sparen, wenn man das Faktoren-Array, dann von hinten anstatt von vorne auffüllt z.B.
Weiter zum Faktoren-Array. Das Ding ist nicht wirklich Speicherplatzeffizient, aber die Laufzeit macht das nicht weiter kaputt, weil diese Werte eh berechnet werden müssen.
Normalerweise programmiert man das eher so:
EINGABE: a, k, n
$result=1$
while k>0:
if [mm] $k\%2==1$:
[/mm]
$result = result * a$
end if
[mm] $a=a^2$
[/mm]
[mm] $k=k//2=\lfloor [/mm] k/2 [mm] \rfloor$
[/mm]
end while
Ist vielleicht zuerst etwas schwieriger nachvollziehbar, aber ziemlich effizient.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:52 Mo 27.10.2014 | | Autor: | Marcel |
Hi Teufel,
> Hi!
>
> Wozu berechnest du denn FaktorenAnzahl? Du benötigst diese
> Zahl nirgendwo!
ah, Danke. Das war in einer Vorversion wichtig, hier hatte ich das nur
als "Kontrolle" benutzt.
> Ansonsten sieht es ok, sollte
> funktionieren, obwohl ich ihn jetzt nicht getestet habe.
Einfache Tests lieferten das passende Ergebnis.
> Aber so von der Logik her zumindest.
> Optimal ist das ganze nicht programmiert, aber es sollte
> den Job noch effizient genug tun.
Okay, danke.
> Zum Beispiel kann man sich das Spiegeln der
> Binärdarstellung sparen, wenn man das Faktoren-Array, dann
> von hinten anstatt von vorne auffüllt z.B.
Ja, ich bin oft faul und benutze einfach gerne auch vorgefertigte Befehle.
> Weiter zum Faktoren-Array. Das Ding ist nicht wirklich
> Speicherplatzeffizient, aber die Laufzeit macht das nicht
> weiter kaputt, weil diese Werte eh berechnet werden
> müssen.
Stimmt, das Anlegen dieses Feldes ist eigentlich überflüssig.
> Normalerweise programmiert man das eher so:
>
> EINGABE: a, k, n
> [mm]result=1[/mm]
> while k>0:
> if [mm]k\%2==1[/mm]:
> [mm]result = result * a[/mm]
> end if
> [mm]a=a^2[/mm]
> [mm]k=k//2=\lfloor k/2 \rfloor[/mm]
> end while
>
> Ist vielleicht zuerst etwas schwieriger nachvollziehbar,
> aber ziemlich effizient.
Okay - das passt wohl eher auch zu der Beschreibung auf Wikipedia,
wo "square and multiply" beschrieben wird. Ich schreibe mir diese effizientere
Methode heute abend als Programm (ist ja wirklich nur eine Minimal-Modifikation,
um das Octave-kompatibel zu machen).
Danke Dir!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:08 Mo 27.10.2014 | | Autor: | Teufel |
Ja, den Pseudocode von Wikipedia kann man meist ganz gut in eine richtige Programmiersprache pressen. :)
Wobei natürlich [mm] $a=a^2$ [/mm] eben [mm] $a=a^2\%n$ [/mm] bedeuten soll. Du kannst ja dann mal testen, um wie viel schneller die "herkömmliche" Methode gegenüber deiner Alten ist. Finde so etwas auch immer spannend. Ich sitze z.B. gerade an einer Kryptochallenge, in der ich billionen mal irgendeine Schleife durchlaufen muss und etwas prüfen muss. Da macht es schon einen Unterschied, ob das ganze 10 Jahre dauert oder 1000mal schneller in 3,5 Tagen durchläuft, weil ich wenigstens ein bisschen optimiert habe.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:30 Mo 27.10.2014 | | Autor: | Marcel |
Hallo,
> Ja, den Pseudocode von Wikipedia kann man meist ganz gut in
> eine richtige Programmiersprache pressen. :)
>
> Wobei natürlich [mm]a=a^2[/mm] eben [mm]a=a^2\%n[/mm]
ja, soweit ich das verstanden hatte, muss ich auch [mm] $a*result\,$ [/mm] mod N berechnen.
Hier mal mein Code: | 1: | function [result]=Schnelle_Exponent_opt_mod_N__V1_0(a,k,N);
| | 2: | % es soll a^k mod N schnell berechnet werden
| | 3: |
| | 4: | result = 1;
| | 5: | while ( k > 0)
| | 6: | if ( mod(k,2)==1 )
| | 7: | result=mod(result*a,N);
| | 8: | end;
| | 9: | a=mod(a*a,N);
| | 10: | k=floor(k/2);
| | 11: | end |
> bedeuten soll. Du
> kannst ja dann mal testen, um wie viel schneller die
> "herkömmliche" Methode gegenüber deiner Alten ist. Finde
> so etwas auch immer spannend.
Die Frage ist, womit ich das testen kann. Mit großen Zahlen sind die beide
superschnell...
> Ich sitze z.B. gerade an einer Kryptochallenge, in der ich billionen mal
> irgendeine Schleife durchlaufen muss und etwas prüfen muss. Da macht
> es schon einen Unterschied, ob das ganze 10 Jahre dauert
> oder 1000mal schneller in 3,5 Tagen durchläuft, weil ich
> wenigstens ein bisschen optimiert habe.
Och Mensch, Du bist aber ungeduldig.
P.S. Das ganze ist nur deshalb eine Frage, weil mal jemand kurz reingucken
sollte, ob da nicht doch en Fehler im Code ist...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:46 Mo 27.10.2014 | | Autor: | Fulla |
> Hallo,
>
> > Ja, den Pseudocode von Wikipedia kann man meist ganz gut in
> > eine richtige Programmiersprache pressen. :)
> >
> > Wobei natürlich [mm]a=a^2[/mm] eben [mm]a=a^2\%n[/mm]
>
> ja, soweit ich das verstanden hatte, muss ich auch
> [mm]a*result\,[/mm] mod N berechnen.
>
Hallo Marcel,
das rote result kannst du dir sparen. Die Variable hat an dieser Stelle immer den Wert 1.
[Hier stand Blödsinn]
(Mit Matlab kenne ich mich zwar nicht aus, aber dieser Code ist ja nicht besonders spezifisch....)
> Hier mal mein Code: | 1: | function
| | 2: | > [mm][result]=Schnelle_Exponent_opt_mod_N__V1_0(a,k,N);[/mm]
| | 3: | > % es soll [mm]a^k[/mm] mod N schnell berechnet werden
| | 4: | >
| | 5: | > result = 1;
| | 6: | > while ( k > 0)
| | 7: | > if ( mod(k,2)==1 )
| | 8: | > result=mod([red]result[/red]*a,N);
| | 9: | > end;
| | 10: | > a=mod(a*a,N);
| | 11: | > k=floor(k/2);
| | 12: | > end |
Lieben Gruß,
Fulla
EDIT: in der Code-Umgebung geht kein rot. Ich meine das "result" zwischen den red-Tags. Die Floor-Funktion brauchst jetzt auch nicht mehr, da k in dieser Codezeile stets gerade ist (siehe meine PM).
[Hier auch.]
> > bedeuten soll. Du
> > kannst ja dann mal testen, um wie viel schneller die
> > "herkömmliche" Methode gegenüber deiner Alten ist. Finde
> > so etwas auch immer spannend.
>
> Die Frage ist, womit ich das testen kann. Mit großen
> Zahlen sind die beide
> superschnell...
>
> > Ich sitze z.B. gerade an einer Kryptochallenge, in der ich
> billionen mal
> > irgendeine Schleife durchlaufen muss und etwas prüfen
> muss. Da macht
> > es schon einen Unterschied, ob das ganze 10 Jahre dauert
> > oder 1000mal schneller in 3,5 Tagen durchläuft, weil ich
> > wenigstens ein bisschen optimiert habe.
>
> Och Mensch, Du bist aber ungeduldig.
>
> P.S. Das ganze ist nur deshalb eine Frage, weil mal jemand
> kurz reingucken
> sollte, ob da nicht doch en Fehler im Code ist...
>
> Gruß,
> Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:54 Mo 27.10.2014 | | Autor: | Marcel |
Hallo Fulla,
> > Hallo,
> >
> > > Ja, den Pseudocode von Wikipedia kann man meist ganz
> gut in
> > > eine richtige Programmiersprache pressen. :)
> > >
> > > Wobei natürlich [mm]a=a^2[/mm] eben [mm]a=a^2\%n[/mm]
> >
> > ja, soweit ich das verstanden hatte, muss ich auch
> > [mm]a*result\,[/mm] mod N berechnen.
> >
>
> Hallo Marcel,
>
> das rote result kannst du dir sparen. Die Variable hat an
> dieser Stelle immer den Wert 1. (Mit Matlab kenne ich mich
> zwar nicht aus, aber dieser Code ist ja nicht besonders
> spezifisch....)
nö, das wird doch in der while-Schleife sukzessive verändert.
> > Hier mal mein Code: | 1: | function
| | 2: | > > [mm][result]=Schnelle_Exponent_opt_mod_N__V1_0(a,k,N);[/mm]
| | 3: | > > % es soll [mm]a^k[/mm] mod N schnell berechnet werden
| | 4: | > >
| | 5: | > > result = 1;
| | 6: | > > while ( k > 0)
| | 7: | > > if ( mod(k,2)==1 )
| | 8: | > > result=mod([b][red]result[/red][/b]*a,N);
| | 9: | > > end;
| | 10: | > > a=mod(a*a,N);
| | 11: | > > k=floor(k/2);
| | 12: | > > end |
Ich rechne mal ein Beispiel:
result hat zuerst den Wert 1. Wenn jetzt etwa [mm] $k=3\,$ [/mm] ist, dann sagt
result=mod(result*a,N),
dass result nun den folgenden Wert bekommt: result wird auf den Rest
gesetzt, den die Division der Zahl a durch N läßt.
Etc. pp.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:23 Mo 27.10.2014 | | Autor: | Marcel |
Hi,
okay, ich lasse die Frage mal auf halb beantwortet, dann kann mir vielleicht
Teufel (oder sonst jemand) noch einen Tipp für einen Laufzeit-Test der
beiden Methoden sagen?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:17 Mo 27.10.2014 | | Autor: | Thomas_Aut |
Hallo Marcel,
Welche Zeit misst Matlab denn jeweils pro Durchlauf ?
Dein Code scheint mir etwas unpraktisch was den Speicherplatz betrifft ... aber für die Laufzeit wird das keine Rolle spielen(bzw. wenn dann absolut vernachlässigbar) .
Gruß Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:23 Mo 27.10.2014 | | Autor: | Marcel |
Hi Thomas,
> Hallo Marcel,
>
> Welche Zeit misst Matlab denn jeweils pro Durchlauf ?
>
> Dein Code scheint mir etwas unpraktisch was den
> Speicherplatz betrifft ... aber für die Laufzeit wird das
> keine Rolle spielen(bzw. wenn dann absolut vernachlässigbar) .
mit "tic toc" bei einem einmaligen Aufruf irgendwas in der 4en Nachkommastelle
im Sekundenbereich. Ist mit Octave schwer genauer zu testen. Ich gehe
gleich mal an einen anderen Rechner, da ist aber "Matlab-Steinzeit" (also
genauer: 6.0 ) drauf.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:31 Mo 27.10.2014 | | Autor: | Thomas_Aut |
Hallo Marcel,
[mm] 10^{-4} [/mm] Sekunden ist doch sehr rasch -liegt die Zeit bei beiden Versionen in dem Bereich?
Ich habe noch nie mit Octave gearbeitet , aber das hat doch sicher auch eine tic,toc Funktion oder nicht?
Gruß Thomas
Ps: Die Variante von Teufel ist natürlich auf das Minimum reduziert - weniger Aufwand gibts nicht- dennoch gehe ich davon aus, dass du kaum Unterschiede merken wirst.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:35 Mo 27.10.2014 | | Autor: | Marcel |
Hi,
> Hallo Marcel,
>
> [mm]10^{-4}[/mm] Sekunden ist doch sehr rasch -liegt die Zeit bei
> beiden Versionen in dem Bereich?
ja, und das ist schwer, genauer zu werden, da das varriiert. Ich könnte
statistisch auswerten oder eine Schleife drum bauen.
> Ich habe noch nie mit Octave gearbeitet , aber das hat doch
> sicher auch eine tic,toc Funktion oder nicht?
Ja, ich hab's ja nur in Octave (allerdings unter cygwin) getestet.
>
> Gruß Thomas
>
> Ps: Die Variante von Teufel ist natürlich auf das Minimum
> reduziert - weniger Aufwand gibts nicht- dennoch gehe ich
> davon aus, dass du kaum Unterschiede merken wirst.
Momentan sehe ich laufzeitmäßig quasi keine, aber speichermäßig hat er
schon recht (gerade, wenn man große Zahlen und große Exponenten hat),
das geht besser. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:53 Mo 27.10.2014 | | Autor: | Marcel |
Hallo,
mit Schleifen sagt mir Matlab:
Das Verhältnis des optimalen zu meinem Algorithmus ist etwa
[mm] $2/3\,.$
[/mm]
Anders gesagt: Meiner ist etwa 50% langsamer...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:13 Mo 27.10.2014 | | Autor: | Thomas_Aut |
> Hallo,
>
> mit Schleifen sagt mir Matlab:
> Das Verhältnis des optimalen zu meinem Algorithmus ist
> etwa
>
> [mm]2/3\,.[/mm]
>
> Anders gesagt: Meiner ist etwa 50% langsamer...
>
> Gruß,
> Marcel
Das ist doch einiges...
Gruß Thomas
|
|
|
| |
|
Noch zwei Anmerkungen von mir:
- Statt Faktoren=NaN*ones(1,length(bin_k_flipped)); kannst auch direkt Faktoren=NaN(1,length(bin_k_flipped)); schreiben.
- Ebenso kannst du Faktoren=Faktoren(find(bin_k_flipped==num2str(1))); durch Faktoren=Faktoren(bin_k_flipped==num2str(1)); ersetzen
Ersteres bringt keine Laufzeitgewinne, zweiteres ist aber schneller. Ob das auch in Octave funktioniert, kann ich allerdings nicht sagen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:21 Mo 27.10.2014 | | Autor: | Marcel |
Hallo,
> Noch zwei Anmerkungen von mir:
>
> - Statt [mm][code]Faktoren=NaN*ones(1,length(bin_k_flipped));[/mm]
> [/code] kannst auch direkt
> [mm][code]Faktoren=NaN(1,length(bin_k_flipped));[/mm] [/code]
> schreiben.
>
> - Ebenso kannst du
> [mm][code]Faktoren=Faktoren(find(bin_k_flipped==num2str(1)));[/mm]
> [/code] durch
> [mm][code]Faktoren=Faktoren(bin_k_flipped==num2str(1));[/mm] [/code]
> ersetzen
>
> Ersteres bringt keine Laufzeitgewinne, zweiteres ist aber
> schneller. Ob das auch in Octave funktioniert, kann ich
> allerdings nicht sagen.
Danke, ich werde es nachher mal testen.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:17 Mo 27.10.2014 | | Autor: | Marcel |
Hallo,
> Noch zwei Anmerkungen von mir:
>
> - Statt [mm][code]Faktoren=NaN*ones(1,length(bin_k_flipped));[/mm]
> [/code] kannst auch direkt
> [mm][code]Faktoren=NaN(1,length(bin_k_flipped));[/mm] [/code]
> schreiben.
>
> - Ebenso kannst du
> [mm][code]Faktoren=Faktoren(find(bin_k_flipped==num2str(1)));[/mm]
> [/code] durch
> [mm][code]Faktoren=Faktoren(bin_k_flipped==num2str(1));[/mm] [/code]
> ersetzen
>
> Ersteres bringt keine Laufzeitgewinne, zweiteres ist aber
> schneller.
> Ob das auch in Octave funktioniert, kann ich
> allerdings nicht sagen.
beides funktioniert so anscheinend auch in Octave.
Danke nochmals.
Gruß,
Marcel
|
|
|
|
