Square and Multiply

Square and Multiply

Unter dem Schnellen Potenzieren versteht man ein mathematisch optimiertes Verfahren, dessen bekanntester Vertreter das „Square & Multiply“ ist. Es stellt eine Möglichkeit dar, um die Berechnung von natürlichen Zahlen mit großen Exponenten zu beschleunigen, in dem es versucht, Rechenoperationen einzusparen.

Inhaltsverzeichnis

Square & Multiply

Das „Square-&-Multiply“-Verfahren beschreibt eine Methode, um schnell Potenzen zu berechnen.

Einsatzgebiete

Das Verfahren ist für folgende zwei Fragestellungen geeignet:

  • ac
  • a^c \,\mathrm{mod}\, n

Das Verfahren ist nicht nur auf die Multiplikation beschränkt, sondern kann für verschiedenste Operationen (z. B. Elliptische Kurven-Addition) adaptiert werden.

Verfahren

„Square & Multiply“ nutzt die Tatsache, dass ac eindeutig als a^c = a^{1\cdot b_0} \cdot a^{2\cdot b_1} \cdot a^{4\cdot b_2} \cdot \dots \cdot a^{2^n \cdot b_n} geschrieben werden kann, wobei b_i \in \{0,1\} und \sum_{i=0}^{n} b_i \cdot 2^i = c. Die bis sind also die Stellen von c in der Darstellung als Binärzahl.

Dies kann man wiederum umformen und erhält folgende Form: a^c= a^{b_0}(a^{b_1}(\dots(a^{b_{n-1}}(a^{b_n})^2)^2\dots)^2)^2

Algorithmus

Gegeben:

Gesucht:

  • res=a^c\;\bmod{m}

Ablauf:

Square & Multiply 
 res = a
 for i=n-1..0
    res = res^2 mod m
    if b_i = 1
       res = (res * a) mod m
    end-if
 end-for

Wenn keine modulare Reduzierung vonnöten ist, wird diese einfach weggelassen.

Möchte man die Punktmultiplikation für elliptische Kurven implementieren, muss man die Quadrierung und die Multiplikation durch das jeweilige Äquivalent ersetzen. Der adaptierte Algorithmus hätte folgende Form.

Gegeben:

Gesucht:

  • Q=c \cdot P
Square & Multiply für elliptische Kurven 
 Q=INF
 for i=n..0
    Q = 2*Q
    if b_i = 1
       Q = Q + P
    end-if
 end-for

Beispiel

Gegeben:

  • a = 2
  • c = 11
  • b = 1011


res = 1
  • Schleifendurchlauf 1: b3 = 1
res = res2 = 1
res = res * a = 2
  • Schleifendurchlauf 2: b2 = 0
res = res2 = 4
  • Schleifendurchlauf 3: b1 = 1
res = res2 = 16
res = res * a = 32
  • Schleifendurchlauf 4: b0 = 1
res = res2 = 1024
res = res * a = 2048

Laufzeitanalyse

Bei der einfachen und langsamen Potenzierung von ac multipliziert man a (c − 1)-mal mit sich selbst. Beim „Square & Multiply“ werden lediglich log2(c) Schleifendurchläufe benötigt (log2(c) entspricht hierbei ungefähr der Länge der Zahl c in der Binärdarstellung). In jedem Schleifendurchlauf kommt es zu einer Quadrierung (wobei die erste Quadrierung vernachlässigt werden kann) und eventuell einer Multiplikation. Asymptotisch werden O(log(c)) Operationen (die Basis des Logarithmus ist in diesem Fall nicht von Bedeutung) benötigt, wogegen O(c) Operationen bei der einfachen Potenzierung zu Buche schlagen. O bezeichnet eine asymptotische obere Schranke für das Laufzeitverhalten des Algorithmus. Wie man leicht einsieht, ist das „Square-&-Multiply“-Verfahren sehr viel effizienter als das einfache Verfahren. Dieser verringerte Anspruch an die Rechenleistung ist bei großen Basen und Exponenten enorm.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Square-and-Multiply-Algorithmus — Unter dem Schnellen Potenzieren versteht man ein mathematisch optimiertes Verfahren, dessen bekanntester Vertreter das „Square Multiply“ ist. Es stellt eine Möglichkeit dar, um die Berechnung von natürlichen Zahlen mit großen Exponenten zu… …   Deutsch Wikipedia

  • Square — may mean:Mathematics*Square (algebra), to multiply a number or other quantity by itself **Perfect square **Square matrix **Square number **Square root*Square (geometry), a polygon with four equal sides and angles **Unit square*Square wave, a… …   Wikipedia

  • square — ► NOUN 1) a plane figure with four equal straight sides and four right angles. 2) an open, typically four sided, area surrounded by buildings. 3) an area within a military barracks or camp used for drill. 4) the product of a number multiplied by… …   English terms dictionary

  • square — [[t]skwe͟ə(r)[/t]] ♦♦ squares, squaring, squared 1) N COUNT A square is a shape with four sides that are all the same length and four corners that are all right angles. Serve the cake warm or at room temperature, cut in squares... There was a… …   English dictionary

  • square — squarable, adj. squarelike, adj. squareness, n. squarer, n. /skwair/, n., v., squared, squaring, adj., squarer, squarest, adv. n. 1. a rectangle having all four sides of equal length …   Universalium

  • square — noun 1》 a plane figure with four equal straight sides and four right angles.     ↘something that is the shape of a square or a cube.     ↘historical a body of infantry drawn up in rectangular form. 2》 an open, typically four sided, area… …   English new terms dictionary

  • square — [[t]skwɛər[/t]] n. v. squared, squar•ing, 1) math. a rectangle having all four sides of equal length 2) something having or resembling this form, as a city block 3) an open area formed by the intersecting of two or more streets 4) gam a… …   From formal English to slang

  • square — [skwer] n. [ME < OFr esquarre < VL * exquadra < * exquadrare, to make square < L ex, out + quadrare, to square < quadrus, a square < base of quattuor,FOUR] 1. a plane figure having four equal sides and four right angles: see… …   English World dictionary

  • Square — Square, v. t. [imp. & p. p. {Squared} (skw[^a]rd); p. pr. & vb. n. {Squaring}.] [Cf. OF. escarrer, esquarrer. See {Square}, n.] 1. To form with four equal sides and four right angles. Spenser. [1913 Webster] 2. To form with right angles and… …   The Collaborative International Dictionary of English

  • Multiply–accumulate operation — In computing, especially digital signal processing, the multiply–accumulate operation is a common step that computes the product of two numbers and adds that product to an accumulator. The hardware unit that performs the operation is known as a… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”