<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Square-and-Multiply</id>
	<title>Square-and-Multiply - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://wiki.flbk-hamm.de/index.php?action=history&amp;feed=atom&amp;title=Square-and-Multiply"/>
	<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Square-and-Multiply&amp;action=history"/>
	<updated>2026-11-16T00:43:08Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in FLBK-Wiki</subtitle>
	<generator>MediaWiki 1.46.2</generator>
	<entry>
		<id>https://wiki.flbk-hamm.de/index.php?title=Square-and-Multiply&amp;diff=3215&amp;oldid=prev</id>
		<title>Flbkwikiadmin: Die Seite wurde neu angelegt: „Beim RSA-Verfahren werden Zahlen mit riesigen Exponenten potenziert. Schritt für Schritt zu multiplizieren würde viel zu lange dauern. Das wiederholte Quadrieren und Multiplizieren kommt mit wenigen Rechenschritten aus.  ==Definition== &#039;&#039;&#039;Square-and-Multiply&#039;&#039;&#039; (deutsch: wiederholtes Quadrieren und Multiplizieren) ist ein Verfahren, das eine Potenz &lt;math&gt;a^x \bmod n&lt;/math&gt; mit wenigen Multiplikationen berechnet. Es nutzt die Darstellung des Exponent…“</title>
		<link rel="alternate" type="text/html" href="https://wiki.flbk-hamm.de/index.php?title=Square-and-Multiply&amp;diff=3215&amp;oldid=prev"/>
		<updated>2026-11-15T06:52:01Z</updated>

		<summary type="html">&lt;p&gt;Die Seite wurde neu angelegt: „Beim &lt;a href=&quot;/RSA-Verfahren&quot; title=&quot;RSA-Verfahren&quot;&gt;RSA-Verfahren&lt;/a&gt; werden Zahlen mit riesigen Exponenten potenziert. Schritt für Schritt zu multiplizieren würde viel zu lange dauern. Das wiederholte Quadrieren und Multiplizieren kommt mit wenigen Rechenschritten aus.  ==Definition== &amp;#039;&amp;#039;&amp;#039;Square-and-Multiply&amp;#039;&amp;#039;&amp;#039; (deutsch: wiederholtes Quadrieren und Multiplizieren) ist ein Verfahren, das eine Potenz &amp;lt;math&amp;gt;a^x \bmod n&amp;lt;/math&amp;gt; mit wenigen Multiplikationen berechnet. Es nutzt die Darstellung des Exponent…“&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Beim [[RSA-Verfahren]] werden Zahlen mit riesigen Exponenten potenziert. Schritt für Schritt zu multiplizieren würde viel zu lange dauern. Das wiederholte Quadrieren und Multiplizieren kommt mit wenigen Rechenschritten aus.&lt;br /&gt;
&lt;br /&gt;
==Definition==&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Square-and-Multiply&amp;#039;&amp;#039;&amp;#039; (deutsch: wiederholtes Quadrieren und Multiplizieren) ist ein Verfahren, das eine Potenz &amp;lt;math&amp;gt;a^x \bmod n&amp;lt;/math&amp;gt; mit wenigen Multiplikationen berechnet. Es nutzt die Darstellung des Exponenten &amp;lt;math&amp;gt;x&amp;lt;/math&amp;gt; im [[Dualsystem]]:&lt;br /&gt;
&lt;br /&gt;
* Jede 1 in der Dualdarstellung steht für eine Zweierpotenz. Der Exponent ist die Summe dieser Zweierpotenzen.&lt;br /&gt;
* Nach den Potenzgesetzen ist &amp;lt;math&amp;gt;a^x&amp;lt;/math&amp;gt; deshalb das Produkt der Potenzen &amp;lt;math&amp;gt;a^1; a^2; a^4; a^8; \dots&amp;lt;/math&amp;gt;, die zu den Einsen gehören.&lt;br /&gt;
* Diese Potenzen entstehen durch fortgesetztes Quadrieren, denn &amp;lt;math&amp;gt;\left(a^u\right)^2 = a^{2u}&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Nach jeder Rechnung wird der Rest modulo &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; gebildet, damit die Zahlen klein bleiben (siehe [[Modulo#Rechenregeln|Rechenregeln]]).&lt;br /&gt;
&lt;br /&gt;
==Von rechts nach links==&lt;br /&gt;
Die Rechnung wird in einer Tabelle geführt, der &amp;#039;&amp;#039;&amp;#039;Belegungstabelle&amp;#039;&amp;#039;&amp;#039;. Sie hat für jedes Bit des Exponenten eine Zeile, beginnend mit dem Bit ganz rechts.&lt;br /&gt;
&lt;br /&gt;
# Den Exponenten ins Dualsystem umrechnen und die Bits von rechts nach links untereinander schreiben.&lt;br /&gt;
# Spalte &amp;#039;&amp;#039;&amp;#039;Quadrat&amp;#039;&amp;#039;&amp;#039;: In der ersten Zeile steht &amp;lt;math&amp;gt;a \bmod n&amp;lt;/math&amp;gt;. In jeder weiteren Zeile steht das Quadrat des Wertes darüber, modulo &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt;. So entstehen der Reihe nach &amp;lt;math&amp;gt;a^1; a^2; a^4; a^8; \dots&amp;lt;/math&amp;gt;&lt;br /&gt;
# Spalte &amp;#039;&amp;#039;&amp;#039;Zwischenergebnis&amp;#039;&amp;#039;&amp;#039;: Steht in der Zeile das Bit 1, wird das bisherige Zwischenergebnis mit dem Quadrat dieser Zeile multipliziert, modulo &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt;. Beim ersten Bit 1 ist das Zwischenergebnis das Quadrat selbst. Steht in der Zeile das Bit 0, bleibt das Zwischenergebnis unverändert.&lt;br /&gt;
# Das letzte Zwischenergebnis ist &amp;lt;math&amp;gt;a^x \bmod n&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
==Von links nach rechts==&lt;br /&gt;
Die zweite Form arbeitet die Bits von links nach rechts ab und braucht nur ein Zwischenergebnis:&lt;br /&gt;
&lt;br /&gt;
# Mit dem Zwischenergebnis 1 beginnen.&lt;br /&gt;
# Für jedes Bit, beginnend ganz links: das Zwischenergebnis quadrieren.&lt;br /&gt;
# Ist das Bit 1, zusätzlich mit &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; multiplizieren.&lt;br /&gt;
# Nach jedem Schritt den Rest modulo &amp;lt;math&amp;gt;n&amp;lt;/math&amp;gt; bilden.&lt;br /&gt;
&lt;br /&gt;
Beide Formen liefern dasselbe Ergebnis.&lt;br /&gt;
&lt;br /&gt;
==Aufwand==&lt;br /&gt;
Hat der Exponent in der Dualdarstellung &amp;lt;math&amp;gt;t&amp;lt;/math&amp;gt; Bit, braucht das Verfahren &amp;lt;math&amp;gt;t - 1&amp;lt;/math&amp;gt; Quadrierungen und für jede weitere 1 nach der ersten eine Multiplikation. Das sind zusammen höchstens &amp;lt;math&amp;gt;2 \cdot (t - 1)&amp;lt;/math&amp;gt; Rechenschritte, denn auch jede Quadrierung ist eine Multiplikation. Wer dagegen &amp;lt;math&amp;gt;a&amp;lt;/math&amp;gt; immer wieder mit sich selbst multipliziert, braucht &amp;lt;math&amp;gt;x - 1&amp;lt;/math&amp;gt; Multiplikationen.&lt;br /&gt;
&lt;br /&gt;
Der Aufwand wächst also nur mit der Länge des Exponenten in Bit und nicht mit seinem Wert. Erst dadurch lassen sich Potenzen mit den riesigen Exponenten des RSA-Verfahrens überhaupt berechnen.&lt;br /&gt;
&lt;br /&gt;
==Umsetzung in Java==&lt;br /&gt;
Die Methode arbeitet von rechts nach links. Das letzte Bit des Exponenten liefert &amp;lt;code&amp;gt;exponent % 2&amp;lt;/code&amp;gt;, die Division durch 2 entfernt es.&lt;br /&gt;
&lt;br /&gt;
&amp;lt;syntaxhighlight lang=&amp;quot;java&amp;quot;&amp;gt;&lt;br /&gt;
public static long potenzMod(long basis, long exponent, long modul) {&lt;br /&gt;
    long ergebnis = 1;&lt;br /&gt;
    long quadrat = basis % modul;&lt;br /&gt;
    while (exponent &amp;gt; 0) {&lt;br /&gt;
        if (exponent % 2 == 1) {&lt;br /&gt;
            ergebnis = ergebnis * quadrat % modul;&lt;br /&gt;
        }&lt;br /&gt;
        quadrat = quadrat * quadrat % modul;&lt;br /&gt;
        exponent = exponent / 2;&lt;br /&gt;
    }&lt;br /&gt;
    return ergebnis;&lt;br /&gt;
}&lt;br /&gt;
&amp;lt;/syntaxhighlight&amp;gt;&lt;br /&gt;
&lt;br /&gt;
Der Datentyp &amp;lt;code&amp;gt;long&amp;lt;/code&amp;gt; ist nötig, weil das Produkt zweier Zahlen kleiner als der Modul nicht mehr in ein &amp;lt;code&amp;gt;int&amp;lt;/code&amp;gt; passen muss. Für Moduln in der Größe echter Schlüssel reicht auch &amp;lt;code&amp;gt;long&amp;lt;/code&amp;gt; nicht. Dafür gibt es in Java die Klasse &amp;lt;code&amp;gt;BigInteger&amp;lt;/code&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
==Beispiele==&lt;br /&gt;
===Potenz mit der Belegungstabelle berechnen===&lt;br /&gt;
Gesucht ist &amp;lt;math&amp;gt;5^{23} \bmod 133&amp;lt;/math&amp;gt;. Der Exponent im Dualsystem: &amp;lt;math&amp;gt;23 = 16 + 4 + 2 + 1 = 10111_2&amp;lt;/math&amp;gt;. Damit gilt &amp;lt;math&amp;gt;5^{23} = 5^{16} \cdot 5^{4} \cdot 5^{2} \cdot 5^{1}&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot; style=&amp;quot;text-align:center&amp;quot;&lt;br /&gt;
! Bit !! Potenz !! Quadrat mod 133 !! Zwischenergebnis mod 133&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;5^{1}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;5&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;5&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;5^{2}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;5^{2} = 25&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;5 \cdot 25 = 125&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;5^{4}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;25^{2} = 625 \equiv 93&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;125 \cdot 93 = 11625 \equiv 54&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;5^{8}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93^{2} = 8649 \equiv 4&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;5^{16}&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;4^{2} = 16&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;54 \cdot 16 = 864 \equiv 66&amp;lt;/math&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
Das letzte Zwischenergebnis ist das Ergebnis: &amp;lt;math&amp;gt;5^{23} \bmod 133 = 66&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Dieselbe Potenz von links nach rechts berechnen===&lt;br /&gt;
Die Bits des Exponenten werden jetzt von links nach rechts abgearbeitet, das Zwischenergebnis beginnt mit 1:&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot; style=&amp;quot;text-align:center&amp;quot;&lt;br /&gt;
! Bit !! quadrieren mod 133 !! bei Bit 1 mit 5 multiplizieren mod 133&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;1^{2} = 1&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;1 \cdot 5 = 5&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 0 || &amp;lt;math&amp;gt;5^{2} = 25&amp;lt;/math&amp;gt; || –&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;25^{2} = 625 \equiv 93&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93 \cdot 5 = 465 \equiv 66&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;66^{2} = 4356 \equiv 100&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;100 \cdot 5 = 500 \equiv 101&amp;lt;/math&amp;gt;&lt;br /&gt;
|-&lt;br /&gt;
| 1 || &amp;lt;math&amp;gt;101^{2} = 10201 \equiv 93&amp;lt;/math&amp;gt; || &amp;lt;math&amp;gt;93 \cdot 5 = 465 \equiv 66&amp;lt;/math&amp;gt;&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
Auch hier ist &amp;lt;math&amp;gt;5^{23} \bmod 133 = 66&amp;lt;/math&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
===Aufwand vergleichen===&lt;br /&gt;
Für &amp;lt;math&amp;gt;5^{23} \bmod 133&amp;lt;/math&amp;gt; genügen 4 Quadrierungen und 3 Multiplikationen. Wer 5 Schritt für Schritt mit sich selbst multipliziert, braucht 22 Multiplikationen.&lt;br /&gt;
&lt;br /&gt;
[[Kategorie:Kryptologie]]&lt;br /&gt;
[[Kategorie:Mathematik]]&lt;br /&gt;
[[Kategorie:AHR I Informatik LK]]&lt;/div&gt;</summary>
		<author><name>Flbkwikiadmin</name></author>
	</entry>
</feed>