Hallo,
erstmal vielen Dank für die vielen Antworten!
@lunar: Naja, das mit den binären Zahlen ist schon ne Zeit her
Und das rechnen damit fand ich auch nicht sehr ansprechend (Vielleicht war Schieberegister rekonstruieren damals auch einfach zu viel für mich). Aber ich habe mir deinen Rat zu Herzen genommen und mich bei Wikipedia eingelesen; jetzt ist mir auch klar geworden, dass mit AND und OR nicht die bool'schen Vergleiche, wie ich dachte, gemeint waren.
@nomnom: Vielen Dank für dein C-Beispiel! Mir ist leider nicht ganz klar, was
(Zeile 10) an sich macht. Vielleicht könntest du das noch ein wenig näher erläutern. Da du unsigned-Typen verwendest, ist mir auch erst richtig klar geworden, dass das ganze nur für x und k als Element der natürlichen Zahlen definiert ist - Kann man den Algorithmus rein theoretisch auch auf Floats (3^(1/2)) und negative Zahlen (-3^5) erweitern? Hier brauche ich kein Code-Snippet, es würde mich nur interessieren
@all: Ich habe mal mein Coding for Fun Buch raus gekramt; dort wird RSA in Python realisiert und auch einmal der Square & Multiply-Algorithmus angesprochen und verwendet. Hierzu zwei Fragen:
a) Der Autor verwendet keine Strings, sondern prüft mit modulo 2, ob er nun multiplizieren oder nur quadrieren muss. Das ist aber nicht recht viel effektiver als mein (anscheinend nicht so rosiger) Ansatz von oben, oder?
b) Es wird behauptet, man könne das Zwischenergebnis von jedem Durchlauf Modulo n reduzieren, was natürlich bei großen Zahlen enorm Speicher und die Berechnung evtl. schneller macht. Ist das an sich korrekt oder sollte ich da lieber die Finger davon lassen?
Ansonsten: Ich lese mich jetzt mal wieder in das ganze binäre Rechenzeug ein und versuche demnächst/irgendwann mal etwas lauffähiges hier zu posten.
Gruß,
heiliga horsd