Rychlé umocňovací algoritmy

Rychlé umocňovací algoritmy ( algoritmus dichotomického umocňování, binární umocňovací algoritmus) jsou algoritmy navržené tak, aby zvýšily číslo na přirozenou mocninu v menším počtu násobení , než je požadováno při určování stupně [1] . Algoritmy jsou založeny na tom, že pro umocnění čísla na mocninu není nutné násobit číslo samo o sobě jednou, ale můžete násobit již vypočítané mocniny. Konkrétně, pokud je mocnina dvou, pak pro zvýšení na mocninu stačí umocnit číslo krát a utrácet násobení místo . Chcete-li například zvýšit číslo na osmou mocninu, můžete místo sedmi násobení odmocnit číslo ( ), pak výsledek znovu odmocnit, abyste získali čtvrtou mocninu ( ), a nakonec výsledek znovu odmocnit a získat odpověď ( ). $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))$

Některé algoritmy pro další optimalizaci navíc využívají toho, že operace kvadratury je rychlejší než operace násobení díky tomu, že se cifry ve faktoru při kvadratuře opakují [2] .

Binární umocňovací algoritmus byl poprvé navržen v 15. století perským matematikem Al-Kashi [3] .

Tyto algoritmy nejsou vždy optimální. Například při použití schématu zleva doprava bude rychlé umocňování n = 15 vyžadovat tři násobení a tři operace umocnění, ačkoli zvýšení na 15. mocninu lze provést ve 3 násobení a 2 umocnění [4] . Optimální umocnění odpovídá konstrukci nejkratšího aditivního řetězce .

Popis

Hlavním algoritmem pro rychlé umocňování je schéma „zleva doprava“. Svůj název získal podle toho, že bity exponentu jsou nahlíženy zleva doprava, tedy od vysokého k nízkému [5] .

Nechat

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

je binární reprezentace stupně n , tj.

n=m_{{k}}\cdot 2^{{k}}+m_{{k-1}}\cdot 2^{{k-1}}+\tečky +m_{{1}}\cdot 2 +m_{{0}},

kde . Pak $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] .

Posloupnost akcí při použití tohoto schématu lze popsat takto:

Představte exponent n v binárním tvaru
Je-li = 1, pak se aktuální výsledek odmocní a poté vynásobí x. Je-li = 0, pak se aktuální výsledek jednoduše odmocní [6] . Index i se mění z k -1 na 0 [7] . $m_i$ $m_i$

Algoritmus rychlého umocňování se tedy redukuje na multiplikativní analog Hornerova schématu [6] :

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

Zobecnění

Nechť je pár ( S , *) pologrupa , pak můžeme operaci nazvat * násobení a definovat operaci zvýšení na přirozenou mocninu:

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

Poté, pro výpočet hodnot a n v jakékoli pologrupě ( zejména v Abelovské grupě ), lze použít algoritmy pro rychlé umocňování [8] .

Příklady řešení problémů

Použitím algoritmu vypočítáme 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}}

Schéma zprava doleva

V tomto schématu, na rozdíl od schématu „zleva doprava“, jsou bity exponentu prohlíženy od nejnižšího k nejvyššímu [5] .

Posloupnost akcí při implementaci tohoto algoritmu.

Vyjádřete exponent n binárně.
Nastavte pomocnou proměnnou z rovnou číslu x.
1. Jestliže , pak se aktuální výsledek vynásobí z a samotné číslo z se umocní na druhou. Je-li = 0, pak stačí odmocnit z [6] . V tomto případě se index i , na rozdíl od schématu zleva doprava, pohybuje od 0 do k -1 včetně [7] . $m_{i}=1$ $m_i$

Tento obvod obsahuje tolik násobení a umocnění jako obvod „zleva doprava“. Navzdory tomu je však schéma zleva doprava výnosnější než schéma zprava doleva, zvláště pokud exponent obsahuje mnoho jednotek. Jde o to, že ve schématu zleva doprava operace výsledek = výsledek · x obsahuje konstantní násobitel x . A pro malé x (což je často případ testů primality) bude násobení rychlé. Například pro x = 2 můžeme operaci násobení nahradit operací sčítání [7] .

Matematické zdůvodnění fungování tohoto algoritmu může být reprezentováno následujícím vzorcem:

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říklad . Vypočítejme hodnotu 21 13 pomocí schématu umocňování zprava doleva .

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

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

Výpočetní složitost

Pro schéma zleva doprava i zprava doleva je počet operací umocnění stejný a rovná se k, kde k je délka exponentu n v bitech, . Počet požadovaných operací násobení se rovná Hammingově váze , tedy počtu nenulových prvků v binární reprezentaci čísla n . V průměru jsou vyžadovány operace násobení [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

Například pro zvýšení čísla na setinu bude tento algoritmus vyžadovat pouze 8 operací násobení a kvadratury [5] .

Pro srovnání u standardní metody umocňování je nutná operace násobení, to znamená, že počet operací lze odhadnout jako [10] . $n-1$ $Na)$

Optimalizace algoritmu

Obecně je operace kvadratury rychlejší než operace násobení. Metoda okna umožňuje snížit počet operací násobení a tím optimalizovat umocňovací algoritmus [8] .

Okno je vlastně základem číselné soustavy [7] . Nechť w je šířka okna, to znamená, že se najednou bere v úvahu w znaků indikátoru.

Zvažte metodu okna.

Pro předem vypočítané x i $i = \overline {0, 2^w-1}$
Exponent je uveden v následujícím tvaru: , kde $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \in {(0, 1, ..., 2^w-1)}$
Nechť y je proměnná, ve které se bude počítat konečný výsledek. Nechte _ $y=x^{n_{k/w}}$
Pro všechna i = k/w - 1, k/w - 2, ..., 0 proveďte následující:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Tento algoritmus vyžaduje k kvadraturu, ale počet násobení je v průměru redukován na k/w [8] .

Ještě efektivnější je metoda posuvného okna. Spočívá ve skutečnosti, že šířka okna se během provádění procesu může změnit:

Exponent je reprezentován jako , kde a 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)}$
Pro x se počítá i . Dále označíme x i jako x i . $i = (1, 3, 5, ..., 2^w-1)$
Nechť y je proměnná, ve které se bude počítat konečný výsledek. Nechte _ $y=x^{n_{l}}$
Pro všechna i = l - 1, l - 2, ..., 0 proveďte následující:
1. Pro všechna j od 0 do e i+1 - e i - 1 y čtverec
2. $j = m_i$
3. $y = y\cdot x_j$
Pro všechna j od 0 do e 0 - 1 y čtverec [8] .

Počet operací umocňování v tomto algoritmu je stejný jako u metody okna, ale počet operací násobení byl snížen na l , tedy na průměr [8] . $\frac{k}{w+1}$

Například pomocí metody posuvného okna zvětšíme číslo x na 215. Šířka okna je w = 3.

215 = 27 + 5 24 + 7
y=1
y = y x = x
y je odmocněno 3krát, protože v tomto kroku e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2 a odpočítávání je od nuly, to znamená y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y je odmocněno 4krát, protože v tomto kroku e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, to znamená y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Aplikace

Rychlý umocňovací algoritmus se rozšířil v kryptosystémech s veřejným klíčem . Algoritmus se používá zejména v protokolu RSA , schématu ElGamal a dalších kryptografických algoritmech [11] .

Viz také

Poznámky

↑ Shvets A.N. Rychlé umocňování . Datum přístupu: 13. listopadu 2015. Archivováno z originálu 17. listopadu 2015. (neurčitý)
↑ Pankratova, 2009 , str. 7.
↑ Pankratova, 2009 , str. jedenáct.
↑ Pankratova, 2009 , str. deset.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Příručka, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Kryptografie, 2005 .
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Aplikovaná kryptografie, 2002 .

Literatura

Schneier B. Algoritmy s veřejnými klíči // Aplikovaná kryptografie. - Triumph, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. Základy moderní kryptografie pro odborníky v oblasti informačních technologií - Vědecký svět , 2004. - S. 15. - 173 s. — ISBN 978-5-89176-233-6
Smart N. Algoritmy pro umocňování // Kryptografie . - Moskva: Technosfera, 2005. - S. 287 -292. — 528 s. - ISBN 5-94836-043-1 .
Makhovenko E. B. Číselné teoretické metody v kryptografii - M .: Helios ARV , 2006. - S. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Handbook of Elliptic and Hypereliptic Curve Cryptography . - Chapman & Hall / CRC, 2006. - S. 145-150 . — 808 str. — ISBN 1-58488-518-1 .
Pankratova I. A. Číselně teoretické metody kryptografie - Tomsk : TGU , 2009. - 120 s.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - S. 230-231. — 225 str. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Algoritmy veřejného klíče // Prvočísla : Kryptografické a výpočetní aspekty - M .: URSS , 2011. - S. 514-520. — 663 s. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2