Montgomery Multiplikation für LongInt
-
Hallo Zusammen,
schreibe gerade eine kleine Bibliothek für die Verarbeitung von Langzahlen (LongInt). Es gibt da einen, unter bestimmten Bedingungen, sehr effizienten Algorithmus zur Berechnung einer modularen Multipilkation: (a * b mod c). Es ist die sogenannte Montgommery-Multiplikation. Habe da einiges zu gelesen, aber irgendwie versteh ich da was nicht...
Ich bräuchte mal ein Stück Code, dass funktioniert, um rauszufinden was ich übersehen habe. Kann meinen Kram dann entsprechend anpassen. Wäre schön, falls hemand etwas für mich hätte! Vielen Dank schon mal!
-
dieses \1: http://www.alpertron.com.ar/ECM.HTM
verwendet das. den code kannst du downloaden (ist ziemlich hässlich), aber vielleicht hilfts.
-
Vielen Dank für die rasche Antwort!
Leider versteh ich nichts von JAVA und der Code scheint mir besonders unleserlich zu sein...
Vielleicht hat ja jemand ja etwas in C/C++?!?
-
-
herzlichen Dank! Allerdings kenn ich dieses pdf bereits...
das problem ist, dass ich (so meine ich wenigstens) alles korrekt umgesetzt habe und trotzdem kommt nicht das gewünschte heraus - daher bräuchte ich jetzt mal einen C-code, der funktioniert, so dass ich herausfinden kann, was ich falsch mache...
-
ich versteh u.a. nicht warum in den Formeln einmal z.B. Größen mit Index und solche ohne Index gemischt auftreten! Was bedeutet das? Z.B. z = v(i) * b^î * v von 0 bis n-1 - was genau bedeutet das? wird v(i) * b^i mit allen (also jedem einzelnen) v(j) von 0 bis n - 1 multipliziert - und dann evt. addiert, oder wie?
-
kannst du mal die genaue stelle angeben? ich glaube du verwechselst das kursive u von dem kursiven v
-
und zeig doch mal deinen code
-
auf Seite 7 des oben erwähnten dokumentes z.B.
-
an meinem code habe ich ziemlich rumgepfuscht, um alles möglich zu testen... so kann man den niemanden zeigen.
muss erstmal alles wieder einigermaßen aufmöbeln...
-
das ist z := z + u_i*b^i*v
-
Raineer K. schrieb:
Leider versteh ich nichts von JAVA und der Code scheint mir besonders unleserlich zu sein...
Vielleicht hat ja jemand ja etwas in C/C++?!?ja, der code ist wirklich grausam (es scheint irgendwie ein naturgesetz zu sein: je mehr einer drauf hat, desto hässlicheren code schreibt er), aber die MontgomeryMult()-funktion kannst du mit wenig aufwand nach C portieren. musst natürlich beachten, dass in Java 'int' 32 bits und 'long' 64 bits (signed) sind.
-
Hallo,
hast Du Dein Problem mittlerweile gelöst, ich arbeite an was ähnlichem...
VG