Gyors hatványozási algoritmusok

A gyors hatványozási algoritmusok ( dichotóm hatványozási algoritmus, bináris hatványozási algoritmus) olyan algoritmusok , amelyeket arra terveztek, hogy egy számot természetes hatványra emeljenek a fok meghatározásához szükségesnél kevesebb szorzásban [1] . Az algoritmusok azon a tényen alapulnak, hogy egy szám hatványra emeléséhez nem szükséges a számot egyszer megszorozni önmagával , hanem meg lehet szorozni a már kiszámított hatványokat. Különösen, ha kettő hatványa, akkor hatványra emeléshez elegendő a számszorok négyzetre emelése, miközben szorzásokat költünk helyette . Például egy szám nyolcadik hatványra emeléséhez hét szorzás elvégzése helyett négyzetezheti a számot ( ), majd ismét négyzetre emelheti az eredményt, hogy megkapja a negyedik hatványt ( ), végül ismét négyzetre emelje az eredményt, és megkapja a választ ( ). $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$ $x^{4}=x^{2}\cdot x^{2}$ $x^{8}=x^{4}\cdot x^{4}$

Ezen túlmenően egyes további optimalizálás algoritmusok azt a tényt használják fel, hogy a négyzetesítési művelet gyorsabb, mint a szorzás, mivel a faktor számjegyei négyzetre emeléskor ismétlődnek [2] .

A bináris hatványozási algoritmust először a 15. században Al-Kashi perzsa matematikus javasolta [3] .

Ezek az algoritmusok nem mindig optimálisak. Például a balról jobbra haladó séma használatakor n = 15 gyors hatványozása három szorzást és három négyzetesítési műveletet igényel, bár a 15. hatványra emelés 3 szorzással és 2 négyzetesítéssel is végrehajtható [4] . Az optimális hatványozás a legrövidebb adaléklánc felépítésének felel meg .

Leírás

A gyors hatványozás fő algoritmusa a „balról jobbra” séma. Nevét onnan kapta, hogy a kitevő bitjeit balról jobbra, azaz magasról alacsonyra nézzük [5] .

Hadd

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

az n fok bináris reprezentációja , azaz

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

ahol . Akkor $m_{{k}}=1,m_{{i}}\in \{0,1\}$

x^{n}=x^{((\pontok((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}\pontok)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}

[5] .

A séma használatakor a műveletek sorrendje a következőképpen írható le:

Az n kitevőt bináris formában ábrázolja
Ha = 1, akkor az aktuális eredményt négyzetre emeljük, majd megszorozzuk x-szel. Ha = 0, akkor az aktuális eredményt egyszerűen négyzetre emeljük [6] . Az i index k -1-ről 0 -ra változik [7] . $m_i$ $m_i$

Így a gyors hatványozási algoritmus a Horner-séma [6] multiplikatív analógjává redukálódik :

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

Általánosítások

Legyen az ( S , *) pár félcsoport , akkor a * műveletet hívhatjuk szorzásnak és definiálhatjuk a természetes hatványra emelés műveletét:

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

Ezután egy n értékének kiszámításához bármely félcsoportban ( különösen egy Abel-csoportban ) használhatunk algoritmusokat a gyors hatványozáshoz [8] .

Példák problémamegoldásra

Az algoritmus alkalmazásával 21 13 kiszámítjuk :

{\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}}

Jobbról balra haladó séma

Ebben a sémában a "balról jobbra" sémától eltérően a kitevő bitjeit a legalacsonyabbtól a legmagasabbig tekintjük [5] .

A műveletek sorrendje ennek az algoritmusnak a megvalósításában.

Fejezd ki az n kitevőt binárisan!
Állítsa a z segédváltozót egyenlőnek az x számmal.
1. Ha , akkor az aktuális eredményt megszorozzuk z -vel , és magát a z számot négyzetre emeljük. Ha = 0, akkor csak z négyzetre kell emelni [6] . Ebben az esetben az i index a balról jobbra haladó sémától eltérően 0 és k -1 között változik [7] . $m_{i}=1$ $m_i$

Ez az áramkör annyi szorzást és négyzetesítést tartalmaz, mint a "balról jobbra" áramkör. Ennek ellenére azonban a balról jobbra haladó séma jövedelmezőbb, mint a jobbról balra haladó séma, különösen, ha a kitevő sok egységet tartalmaz. A lényeg az, hogy a sémában balról jobbra az eredmény = eredmény · x egy x konstans szorzót tartalmaz . És kis x esetén (ami gyakran előfordul az elsődlegességi tesztekben) a szorzás gyors lesz. Például x = 2 esetén a szorzási műveletet helyettesíthetjük az összeadás művelettel [7] .

Az algoritmus működésének matematikai indoklása a következő képlettel ábrázolható:

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

Példa . Számítsuk ki a 21 13 értéket a jobbról balra haladó hatványozási séma segítségével .

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

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

Számítási összetettség

Mind a balról jobbra, mind a jobbról balra sémában a négyzetre emelési műveletek száma azonos és egyenlő k-val, ahol k az n kitevő hossza bitekben, . A szükséges szorzási műveletek száma megegyezik a Hamming -súllyal, vagyis az n szám bináris reprezentációjában szereplő nem nulla elemek számával . Átlagosan szorzási műveletekre van szükség [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

Például egy szám századik hatványra emeléséhez ehhez az algoritmushoz mindössze 8 szorzási és négyzetes műveletre lesz szükség [5] .

Összehasonlításképpen a szabványos hatványozási módszerrel szorzási művelet szükséges, vagyis a műveletek száma [10] -re becsülhető . $n-1$ $Tovább)$

Algoritmus optimalizálás

Általában a négyzetesítési művelet gyorsabb, mint a szorzás. Az ablak módszer lehetővé teszi a szorzási műveletek számának csökkentését, és ezáltal a hatványozási algoritmus optimálisabbá tételét [8] .

Az ablak tulajdonképpen a számrendszer alapja [7] . Legyen w az ablak szélessége, azaz a mutató w karakterét veszik figyelembe egyszerre.

Fontolja meg az ablak módszerét.

Az előre kiszámított x i -hez $i = \overline {0, 2^w-1}$
A kitevő a következő formában jelenik meg: , ahol $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \in {(0, 1, ..., 2^w-1)}$
Legyen y az a változó, amelyben a végeredményt kiszámítjuk. Hadd . $y=x^{n_{k/w}}$
Minden i = k/w - 1, k/w - 2, ..., 0 esetén tegye a következőket:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Ez az algoritmus k négyzetesítést igényel, de a szorzások száma átlagosan k/w -ra csökken [8] .

Még hatékonyabb a tolóablak módszer. Ez abban rejlik, hogy az ablak szélessége a folyamat végrehajtása során változhat:

A kitevőt a következőképpen ábrázoljuk: , ahol , és 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)}$
x -re i számítódik ki . A továbbiakban x i -t x i -ként jelöljük . $i = (1, 3, 5, ..., 2^w-1)$
Legyen y az a változó, amelyben a végeredményt kiszámítjuk. Hadd . $y=x^{n_{l}}$
Minden i = l - 1, l - 2, ..., 0 esetén tegye a következőket:
1. Minden j-re 0-tól e -ig i+1 - e i - 1 y négyzet
2. $j = m_i$
3. $y = y\cdot x_j$
Minden j -re 0-tól e - ig 0-1 y négyzet [8] .

A hatványozási műveletek száma ebben az algoritmusban megegyezik az ablakos módszerrel, de a szorzási műveletek száma l -re , azaz átlagosra csökkent [8] . $\frac{k}{w+1}$

Például emeljük az x számot 215 hatványára a csúszóablak módszerrel Az ablak szélessége w = 3.

215 = 27 + 5 24 + 7
y=1
y = y x = x
y 3-szoros négyzet, mivel ebben a lépésben e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2, és a visszaszámlálás nullától történik, azaz y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y négyszeres négyzet, mivel ebben a lépésben e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, azaz y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Alkalmazás

A gyors hatványozási algoritmus széles körben elterjedt a nyilvános kulcsú kriptorendszerekben . Az algoritmust különösen az RSA protokollban , az ElGamal sémában és más kriptográfiai algoritmusokban használják [11] .

Lásd még

Jegyzetek

↑ Shvets A.N. Gyors hatványozás . Hozzáférés időpontja: 2015. november 13. Az eredetiből archiválva : 2015. november 17. (határozatlan)
↑ Pankratova, 2009 , p. 7.
↑ Pankratova, 2009 , p. tizenegy.
↑ Pankratova, 2009 , p. tíz.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Kézikönyv, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Kriptográfia, 2005 .
↑ Gabidulin, Ksevetszkij, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Alkalmazott kriptográfia, 2002 .

Irodalom

Schneier B. Algoritmusok nyilvános kulcsokkal // Alkalmazott kriptográfia. - Triumph, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. A modern kriptográfia alapjai informatikai szakemberek számára - Tudományos világ , 2004. - 15. o. - 173 p. — ISBN 978-5-89176-233-6
Smart N. Hatványozási algoritmusok // Kriptográfia . - Moszkva: Technosfera, 2005. - S. 287 -292 . — 528 p. - ISBN 5-94836-043-1 .
Makhovenko E. B. Számelméleti módszerek a kriptográfiában - M .: Helios ARV , 2006. - P. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Az elliptikus és hiperelliptikus görbe kriptográfia kézikönyve . - Chapman & Hall / CRC, 2006. - P. 145-150 . — 808 p. — ISBN 1-58488-518-1 .
Pankratova I. A. A kriptográfia számelméleti módszerei - Tomszk : TGU , 2009. - 120 p.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Információbiztonság : tankönyv - M .: MIPT , 2011. - P. 230-231. — 225 p. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Nyilvános kulcsú algoritmusok // Prímszámok : Kriptográfiai és számítási szempontok - M .: URSS , 2011. - P. 514-520. — 663 p. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2