Nopeat eksponentioalgoritmit

Nopeat eksponentioalgoritmit ( dikotominen eksponentioalgoritmi, binäärinen eksponentioalgoritmi) ovat algoritmeja , jotka on suunniteltu nostamaan luku luonnolliseen potenssiin harvemmalla kertolaskulla kuin asteen määrittämisessä vaaditaan [1] . Algoritmit perustuvat siihen, että luvun nostamiseksi potenssiin , lukua ei tarvitse kertoa itsellään kerran, vaan jo lasketut potenssit voidaan kertoa. Erityisesti, jos potenssi on kaksi, niin potenssiin nostamiseen riittää lukukertojen neliöinti, samalla kun kulutetaan kertolaskuja . Esimerkiksi, jos haluat nostaa luvun kahdeksanteen potenssiin seitsemän kertokertoimen suorittamisen sijaan , voit neliöttää luvun ( ), sitten neliöidä tuloksen uudelleen saadaksesi neljännen potenssin ( ) ja lopuksi neliöimällä tuloksen uudelleen ja saat vastauksen ( ). $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))$

Lisäksi jotkin algoritmit lisäoptimointiin käyttävät sitä tosiasiaa, että neliöintioperaatio on nopeampi kuin kertolasku, koska kertoimen numerot toistuvat neliöitäessä [2] .

Persialainen matemaatikko Al-Kashi [3] ehdotti ensimmäisen kerran binaarista eksponentiointialgoritmia 1400-luvulla .

Nämä algoritmit eivät aina ole optimaalisia. Esimerkiksi käytettäessä vasemmalta oikealle -mallia n = 15:n nopea eksponentio vaatii kolme kertolaskua ja kolme neliöintioperaatiota, vaikka korotus 15. potenssiin voidaan suorittaa kolmella kertolaskulla ja kahdella neliöinnillä [4] . Optimaalinen eksponentio vastaa lyhimmän lisäaineketjun rakennetta .

Kuvaus

Pääalgoritmi nopealle eksponentiolle on "vasemmalta oikealle" -malli. Se on saanut nimensä siitä, että eksponentin bittejä tarkastellaan vasemmalta oikealle, eli korkeasta matalaan [5] .

Päästää

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

on asteen n binääriesitys , eli

n=m_{{k}}\cpiste 2^{{k}}+m_{{k-1}}\cpiste 2^{{k-1}}+\pisteet +m_{{1}}\cpiste 2 +m_{{0}},

missä . Sitten $m_{{k}}=1,m_{{i}}\in \{0,1\}$

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

[5] .

Toimintojen järjestys tätä järjestelmää käytettäessä voidaan kuvata seuraavasti:

Esitä eksponentti n binäärimuodossa
Jos = 1, nykyinen tulos neliöidään ja kerrotaan sitten x:llä. Jos = 0, niin nykyinen tulos yksinkertaisesti neliötetään [6] . Indeksi i muuttuu arvosta k -1 arvoon 0 [7] . $mi$ $mi$

Siten nopea eksponentioalgoritmi pelkistyy Hornerin kaavion [6] multiplikatiiviseksi analogiksi :

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

Yleistykset

Olkoon pari ( S , *) puoliryhmä , jolloin voidaan kutsua operaatiota * kertolasku ja määritellä nostooperaatio luonnolliseen potenssiin:

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

Sitten n:n arvojen laskemiseksi missä tahansa puoliryhmässä ( erityisesti Abelin ryhmässä ) voidaan käyttää algoritmeja nopeaan eksponentioon [8] .

Esimerkkejä ongelmanratkaisusta

Algoritmia soveltaen laskemme 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}\cpiste 21^{0})^{2}\cpiste 21^{1}\\&=(((1\cpiste 21)^{2}\cpiste 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}}

Oikealta vasemmalle -kaavio

Tässä mallissa, toisin kuin "vasemmalta oikealle" -mallissa, eksponentin bittejä tarkastellaan alimmasta korkeimpaan [5] .

Toimintojen järjestys tämän algoritmin toteutuksessa.

Ilmaise eksponentti n binäärimuodossa.
Aseta apumuuttuja z yhtä suureksi kuin luku x.
1. Jos , niin nykyinen tulos kerrotaan z :llä ja itse luku z neliötetään. Jos = 0, sinun tarvitsee vain neliöttää z [6] . Tässä tapauksessa indeksi i , toisin kuin kaaviossa vasemmalta oikealle, vaihtelee välillä 0 - k -1 mukaan lukien [7] . $m_{i}=1$ $mi$

Tämä piiri sisältää yhtä monta kertolaskua ja neliöintiä kuin "vasemmalta oikealle" -piiri. Tästä huolimatta vasemmalta oikealle -kaavio on kuitenkin kannattavampi kuin oikealta vasemmalle -malli, varsinkin jos eksponentti sisältää useita yksiköitä. Asia on siinä, että kaaviossa vasemmalta oikealle operaation tulos = tulos · x sisältää vakiokertoimen x . Ja pienelle x :lle (joka usein tapahtuu primaliteettitesteissä) kertominen on nopeaa. Esimerkiksi, kun x = 2, voimme korvata kertolaskuoperaation summausoperaatiolla [7] .

Tämän algoritmin toiminnan matemaattinen perustelu voidaan esittää seuraavalla kaavalla:

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

Esimerkki . Lasketaan arvo 21 13 käyttäen eksponentiokaaviota oikealta vasemmalle .

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

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

Laskennallinen monimutkaisuus

Sekä vasemmalta oikealle että oikealta vasemmalle -mallissa neliöintioperaatioiden lukumäärä on sama ja yhtä suuri kuin k, missä k on eksponentin n pituus bitteinä, . Vaadittujen kertolaskuoperaatioiden määrä on yhtä suuri kuin Hamming -paino , eli nollasta poikkeavien alkioiden lukumäärä luvun n binääriesityksessä . Keskimäärin kertolaskuja tarvitaan [6] . $k \sim \ln{n}$ $\frac{1}{2}\cdot\ln{n}$

Esimerkiksi luvun nostamiseksi sadasosaan tämä algoritmi vaatii vain 8 kerto- ja neliöintioperaatiota [5] .

Vertailun vuoksi standardin eksponentiomenetelmän kanssa tarvitaan kertolasku, eli operaatioiden lukumäärä voidaan arvioida [10] . $n-1$ $Päällä)$

Algoritmin optimointi

Yleensä neliöintioperaatio on nopeampi kuin kertolasku. Ikkunamenetelmän avulla voit vähentää kertolaskujen määrää ja tehdä siten eksponentioalgoritmista optimaalisemmaksi [8] .

Ikkuna on itse asiassa numerojärjestelmän perusta [7] . Olkoon w ikkunan leveys, eli indikaattorin w merkkiä otetaan huomioon kerrallaan.

Harkitse ikkunamenetelmää.

Ennalta lasketulle x i : lle $i = \overline {0, 2^w-1}$
Eksponentti esitetään seuraavassa muodossa: , missä $n = \sum_{i=0}^{k/w}{n_i\cdot2^{i\cdot w}}$ $n_i \in {(0, 1, ..., 2^w-1)}$
Olkoon y muuttuja, josta lopullinen tulos lasketaan. Anna . $y=x^{n_{k/w}}$
Kaikille i = k/w - 1, k/w - 2, ..., 0, toimi seuraavasti:
1. $y = y^{2^w}$
2. $y = y\cdot x^{n_i}$ [8] .

Tämä algoritmi vaatii k -neliöinnin, mutta kertolaskujen lukumäärä pienenee keskimäärin k/w :iin [8] .

Vielä tehokkaampi on liukuikkunamenetelmä. Se johtuu siitä, että ikkunan leveys voi muuttua prosessin aikana:

Eksponentti esitetään muodossa , missä ja 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)}$
Arvolle x i lasketaan . Lisäksi nimeämme x i :ksi x i . $i = (1, 3, 5, ..., 2^w-1)$
Olkoon y muuttuja, josta lopullinen tulos lasketaan. Anna . $y=x^{n_{l}}$
Kaikille i = l - 1, l - 2, ..., 0 toimi seuraavasti:
1. Kaikille j:lle 0 - e i+1 - e i - 1 y neliö
2. $j = m_i$
3. $y = y\cdot x_j$
Kaikille j :lle 0 - e 0 - 1 y -neliö [8] .

Eksponenttioperaatioiden määrä tässä algoritmissa on sama kuin ikkunamenetelmässä, mutta kertolaskuoperaatioiden määrä on vähennetty l :ään eli keskiarvoon [8] . $\frac{k}{w+1}$

Nostetaan esimerkiksi luku x potenssiin 215 liukuvalla ikkunamenetelmällä . Ikkunan leveys on w = 3.

215 = 27 + 5 24 + 7
y = 1
y = y x = x
y on neliöity 3 kertaa, koska tässä vaiheessa e 2 - e 1 -1 \u003d 7 - 4 - 1 \u003d 2, ja lähtölaskenta on nollasta, eli y \u003d y 8 \u003d x 8
y \u003d y x 5 \u003d x 13
y on neliöity 4 kertaa, koska tässä vaiheessa e 1 - e 0 -1 \u003d 4 - 0 - 1 \u003d 3, eli y \u003d y 16 \u003d x 208
y \u003d y x 7 \u003d x 215

Sovellus

Nopea eksponentioalgoritmi on yleistynyt julkisen avaimen salausjärjestelmissä . Algoritmia käytetään erityisesti RSA -protokollassa , ElGamal-skeemassa ja muissa salausalgoritmeissa [11] .

Katso myös

Muistiinpanot

↑ Shvets A.N. Nopea eksponentio . Käyttöpäivä: 13. marraskuuta 2015. Arkistoitu alkuperäisestä 17. marraskuuta 2015. (määrätön)
↑ Pankratova, 2009 , s. 7.
↑ Pankratova, 2009 , s. yksitoista.
↑ Pankratova, 2009 , s. kymmenen.
↑ 1 2 3 4 Ryabko, Fionov, 2004 .
↑ 1 2 3 4 Käsikirja, 2006 .
↑ 1 2 3 4 Crandall, Pomerance, 2011 .
↑ 1 2 3 4 5 6 Kryptografia, 2005 .
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Mahovenko, 2006 .
↑ Applied Cryptography, 2002 .

Kirjallisuus

Schneier B. Algoritmit julkisilla avaimilla // Applied Cryptography. - Triumph, 2002. - ISBN 5-89392-055-4 .
Ryabko B. Ya. , Fionov A. N. Modernin salauksen perusteet tietotekniikan asiantuntijoille - Tieteellinen maailma , 2004. - S. 15. - 173 s. — ISBN 978-5-89176-233-6
Smart N. Eksponentioinnin algoritmit // Kryptografia . - Moskova: Technosfera, 2005. - S. 287 -292. — 528 s. - ISBN 5-94836-043-1 .
Makhovenko E. B. Numeroteoreettiset menetelmät kryptografiassa - M .: Helios ARV , 2006. - P. 154-155. — ISBN 978-5-85438-143-7
Cohen H., Frei G. Elliptisen ja hyperelliptisen käyrän kryptografian käsikirja . - Chapman & Hall / CRC, 2006. - S. 145-150 . — 808 s. — ISBN 1-58488-518-1 .
Pankratova I. A. Krypografian lukuteoreettiset menetelmät - Tomsk : TGU , 2009. - 120 s.
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Tietoturva : oppikirja - M .: MIPT , 2011. - P. 230-231. - 225 s. — ISBN 978-5-7417-0377-9
Crandall R. , Pomerance K. Julkisen avaimen algoritmit // Alkuluvut : kryptografiset ja laskennalliset näkökohdat - M .: URSS , 2011. - P. 514-520. — 663 s. — ISBN 978-5-453-00016-6 , 978-5-397-02060-2