Diskussion:Schnelles Potenzieren

Mal eine Anmerkung an die Autoren: Ich habe diesen Artikel unter "Square and Multiply" gesucht und nicht gefunden. In der hier Vorliegenden Version kommt der Begriff "Square & Multiply" allerdings vor. Bitte indizieren sie auch die andere Schreibweise. Mit freundlichen Grüßen XXX

STIMMT. BITTE NACHHOLEN!

erledigt.

Überschneidung mit Artikel Binäre Exponentiation.

Hallo,

dieser Artikel überschneidet sich doch sehr mit dem Artikel Binäre Exponentiation.

Ich meine man sollte zumindest auf den anderen Artikel verweisen oder vielleicht sogar beide zusammenfassen?

Wolfgang Ertel schreibt in seinem Buch "Angewandte Kryptographie" 2. Auflage, Seite 82 zu diesem Algorithmus: „[…] (er hat) O(k³) Bit-Operationen durchzuführen. Diese kubische Komplexität führt zu relativ langen Rechenzeiten, insbesondere beim Entschlüsseln und bei der Signatur mit RSA, wo der längere geheime Schlüssel d benutzt wird.“

Wie lässt sich das mit O(log(c)) bzw. O(c)) vereinbaren ?

→→→ Im Artikel wird multiplizieren als eine Operation gezählt, im Buch werden Bit-Operationen gezählt. Die Multiplikation einer n-Bit-Zahl benötigt bis zu O(n²) Bit-Operationen. Paßt also beides. 77.131.154.181 10:26, 17. Dez. 2008 (CET)

Möchte dieses Thema auch aufgreifen. Auch wenn es mir nicht gefällt. Binäre Exponentiation enthält das gleiche und ist älter. ... Ein Zusammenführen wäre hier eventuell kein schlechter Weg. Was haltet ihr davon? -- KingLoeric 21:34, 6. Mai 2009 (CEST)

Ablauf square&multiply

Ich bin mir nicht sicher, aber müsste die Zeile

res = res^2 mod m

nicht eigentlich

a = a^2 mod m

lauten? Wenn ich mich irre - sorry. Beschäftige mich grade erst mit dem Thema. --Hco 15:41, 10. Feb. 2008 (CET)

meiner Meinung nach ist das Korrekt --Stasik 11:42, 11. Mar. 2008 (CET)

Falscher Algorithmus

die Zeile for i=0..n muss eigentlich for i=1..n lauten

mann lässt den Höchstwertigen Bit aus, wird klar wenn man nachrechnet --Stasik 11:42, 11. Mar. 2008 (CET)

Bitnummerierung

Ich finde es sehr seltsam und verwirrend, das im Absatz "Verfahren" das niederwertigste Bit die Nummer 0 bekommt, und im Absatz "Algorithmus" das höchstwertige. Im Algorithmus dann gibt es plötzlich nicht mehr n+1 sonder nur noch n Bits. Das sollte imo dringend homogenisiert werden, bevorzugt auf die Variante aus dem Absatz "Verfahren". 81.173.185.231 22:30, 17. Mai 2008 (CEST)

Algo: Square & Multiply

(Kopie von [1], zur Frage wo der Index im Algorithmus Square & Multiply starten sollte)

Betrachten wir den Fall n=2. Dann gibt es b_2, b_1 und b_0. b_2 ist immer 1. Das wird bei der Initalisierung res = a berücksichtigt. Nun der erste Schleifendurchlauf. Im Multiply-Schritt muss b_1 abgefragt werden, nicht b_0. Also muss i=n-1 sein und nicht i=n-2. Im 2. und letzten Schleifendurchlauf wird mit a multipliziert, wenn b_0=1 ist. Ende des Algorithmus'.

Und jetzt das ganze nochmal an einem handfesten Zahlenbeispiel zum mitrechen: Ich will 3^6 berechnen. Der Exponent 6 ist binär 110, also b_2=1, b_1=1 und b_0=0.

In der derzeitigen Version ergibt sich folgendes:

Vor der Schleife: res=3.

Nach dem ersten Durchlauf: res=9.

End.

In meiner Version:

Vor der Schleife: res=3.

Nach dem ersten Durchlauf: res=9*3=27.

Nach dem zweiten Durchlauf: res=27^2=729.

End.

Fazit: Ich habe über eine halbe Stunde damit verbracht, meine Korrektur zu rechtfertigen anstatt dass ich sie einfach machen durfte. Wäre mir unter normalen Umständen zu dumm gewesen, aber ich habe einem Schulkind dieses Thema als Referat verpasst.

-- Hansm 18:09, 5. Mai 2009 (CEST)

Sorry, ich hatte offenbar Tomaten auf den Augen und hab falschrum gedacht, natürlich muss es bei bei n oder n-1 anfangen aber auf keinen Fall bei n-2, wie ich es wieder reinrevertiert habe! Sorry dafür. Und auch hier hast du Recht: bei n anzufangen erübrigt sich durch das res=a. Willst du es nochmal verbessern oder soll ich? :-/ --χario 18:39, 5. Mai 2009 (CEST)

Ach, mach du das ruhig. Dann steht es wenigstens gleich drin. -- Hansm 18:50, 5. Mai 2009 (CEST)

Mit res=a anzufangen ist nicht korrekt. Man kann somit nicht mehr a^0 berechnen. res = a ist nur dann korrekt, wenn man folgende Voraussetzungen annimmt. Keine führenden 0en bin der Binärdarstellung (gut. das ist kein Problem). Die erste Zahl ist 1 (schließt a^0 aus). Deshalb hab ich das mal gleich geändert. -- KingLoeric 21:46, 6. Mai 2009 (CEST)