square + multiply

[Mäxle]

Moin,

könnt ihr mir bitte verraten, wie man von einer utopisch großen Zahl, dargestellt durch b^n mit Hilfe von square and multiply herausfinden kann, wie die letzten beiden Dezimalstellen der Zahl aussehen müssten.
Wie man das Verfahren anwendet, um den Modulo herauszufinden, weiß ich. Aber irgendwie fehlt mir die Idee, das auf das Aussehen der Zahl selbst bzw. deren letzte i Derzimalstellen zu übertragen.

Danke!

[Vinzenz Mai]

Hallo,

könnt ihr mir bitte verraten, wie man von einer utopisch großen Zahl, dargestellt durch b^n mit Hilfe von square and multiply herausfinden kann,

ich habe leider keine Ahnung, wie "square" und "multiply" definiert sein sollen.

Soll square das Quadrat einer Zahl liefern, d.h. square(n) = n∙n?
Soll multiply eine Funktion sein, die das Produkt zweier zahlen zurückgibt,
d.h. multiply(n,m) = n∙m?

wie die letzten beiden Dezimalstellen der Zahl aussehen müssten.
Wie man das Verfahren anwendet, um den Modulo herauszufinden, weiß ich. Aber irgendwie fehlt mir die Idee, das auf das Aussehen der Zahl selbst bzw. deren letzte i Derzimalstellen zu übertragen.

Wenn Du Modulo anwenden kannst, warum tust Du es nicht.
Die i-letzte Stelle ist die Ziffer x = (b^n) modulo (10^i)
Der Wert ist x∙(10^i), die i-letzten Ziffern bekommst Du über die entsprechende Summe:

letzte i Stellen = Summe (j läuft von 1 bis i) ((b^n) modulo (10^j)∙(10^j)) [1]

Freundliche Grüße

Vinzenz

[1] Ich sollte mich mal wieder mit LaTex beschäftigen :-)

[Otto]

Hi Vinzenz Mai,

ich habe leider keine Ahnung, wie "square" und "multiply" definiert sein sollen.

"Square and Multiply" ist ein Algo. für das schnell Potenzieren von sehr großen Zahlen, wird u.a. bei RSA verwendet.
http://de.wikipedia.org/wiki/Schnelles_Potenzieren
MfG
Otto

[Vinzenz Mai]

Hallo Otto,

ich habe leider keine Ahnung, wie "square" und "multiply" definiert sein sollen.

"Square and Multiply" ist ein Algo. für das schnell Potenzieren von sehr großen Zahlen, wird u.a. bei RSA verwendet.
http://de.wikipedia.org/wiki/Schnelles_Potenzieren

das Verfahren war mir bekannt - allerdings nicht dass man dieses Verfahren auch "Square and Multiply" nennt. Danke für den Link.

Freundliche Grüße

Vinzenz

[MudGuard]

Hi,

könnt ihr mir bitte verraten, wie man von einer utopisch großen Zahl, dargestellt durch b^n mit Hilfe von square and multiply herausfinden kann, wie die letzten beiden Dezimalstellen der Zahl aussehen müssten.
Wie man das Verfahren anwendet, um den Modulo herauszufinden, weiß ich.

D.h. Du kannst bereits b^n modulo 100 herausfinden.

x ist Deine gegebene Zahl.

a sei dann x % 100 und c sei x - a.

Sprich: a sind die letzten 2 Ziffern, b die Zahl x mit Ersetzung der letzten 2 Ziffern durch Nullen.
Im Beispiel: 1234 ist a = 34, c = 1200.

x² = (a + c)² = a² + 2ac + c²

c endet also auf 2 Nullen, c² endet damit auf 4 Nullen, c² spielt für die letzten 2 Ziffern von x² also keine Rolle.
2ac endet ebenfalls auf 2 Nullen, spielt also für die letzten 2 Ziffern von x² ebenfalls keine Rolle.

Die letzten 2 Ziffern von x² werden also nur von a² beeinflußt, also von den letzten beiden Ziffern von x.

Wenn Du also, wie Du ja schriebst, die letzten beiden Ziffern von b^n ermitteln kannst, kannst Du auch die letzten beiden Ziffern des Quadrats ermitteln, indem Du das Quadrat der Zahl aus den beiden letzten Ziffern bildest.

cu,
Andreas