Algoritmi de exponențiere rapidă

Algoritmii de exponențiere rapidă ( algoritm de exponențiere dihotomică , algoritm de exponențiere binară) sunt algoritmi menționați să ridice un număr la o putere naturală în mai puține înmulțiri decât este necesar în determinarea gradului [1] . Algoritmii se bazează pe faptul că, pentru a ridica un număr la o putere , nu este necesar să înmulțiți numărul cu el însuși o dată, dar puteți înmulți puterile deja calculate. În special, dacă puterea a doi, atunci pentru ridicarea la o putere este suficient să pătrați numărul de ori, în timp ce cheltuiți înmulțiri în loc de $X$ $n$ $X$ $n$ $X$ $n$ $n=2^k$ $n$ $k$ $k$ $2^k$ . De exemplu, pentru a ridica un număr la puterea a opta, în loc să efectuați șapte înmulțiri , puteți pătra numărul ( ), apoi puteți pătra din nou rezultatul pentru a obține a patra putere ( ) și, în cele din urmă, puteți pătra din nou rezultatul și obțineți răspunsul ( ). $X$ $x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x\cdot x$ $x^{2}=x\cdot x$ $x^{4}=x^{2}\cdot x^{2)$ $x^{8}=x^{4}\cdot x^{4)$

În plus, unii algoritmi pentru optimizarea ulterioară folosesc faptul că operația de pătrare este mai rapidă decât operația de înmulțire datorită faptului că cifrele din factor se repetă la pătrat [2] .

Algoritmul de exponențiere binară a fost propus pentru prima dată în secolul al XV-lea de către matematicianul persan Al-Kashi [3] .

Acești algoritmi nu sunt întotdeauna optimi. De exemplu, atunci când se folosește schema de la stânga la dreapta, exponențiarea rapidă a n = 15 va necesita trei înmulțiri și trei operații de pătrare, deși ridicarea la puterea a 15-a poate fi efectuată în 3 înmulțiri și 2 pătrat [4] . Exponentiația optimă corespunde construcției celui mai scurt lanț de aditivi .

Descriere

Algoritmul principal pentru exponențierea rapidă este schema „de la stânga la dreapta”. Își trage numele de la faptul că biții exponentului sunt priviți de la stânga la dreapta, adică de la sus la jos [5] .

Lăsa

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

este o reprezentare binară a gradului n , adică

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

unde . Apoi $m_{{k}}=1,m_{{i}}\în \{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] .

Secvența de acțiuni la utilizarea acestei scheme poate fi descrisă după cum urmează:

Reprezentați exponentul n în formă binară
Dacă = 1, atunci rezultatul curent este pătrat și apoi înmulțit cu x. Dacă = 0, atunci rezultatul curent este pur și simplu pătrat [6] . Indicele i se modifică de la k -1 la 0 [7] . $m_i$ $m_i$

Astfel, algoritmul de exponențiere rapidă se reduce la un analog multiplicativ al schemei lui Horner [6] :

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

Generalizări

Fie perechea ( S , *) un semigrup , atunci putem numi operația * înmulțire și definim operația de ridicare la o putere naturală:

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

Apoi, pentru a calcula valorile unui n în orice semigrup (în special, într- un grup abelian ), se pot folosi algoritmi de exponențiere rapidă [8] .

Exemple de rezolvare a problemelor

Aplicând algoritmul, calculăm 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}}

Schema de la dreapta la stânga

În această schemă, spre deosebire de schema „de la stânga la dreapta”, biții exponentului sunt priviți de la cel mai mic la cel mai mare [5] .

Secvența de acțiuni în implementarea acestui algoritm.

Exprimați exponentul n în binar.
Setați variabila auxiliară z egală cu numărul x.
1. Dacă , atunci rezultatul curent este înmulțit cu z , iar numărul z însuși este pătrat. Dacă = 0, atunci trebuie doar să pătrați z [6] . În acest caz, indicele i , spre deosebire de schema de la stânga la dreapta, variază de la 0 la k -1 inclusiv [7] . $m_{i}=1$ $m_i$

Acest circuit conține tot atâtea înmulțiri și pătrate cât circuitul „de la stânga la dreapta”. Cu toate acestea, în ciuda acestui fapt, schema de la stânga la dreapta este mai profitabilă decât schema de la dreapta la stânga, mai ales dacă exponentul conține multe unități. Ideea este că în schemă, de la stânga la dreapta, rezultatul operației = rezultat · x conține un multiplicator constant x . Și pentru x mic (ceea ce este adesea cazul în testele de primalitate), înmulțirea va fi rapidă. De exemplu, pentru x = 2 putem înlocui operația de înmulțire cu operația de adunare [7] .

Justificarea matematică a funcționării acestui algoritm poate fi reprezentată prin următoarea formulă:

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] .

Exemplu . Să calculăm valoarea 21 13 folosind schema de exponențiere de la dreapta la stânga .

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

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

Complexitate computațională

Atât pentru schemele de la stânga la dreapta, cât și de la dreapta la stânga, numărul de operații la pătrat este același și este egal cu k, unde k este lungimea exponentului n în biți, . Numărul de operații de înmulțire necesare este egal cu greutatea Hamming , adică numărul de elemente nenule din reprezentarea binară a numărului n . În medie, sunt necesare operații de înmulțire [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

De exemplu, pentru a ridica un număr la puterea a suta, acest algoritm va necesita doar 8 operații de înmulțire și pătrare [5] .

Pentru comparație, cu metoda standard de exponențiere, este necesară o operație de înmulțire, adică numărul de operații poate fi estimat ca [10] . $n-1$ $Pe)$

Optimizarea algoritmului

În general, operația de pătrare este mai rapidă decât operația de înmulțire. Metoda ferestrei vă permite să reduceți numărul de operații de înmulțire și, prin urmare, să faceți algoritmul de exponențiere mai optim [8] .

Fereastra este de fapt baza sistemului numeric [7] . Fie w lățimea ferestrei, adică w caracterele indicatorului sunt luate în considerare la un moment dat.

Luați în considerare metoda ferestrei.

Pentru x i precalculat $i = \overline {0, 2^w-1}$
Exponentul este prezentat sub următoarea formă: , unde $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \în {(0, 1, ..., 2^w-1)}$
Fie y variabila în care va fi calculat rezultatul final. Lasă . $y=x^{n_{k/w}}$
Pentru toate i = k/w - 1, k/w - 2, ..., 0, faceți următoarele:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Acest algoritm necesită k pătrat, dar numărul de înmulțiri este redus la k/w în medie [8] .

Și mai eficientă este metoda ferestrei glisante. Constă în faptul că lățimea ferestrei în timpul execuției procesului se poate modifica:

Exponentul este reprezentat ca , unde , și e i+1 — e i ≥ w . $n = \sum_{i=0}^{l}{n_i\cdot2^{e_i}}$ $n_i \în {(1, 3, 5, ..., 2^w-1)}$
Pentru x i se calculează . Mai departe vom desemna x i ca x i . $i = (1, 3, 5, ..., 2^w-1)$
Fie y variabila în care va fi calculat rezultatul final. Lasă . $y=x^{n_{l}}$
Pentru toate i = l - 1, l - 2, ..., 0 faceți următoarele:
1. Pentru toate j de la 0 la e i+1 - e i - 1 y pătrat
2. $j = m_i$
3. $y = y\cdot x_j$
Pentru toate j de la 0 la e 0 - 1 y pătrat [8] .

Numărul de operații de exponențiere din acest algoritm este același ca în metoda ferestrei, dar numărul de operații de înmulțire a fost redus la l , adică la media [8] . $\frac{k}{w+1}$

De exemplu, să ridicăm numărul x la puterea lui 215 folosind metoda ferestrei glisante . Lățimea ferestrei este w = 3.

215 = 27 + 5 24 + 7
y=1
y = y x = x
y este pătrat de 3 ori, deoarece la acest pas e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2, iar numărătoarea inversă este de la zero, adică y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y este pătrat de 4 ori, deoarece la acest pas e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, adică y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Aplicație

Algoritmul de exponențiere rapidă a devenit larg răspândit în criptosistemele cu cheie publică . În special, algoritmul este utilizat în protocolul RSA , schema ElGamal și alți algoritmi criptografici [11] .

Vezi și

Note

↑ Shvets A.N. Fast exponentiation . Data accesului: 13 noiembrie 2015. Arhivat din original pe 17 noiembrie 2015. (nedefinit)
↑ Pankratova, 2009 , p. 7.
↑ Pankratova, 2009 , p. unsprezece.
↑ Pankratova, 2009 , p. zece.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Manual, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Criptografie, 2005 .
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Criptografie aplicată, 2002 .

Literatură

Schneier B. Algoritmi cu chei publice // Criptografie aplicată. - Triumf, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. Fundamentele criptografiei moderne pentru specialiști în tehnologia informației - Lumea științifică , 2004. - P. 15. - 173 p. — ISBN 978-5-89176-233-6
Smart N. Algoritmi pentru exponentiare // Criptografie . - Moscova: Technosfera, 2005. - S. 287 -292. — 528 p. - ISBN 5-94836-043-1 .
Makhovenko E. B. Metode teoretice numerice în criptografie - M .: Helios ARV , 2006. - P. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Manual de criptografie cu curbe eliptice și hipereliptice . - Chapman & Hall / CRC, 2006. - P. 145-150 . — 808 p. — ISBN 1-58488-518-1 .
Pankratova I. A. Metode teoretice numerice ale criptografiei - Tomsk : TGU , 2009. - 120 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - P. 230-231. — 225 p. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Public key algorithms // Prime numbers : Cryptographic and computational aspects - M .: URSS , 2011. - P. 514-520. — 663 p. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2