Gast
#5656495
Hallo, Ich benötige etwas Hilfe und zwar hätte ich gern die Iterative Umformung von. Mir ist klar das ich ne schleife reinbauen muss um den Rekursionsaufruf wegzubekommen:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
Moin, helfen kann ich dir nicht. Was macht denn der Algorithmus? Kannst du den Variablen und der Funktion mal aussagekräftigere Namen geben?
Gast
#5656616
Die Funktion findet man hier: montgomery-multiplikation - http://www.inf.fh-flensburg.de/lang/algorithmen/arithmetik/montgomery-multiplikation.htm Diese Funktion bildet das Inverse Element zur Berechnung der montgomery multiplikation a*b*2^-k % M
Bspw. so:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | |
9 | |
Die Zeile
1 | |
im Originalcode ist übrigens überflüssig.
Gast
#5656878
Yalu, ich weis garnicht wie ich dir danken kann :)
Die rekursive Lösung ist IMHO dennoch die elegantere, und ich hatte einige Mühe, den nichtrekursiven Algorithmus so hinzubiegen, dass er ähnlich effizient wie der rekursive ist. Auch der Stackverbrauch ist hier kaum ein Argument gegen die Rekursion, da er nur mit log2(k) bzw. log2(log2(m)) wächst, angesichts des Speicherverbrauchs von m also vernachlässigbar ist.
Gast
#5657004
Vielen Dank Yalu. Für mich ist es nur in der Iterativen Form möglich den Algorithmus in Verilog zu übertragen.
Falls es um Krypto geht, dann sollte man sich u.U. ein paar Paper dazu ansehen (u.a. auch auf Wikipedia verlinkt), die auch die Seitenkanalresistenz und Fehlersicherheit betrachten u.a.: The Montgomery Powering Ladder https://cr.yp.to/bib/2003/joye-ladder.pdf Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers http://www.caad.arch.ethz.ch/noolab/files/external/conferences/IoT2010_proceedings/pdf/WS1/WS1_6.%20seciot2010_submission_12_final_v0.pdf#page=8
Gast
#5675643
Siehe auch hier: http://www.inf.fh-flensburg.de/lang/zahlentheorie/hensel-lifting.htm