Snabba exponentieringsalgoritmer

Snabba exponentieringsalgoritmer ( dikotom exponentieringsalgoritm, binär exponentieringsalgoritm) är algoritmer utformade för att höja ett tal till en naturlig potens i färre multiplikationer än vad som krävs för att bestämma graden [1] . Algoritmerna bygger på det faktum att för att höja ett tal till en potens , är det inte nödvändigt att multiplicera talet med sig själv en gång, utan du kan multiplicera redan beräknade potenser. I synnerhet, om potensen av två, då för att höja till en potens räcker det med att kvadrera antalet gånger, medan du spenderar multiplikationer istället för . Till exempel, för att höja ett tal till åttonde potensen, istället för att utföra sju multiplikationer , kan du kvadrera talet ( ), sedan kvadrera resultatet igen för att få fjärde potensen ( ), och slutligen kvadrera resultatet igen och få svaret ( ). $x$ $n$ $x$ $n$ $x$ $n$ $n=2^k$ $n$ $k$ $k$ $2^k$ $x$ $x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x$ $x^{2}=x\cdot x$ ${\displaystyle x^{4}=x^{2}\cdot x^{2))$ ${\displaystyle x^{8}=x^{4}\cdot x^{4))$

Dessutom använder vissa algoritmer för ytterligare optimering det faktum att kvadreringsoperationen är snabbare än multiplikationsoperationen på grund av att siffrorna i faktorn upprepas vid kvadrering [2] .

Den binära exponentieringsalgoritmen föreslogs först på 1400-talet av den persiske matematikern Al-Kashi [3] .

Dessa algoritmer är inte alltid optimala. Till exempel, när man använder vänster-till-höger-schemat, kommer en snabb exponentiering av n = 15 att kräva tre multiplikationer och tre kvadreringsoperationer, även om höjning till 15:e potens kan utföras i 3 multiplikationer och 2-kvadrering [4] . Optimal exponentiering motsvarar konstruktionen av den kortaste additivkedjan .

Beskrivning

Huvudalgoritmen för snabb exponentiering är "vänster till höger"-schemat. Den har fått sitt namn från det faktum att exponentens bitar ses från vänster till höger, det vill säga från högt till lågt [5] .

Låta

n=(\overline {m_{{k}}m_{{k-1}}...m_{{1}}m_{{0}}})_{2}

är en binär representation av grad n , dvs.

n=m_{{k}}\cdot 2^{{k}}+m_{{k-1}}\cdot 2^{{k-1}}+\dots +m_{{1}}\cdot 2 +m_{{0}},

var . Sedan $m_{{k}}=1,m_{{i}}\in \{0,1\}$

x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}}) ^{2}\dots)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}

[5] .

Åtgärdssekvensen när du använder detta schema kan beskrivas enligt följande:

Representera exponent n i binär form
Om = 1, då kvadreras det aktuella resultatet och multipliceras sedan med x. Om = 0, då kvadreras det aktuella resultatet helt enkelt [6] . Index i ändras från k -1 till 0 [7] . $mi$ $mi$

Således reduceras den snabba exponentieringsalgoritmen till en multiplikativ analog av Horners schema [6] :

{\begin{Bmatrix}s_{1}=x\\s_{{i+1}}=s_{i}^{2}\cdot x^{{m_{{ki))))\\i=1 ,2,\dots ,k\end{Bmatrix}}.

Generaliseringar

Låt paret ( S , *) vara en halvgrupp , då kan vi kalla operationen * multiplikation och definiera operationen att höja till en naturlig potens:

a^{n}=\left\{{\begin{array}{ll}a&n=1\\a*\left(a^{{n-1}}\right)&n>1\end{array}} \höger.

Sedan, för att beräkna värdena för ett n i vilken semigrupp som helst ( särskilt i en Abelisk grupp ), kan man använda algoritmer för snabb exponentiering [8] .

Exempel på problemlösning

Genom att tillämpa algoritmen beräknar vi 21 13 :

{\displaystyle 13_{10}=1101_{2))

m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1

{\begin{aligned}21^{13}&=(((1\cdot 21^{m_{3)))^{2}\cdot 21^{m_{2)))^{2} \cdot 21^{m_{1}})^{2}\cdot 21^{m_{0}}\\&=(((1\cdot 21^{1})^{2}\cdot 21^{ 1})^{2}\cdot 21^{0})^{2}\cdot 21^{1}\\&=(((1\cdot 21)^{2}\cdot 21)^{2} \cdot 1)^{2}\cdot 21\\&=((21^{2}\cdot 21)^{2})^{2}\cdot 21\\&=((441\cdot 21)^ {2})^{2}\cdot 21\\&=85766121^{2}\cdot 21\\&=154472377739119461\end{aligned}}

Höger till vänster-schema

I detta schema, till skillnad från "vänster till höger"-schemat, ses exponentens bitar från det lägsta till det högsta [5] .

Sekvensen av åtgärder i implementeringen av denna algoritm.

Uttryck exponenten n binärt.
Ställ in hjälpvariabeln z lika med talet x.
1. Om , då det aktuella resultatet multipliceras med z , och talet z i sig kvadratiseras. Om = 0 behöver du bara kvadratisera z [6] . I detta fall varierar indexet i , till skillnad från schemat från vänster till höger, från 0 till k -1 inklusive [7] . $m_{i}=1$ $mi$

Denna krets innehåller lika många multiplikationer och kvadrater som "vänster till höger"-kretsen. Men trots detta är vänster-till-höger-schemat mer lönsamt än höger-till-vänster-schemat, speciellt om exponenten innehåller många enheter. Poängen är att i schemat, från vänster till höger, innehåller operationsresultatet = resultat · x en konstant multiplikator x . Och för litet x (vilket ofta är fallet i primatitetstester) blir multiplikationen snabb. Till exempel, för x = 2 kan vi ersätta multiplikationsoperationen med additionsoperationen [7] .

Den matematiska motiveringen för driften av denna algoritm kan representeras av följande formel:

d=a^{n}=

= a^{\sum_{i=0}^k m_i\cdot 2^i} =

= a^{m_0}\cdot a^{2m_1}\cdot a^{2^2*m_2}\cdot ... \cdot a^{2^k*m_k}=

= a^{m_0}\cdot (a^2)^{m_1}\cdot (a^{2^2})^{m_2}\cdot ... \cdot (a^{2^k})^{ m_k}=

=\prod _{{i=0}}^{k}{(a^{{2^{{i}}}})^{{m_{i}}}}

[9] .

Exempel . Låt oss beräkna värdet 21 13 med hjälp av exponentieringsschemat från höger till vänster .

i	0	ett	2	3
$a^{2^{i}}$	21	441	194 481	37 822 859 361
$m_1$	ett	0	ett	ett

21 194 481 = 4084 101
4084 101 37 822 859 361 = 154 472 377 739 119 461

Beräkningskomplexitet

För både vänster-till-höger- och höger-till-vänster-schemat är antalet kvadreringsoperationer detsamma och lika med k, där k är längden på exponenten n i bitar, . Antalet nödvändiga multiplikationsoperationer är lika med Hamming -vikten , det vill säga antalet element som inte är noll i den binära representationen av talet n . I genomsnitt krävs multiplikationsoperationer [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

Till exempel, för att höja en siffra till hundrade potens, kommer denna algoritm att kräva endast 8 operationer av multiplikation och kvadrering [5] .

Som jämförelse, med standardexponentieringsmetoden, krävs en multiplikationsoperation, det vill säga antalet operationer kan uppskattas till [10] . $n-1$ $På)$

Algoritmoptimering

I allmänhet är kvadreringsoperationen snabbare än multiplikationsoperationen. Fönstermetoden låter dig minska antalet multiplikationsoperationer och därför göra exponentieringsalgoritmen mer optimal [8] .

Fönstret är faktiskt basen i talsystemet [7] . Låt w vara bredden på fönstret, det vill säga w tecken i indikatorn tas i beaktande åt gången.

Tänk på fönstermetoden.

För förberäknade x i $i = \overline {0, 2^w-1}$
Exponenten presenteras i följande form: , där $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \in {(0, 1, ..., 2^w-1)}$
Låt y vara variabeln där det slutliga resultatet kommer att beräknas. Låt . $y=x^{n_{k/w}}$
För alla i = k/w - 1, k/w - 2, ..., 0, gör följande:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Denna algoritm kräver k -kvadrering, men antalet multiplikationer reduceras till k/w i genomsnitt [8] .

Ännu effektivare är metoden med skjutfönster. Det ligger i det faktum att fönstrets bredd under genomförandet av processen kan ändras:

Exponenten representeras som , där , och e i+1 — e i ≥ w . $n = \sum_{i=0}^{l}{n_i\cdot2^{e_i}}$ $n_i \in {(1, 3, 5, ..., 2^w-1)}$
För x beräknas i . Vidare kommer vi att beteckna x i som x i . $i = (1, 3, 5, ..., 2^w-1)$
Låt y vara variabeln där det slutliga resultatet kommer att beräknas. Låt . $y=x^{n_{l}}$
För alla i = l - 1, l - 2, ..., 0 gör följande:
1. För alla j från 0 till e i+1 - e i - 1 y kvadrat
2. $j = m_i$
3. $y = y\cdot x_j$
För alla j från 0 till e 0 - 1 y kvadrat [8] .

Antalet exponentieringsoperationer i denna algoritm är detsamma som i fönstermetoden, men antalet multiplikationsoperationer har reducerats till l , det vill säga till genomsnittet [8] . $\frac{k}{w+1}$

Låt oss till exempel höja talet x till potensen 215 med hjälp av metoden med skjutfönster . Bredden på fönstret är w = 3.

215 = 27 + 5 24 + 7
y=1
y = y x = x
y kvadreras 3 gånger, eftersom i detta steg e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2, och nedräkningen är från noll, det vill säga y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y kvadreras 4 gånger, eftersom i detta steg e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, det vill säga y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Applikation

Algoritmen för snabb exponentiering har blivit utbredd i kryptosystem med offentliga nyckel . Algoritmen används i synnerhet i RSA- protokollet , ElGamal-schemat och andra kryptografiska algoritmer [11] .

Se även

Anteckningar

↑ Shvets A.N. Snabb exponentiering . Datum för åtkomst: 13 november 2015. Arkiverad från originalet 17 november 2015. (obestämd)
↑ Pankratova, 2009 , sid. 7.
↑ Pankratova, 2009 , sid. elva.
↑ Pankratova, 2009 , sid. tio.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Handbok, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Kryptografi, 2005 .
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Tillämpad kryptografi, 2002 .

Litteratur

Schneier B. Algoritmer med publika nycklar // Tillämpad kryptografi. - Triumph, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. Grunderna i modern kryptografi för specialister inom informationsteknologi - Vetenskaplig värld , 2004. - P. 15. - 173 s. — ISBN 978-5-89176-233-6
Smart N. Algoritmer för exponentiering // Kryptografi . - Moskva: Technosfera, 2005. - S. 287 -292. — 528 sid. - ISBN 5-94836-043-1 .
Makhovenko E. B. Tal -teoretiska metoder i kryptografi - M .: Helios ARV , 2006. - P. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Handbook of Elliptic and Hyperelliptic Curve Cryptography . - Chapman & Hall / CRC, 2006. - S. 145-150 . — 808 sid. — ISBN 1-58488-518-1 .
Pankratova I. A. Talteoretiska metoder för kryptografi - Tomsk : TGU , 2009. - 120 sid.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssäkerhet : lärobok - M .: MIPT , 2011. - P. 230-231. — 225 sid. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Offentliga nyckelalgoritmer // Primtal : Kryptografiska och beräkningsaspekter - M .: URSS , 2011. - P. 514-520. — 663 sid. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2