Diskreetti logaritmi

Diskreetti logaritmi (DLOG) on funktion invertointiongelma jossakin äärellisessä kertovassa ryhmässä . $g^{x}$ $G$

Useimmiten diskreetti logaritmiongelmaa tarkastellaan jäännösrenkaan tai äärellisen kentän multiplikatiivisessa ryhmässä sekä äärellisen kentän yli olevan elliptisen käyrän pisteiden ryhmässä . Tehokkaita algoritmeja diskreetin logaritmiongelman ratkaisemiseksi ei yleensä tunneta.

Annetuilla g :llä ja a : lla yhtälön ratkaisua x kutsutaan alkion a diskreetiksi logaritmiksi kannassa g . Siinä tapauksessa, että G on jäännösrenkaan modulo m kertova ryhmä , ratkaisua kutsutaan myös luvun a indeksiksi kantaan g nähden . Indeksi a :sta kantaan g on taattu olemassa, jos g on primitiivinen juurimoduuli m . $g^{x}=a$

Ongelman selvitys

Annetaan jollekin äärelliselle multiplikatiiviselle Abelin ryhmälle yhtälö $G$

g^x=a

(yksi)

Diskreetin logaritmin ongelman ratkaisu on löytää jokin ei-negatiivinen kokonaisluku , joka täyttää yhtälön (1). Jos se on ratkaistavissa, siinä tulee olla vähintään yksi luonnollinen ratkaisu, joka ei ylitä ryhmän järjestystä. Tämä antaa välittömästi karkean arvion ratkaisuhakualgoritmin monimutkaisuudesta ylhäältä katsottuna - tyhjentävä hakualgoritmi löytäisi ratkaisun useissa vaiheissa, jotka eivät ylitä annetun ryhmän järjestystä. $x$

Useimmiten tarkastellaan tapausta , jossa , eli ryhmä on elementin generoima syklinen . Tässä tapauksessa yhtälöllä on aina ratkaisu. Mielivaltaisen ryhmän tapauksessa kysymys diskreetin logaritmiongelman ratkaistavuudesta, eli kysymys yhtälön (1) ratkaisujen olemassaolosta, vaatii erillistä pohdintaa. $G=\langle g\rangle$ $g$

Esimerkki

Tarkastellaan diskreetin logaritmin ongelmaa jäännösrenkaassa modo a alkuluku. Esitetään vertailu

3^x\equiv 13\pmod{17}.

Ratkaisemme ongelman luetteloimalla . Kirjoitetaan taulukko luvun 3 kaikista potenssiista. Laskemme joka kerta 17:llä jaon jäännöksen (esimerkiksi 3 3 ≡ 27 - 17:llä jaon jäännös on 10).

3 1 ≡ 3	3 2 ≡ 9	3 3 ≡ 10	3 4 ≡ 13	3 5 ≡ 5	3 6 ≡ 15	3 7 ≡ 11	3 8 ≡ 16
3 9 ≡ 14	3 10 ≡ 8	3 11 ≡ 7	3 12 ≡ 4	3 13 ≡ 12	3 14 ≡ 2	3 15 ≡ 6	3 16 ≡ 1

Nyt on helppo nähdä, että tarkasteltavana olevan vertailun ratkaisu on x=4 , koska 3 4 ≡13.

Käytännössä moduuli on yleensä melko suuri ja laskentamenetelmä liian hidas, joten nopeampia algoritmeja tarvitaan.

Ratkaisualgoritmit

Mielivaltaisessa kertovassa ryhmässä

J. Buchmannin, MJ Jacobsonin ja E. Tesken artikkeli on omistettu diskreetin logaritmiongelman ratkaistavuudelle ja ratkaisulle mielivaltaisessa äärellisessä Abelin ryhmässä. [1] Algoritmi käyttää alkiopareista koostuvaa taulukkoa ja suorittaa kertolaskuja. Tämä algoritmi on hidas eikä sovellu käytännön käyttöön. Tietyille ryhmille on olemassa omat, tehokkaammat algoritminsa. $O(\sqrt{|\langle g\rangle|})$ $O(\sqrt{|\langle g\rangle|})$

Jäännösrenkaassa modulo prime

Harkitse vertailua

a^{x}\equiv b{\pmod {p)),

(2)

missä on alkuluku ja se ei ole jaollinen ilman jäännöstä. Jos on ryhmän generoiva elementti , yhtälöllä (2) on ratkaisu mille tahansa . Tällaisia lukuja kutsutaan myös primitiivisiksi juuriksi , ja niiden lukumäärä on , missä on Euler-funktio . Yhtälön (2) ratkaisu löytyy kaavasta: $s$ $b$ $s$ $a$ $\mathbb{Z}/p\mathbb{Z}$ $b$ $a$ $\phi (p-1)$ $\phi$

x\equiv\sum\limits_{i=1}^{p-2}(1-a^i)^{-1}b^i\pmod{p}.

Tämän kaavan laskemisen monimutkaisuus on kuitenkin pahempi kuin laskennan monimutkaisuus.

Seuraava algoritmi on monimutkainen . $O(\sqrt{p}\cdot\log{p})$

Algoritmi

Määritä $H:=\left\lfloor \sqrt{p}\right\rfloor + 1$
Laskea $c= a^H\bmod{p}$
Luo arvotaulukko ja lajittele se. $c^u\bmod{p}$ $1\leq u\leq H$
Luo arvotaulukko ja lajittele se. $b\cdot a^v\bmod{p}$ $0\leq v\leq H$
Etsi yleisiä elementtejä taulukoista. Heille missä $c^u\equiv b\cdot a^v\pmod{p},$ $a^{Hu-v}\equiv b\pmod{p}.$
Ongelma . $Huv$

On myös monia muita algoritmeja diskreetin logaritmin ongelman ratkaisemiseksi jäännöskentässä. Ne jaetaan yleensä eksponentiaalisiin ja osaeksponentiaalisiin. Polynomialgoritmia tämän ongelman ratkaisemiseksi ei vielä ole olemassa.

Algoritmit, joiden monimutkaisuus on eksponentiaalista

Shanksin algoritmi ( suuren ja pienen askeleen algoritmi , baby-step jättiläisaskel )
Polyg-Hellman-algoritmi - toimii, jos luvun hajoaminen alkutekijöiksi tiedetään. Vaikeusaste :. Jos tekijät, joihin jaetaan , ovat riittävän pieniä, niin algoritmi on erittäin tehokas [2] . $p-1=\prod\limits_{i=1}^{s}q_i^{\alpha_i}$ $O(\sum\limits_{i=1}^{s}\alpha_i(\log{p}+q_i))$ $p-1$
Pollardin ρ-menetelmällä on heuristinen kompleksisuusestimaatti [3] . $O(p^{\frac{1}{2)))$

Subeksponentiaaliset algoritmit

L - notaatiossa näiden algoritmien laskennallinen monimutkaisuus arvioidaan aritmeettisina operaatioina, joissa ja ovat joitakin vakioita. Algoritmin tehokkuus riippuu suurelta osin arvojen ja 1:n ja 0:n läheisyydestä. $L_{p}[d,c]$ $c$ $0\leq d<1$ $c$ $d$

Adlemanin algoritmi ilmestyi vuonna 1979 [4] . Se oli ensimmäinen osaeksponentiaalinen diskreetti logaritmi-algoritmi. Käytännössä se ei kuitenkaan ole kovin tehokasta. tässä algoritmissa . $d=\frac{1}{2}$
COS-algoritmia ehdottivat vuonna 1986 matemaatikot Don Coppersmith, Andrew Odlyzko ja Schroeppel [ 5 ] . Tässä algoritmissa vakio , . Vuonna 1991 modulologaritmi suoritettiin tällä menetelmällä . Vuonna 1997 Weber teki modulo diskreetin logaritmin käyttämällä jotakin tämän algoritmin versiota. On kokeellisesti osoitettu , että COS-algoritmi on parempi kuin lukukentän seula. $c = 1$ $d=\frac{1}{2}$ $p \noin 10^{58}$ $p \noin 10^{85}$ $p \leq 10^{90}$
Diskreetti logaritmi lukukenttäseulan avulla sovellettiin diskreettiin logaritmiin myöhemmin kuin lukujen tekijöihin jakamiseen. Ensimmäiset ideat ilmestyivät 1990-luvulla. D. Gordonin vuonna 1993 ehdottama algoritmi oli heuristinen monimutkaisuus [6] , mutta se osoittautui melko epäkäytännölliseksi. Myöhemmin tähän algoritmiin ehdotettiin monia erilaisia parannuksia. On osoitettu, että seulalla numerokenttä on nopeampi kuin COS. Nykyaikaiset diskreetin logaritmin tietueet saadaan tällä menetelmällä. $L_{p}\left[{\tfrac {1}{3)),3^{3/2}\right]$ $p \geq 10^{100}$

Parhaat parametrit kompleksisuuden arvioinnissa tällä hetkellä ovat , [7] . $c=(92+26{\sqrt {13)))^{\frac {1}{3}}/3\noin 1{,}902$ $d=\frac{1}{3}$

Erikoislukujen tulosta voidaan parantaa. Joissakin tapauksissa on mahdollista rakentaa algoritmi, jonka vakiot ovat , . Koska vakio on tarpeeksi lähellä 1:tä, tällaiset algoritmit voivat ohittaa algoritmin . $c\approx 1{,}00475$ $d=\frac{2}{5}$ $c$ $d=\frac{1}{3}$

Mielivaltaisessa äärellisessä kentässä

Ongelmaa tarkastellaan kentässä GF(q) , jossa , on yksinkertainen. $q=p^{n}$ $s$

Indeksin laskenta-algoritmi ( index-calculus ) on tehokas, jos se on pieni. Tässä tapauksessa sillä on heuristinen monimutkaisuusarvio . $s$ $L_{p}\left[{\tfrac {1}{2}},c\right]$
ElGamal-algoritmi , joka ilmestyi vuonna 1985, soveltuu aritmeettisiin operaatioihin ja sillä on monimutkaisuus . $n = 2$ $L_{p}\left[{\tfrac {1}{2}},c\right]$
Coppersmithin algoritmista diskreetille logaritmille ominaisuuden 2 äärellisessä kentässä tuli ensimmäinen subeksponentiaalinen diskreetti logaritmi , jonka kompleksisuusestimaatin vakio on . Tämä algoritmi ilmestyi vuonna 1984 - ennen numerokenttäseulan keksintöä [8] . $d=\frac{1}{3}$ $L_{p}[d,c]$

Pisteryhmässä elliptisellä käyrällä

Tarkastellaan äärellisen kentän elliptisen käyrän pisteiden ryhmää . Tämä ryhmä määrittelee kahden pisteen lisäämisen. Sitten on tämä . Diskreetin logaritmin ongelman ratkaisu elliptisellä käyrällä on löytää sellainen luonnollinen luku , joka tietyille pisteille ja $sp$ $\alleviiva{P+\ldots+P}\limits_{m}$ $m$ $mP = A$ $P$ $A.$

Vuoteen 1990 asti ei ollut diskreettejä logaritmialgoritmeja, jotka ottaisivat huomioon pisteryhmän rakenteelliset piirteet elliptisellä käyrällä. Myöhemmin Alfred Menezes , Tatsuaki Okamoto ja Scott Vanstone ehdottivat algoritmia käyttämällä Weil -paria [9] . Kentälle määritellylle elliptiselle käyrälle tämä algoritmi vähentää diskreetin logaritmin ongelman samanlaiseksi kentän ongelmaksi . Tämä vähennys on kuitenkin hyödyllinen vain, jos tutkinto on pieni. Tämä ehto täyttyy pääasiassa supersingulaaristen elliptisten käyrien kohdalla. Muissa tapauksissa tällainen vähennys ei juuri koskaan johda subeksponentiaalisiin algoritmeihin. $GF(q)$ $GF(q^k)$ $k$

Laskennallinen monimutkaisuus ja sovellukset kryptografiassa

Diskreetin logaritmin ongelma on yksi tärkeimmistä ongelmista, joihin julkisen avaimen salaus perustuu . Klassiset siihen perustuvat salausmenetelmät ovat Diffie-Hellmanin yhteisavaimen generointijärjestelmä [10] , ElGamal sähköinen allekirjoitusjärjestelmä [11] [12] , Massey-Omura salausjärjestelmä [13] viestien siirtoon. Niiden kryptografinen vahvuus perustuu oletettavasti korkeaan laskennalliseen monimutkaisuuteen eksponentiaalisen funktion kääntämisessä. Vaikka itse eksponentiaalinen funktio lasketaan varsin tehokkaasti, jopa moderneimmilla diskreetin logaritmin laskentaalgoritmeilla on erittäin suuri monimutkaisuus, mikä on verrattavissa nopeimpien faktorointialgoritmien monimutkaisuuteen .

Toinen mahdollisuus ratkaista diskreetin logaritmin laskentaongelma tehokkaasti liittyy kvanttilaskentaan . On teoreettisesti todistettu, että käyttämällä Shorin algoritmia diskreetti logaritmi voidaan laskea polynomiajassa [14] [15] [16] . Joka tapauksessa, jos diskreetin logaritmin laskemiseen käytetään polynomialgoritmia, tämä tarkoittaa, että siihen perustuvat salausjärjestelmät eivät käytännössä sovellu pitkäaikaiseen tietosuojaan. Useita ideoita uusien julkisen avaimen algoritmien luomiseksi harkitaan .

Muistiinpanot

↑ Buchmann J. , Jacobson MJ, Teske E. Joistakin laskentaongelmista äärellisissä Abelin ryhmissä // Laskennan matematiikka : päiväkirja. - 1997. - Voi. 66 . - s. 1663-1687 . - doi : 10.1090/S0025-5718-97-00880-6 .
↑ S. Pohlig, M. Hellman. Parannettu algoritmi yli logaritmien laskemiseen ja sen kryptografinen merkitys (Corresp.) // IEEE Transactions on Information Theory. - 1978. - tammikuu ( osa 24 , numero 1 ) . - S. 106-110 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1978.1055817 . Arkistoitu alkuperäisestä 21. kesäkuuta 2018.
↑ JM Pollard. Monte Carlon menetelmät indeksien laskemiseen (mod p) // Laskennan matematiikka. - 1978. - tammikuu ( nide 32 , numero 143 ). - S. 918-924 . - doi : 10.1090/S0025-5718-1978-0491431-9 .
↑ L. Adleman. Subeksponentiaalinen algoritmi diskreetin logaritmin ongelmaan kryptografian sovelluksissa // 20th Annual Symposium on Foundations of Computer Science. - 1979. - lokakuu. - S. 55-60 . - doi : 10.1109/SFCS.1979.2 . Arkistoitu alkuperäisestä 10. toukokuuta 2017.
↑ Don Coppersmith, Andrew M. Odlzyko, Richard Schroeppel. Diskreetit logaritmit inGF(p) (englanniksi) // Algorithmica. - 1986. - marraskuu ( osa 1 , painos 1-4 ). - s. 1-15 . - doi : 10.1007/BF01840433 . Arkistoitu alkuperäisestä 13. huhtikuuta 2018.
↑ Daniel M. Gordon. Diskreetit logaritmit GF(p):ssä numerokenttäseulalla // SIAM Journal on Discrete Mathematics. - 1993. - T. 6 , no. 1 . - S. 124-138 . - doi : 10.1137/0406010 .
↑ Don Coppersmith. Numerokenttäseulan muutokset // Journal of Cryptology. - 1993. - Voi. 6 , iss. 3 . - s. 169-180 . - doi : 10.1007/BF00198464 . Arkistoitu alkuperäisestä 19. kesäkuuta 2018.
↑ D. Coppersmith. Nopea logaritmien arviointi ominaisuuden kaksi aloilla // IEEE Transactions on Information Theory. - 1984. - Heinäkuu ( nide 30 , numero 4 ). - S. 587-594 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1984.1056941 .
↑ AJ Menezes, T. Okamoto, SA Vanstone. Elliptisen käyrän logaritmien pelkistäminen logaritmeiksi äärellisessä kentässä // IEEE Transactions on Information Theory. - 1993-09-01. - T. 39 , no. 5 . - S. 1639-1646 . — ISSN 0018-9448 . - doi : 10.1109/18.259647 . Arkistoitu alkuperäisestä 2. heinäkuuta 2017.
↑ Diffie, Hellman, 1976 .
↑ Elgamal, 1984 .
↑ Elgamal, 1985 .
↑ James L. Massey, Jimmy K. Omura. Menetelmä ja laitteisto julkisesti välitettyjen digitaalisten viestien yksityisyyden ylläpitämiseksi (28. tammikuuta 1986). Arkistoitu alkuperäisestä 20. lokakuuta 2016. (määrätön)
↑ Shor, 1994 .
↑ Lyhyt PW -polynomi-aikaalgoritmit alkutekijöihin ja diskreeteille logaritmeille kvanttitietokoneessa // Tietojenkäsittelytieteen perusteet: konferenssijulkaisut. - 1997. - S. 1484-1509.
↑ CompuTerra Online #224 - Kvanttitietokoneet ja kvanttilaskenta ... Keskustelu fysiikan ja matemaattisten tieteiden kandidaatin, algoritmien teorian asiantuntijan Mihail Vyalyn kanssa (Venäjän tiedeakatemian laskentakeskus)

Linkit

Diffie W. , Hellman M.E. Uusia suuntauksia kryptografiassa // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1976. - Voi. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638
Elgamal T. Julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmiin perustuva allekirjoitusjärjestelmä, julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmeihin perustuva allekirjoitusjärjestelmä // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1985. - Voi. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Elgamal T. Julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmiin perustuva allekirjoitusjärjestelmä, julkisen avaimen salausjärjestelmä ja diskreeteihin logaritmeihin perustuva allekirjoitusjärjestelmä // IEEE Trans . inf. Teoria / F. Kschischang - IEEE , 1985. - Voi. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
Shor P. Kvanttilaskennan algoritmit: Diskreetit logaritmit ja faktorointi (englanniksi) // Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on - IEEE , 1994. - S. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . - Moskova: MTSNMO , 2003. - 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Koblitz N. Lukuteorian ja kryptografian kurssi. - Moskova: TVPb, 2001. - 254 s. — ISBN 5-85484-014-6 .
Odlyzko AM Diskreetit logaritmit äärellisissä kentissä ja niiden kryptografinen merkitys // LNCS . - 1984. - T. 209 . - S. 224-316 .
Yu. V. Nesterenko. Luku 4.8. Diskreetti logaritmi // Johdatus kryptografiaan / Toim. V. V. Jaštšenko. - Peter, 2001. - 288 s. - ISBN 5-318-00443-1 .
Diskreettien logaritmien menetelmien yleiskatsaus
Nechaev V.I. Kysymykseen diskreetin logaritmin deterministisen algoritmin monimutkaisuudesta // Matemaattisia huomautuksia . - 1994. - Helmikuu ( nide 55 , numero 2 ). - S. 91-101 .

Sanakirjat ja tietosanakirjat	Iso venäläinen