Tilauksen laskenta-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. kesäkuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Järjestyslaskenta -algoritmi ( indeksi-laskenta-algoritmi ) on todennäköisyyspohjainen algoritmi diskreetin logaritmin laskemiseksi jäännösrenkaassa alkuluvun moduloimiseksi . Diskreetin logaritmin löytämisen monimutkaisuus on monien kryptografiaan liittyvien algoritmien perusta . Koska tämän ongelman ratkaiseminen suurilla määrillä vaatii paljon resursseja, joita mikään nykyaikainen tietokone ei pysty tarjoamaan . Esimerkki tällaisesta algoritmista on GOST R 34.10-2012 .

Historia

Maurice Krajczyk ehdotti ensimmäisen kerran tämän algoritmin perusideaa kirjassaan "Théorie des Nombres" vuonna 1922. Vuoden 1976 jälkeen diskreetin logaritmin ongelma tulee tärkeäksi matematiikassa ja kryptausanalyysissä. Tämä johtuu Diffie-Hellmanin salausjärjestelmän luomisesta . Tältä osin vuonna 1977 R. Merkle jatkoi keskusteluja tästä algoritmista. Kaksi vuotta myöhemmin Merkelin kollegat julkaisivat sen ensimmäisen kerran. Lopulta vuonna 1979 Adlerman optimoi sen, tutki sen monimutkaisuutta ja esitteli sen nykyisessä muodossa. Tällä hetkellä järjestyslaskenta-algoritmi ja sen parannetut versiot tarjoavat nopeimman tavan laskea diskreettejä logaritmeja joissakin äärellisissä ryhmissä.

Diskreetin logaritmiongelman lause

Tietylle alkuluvulle ja kahdelle kokonaisluvulle on löydettävä kokonaisluku , joka tyydyttää vertailun: $s$ $g$ $c$ $x$

g^{x}\equiv c\;{\pmod {p}},

jossa on elementin muodostaman syklisen ryhmän elementti . $c$ $G$ $g$

Algoritmi

Syöttö : g - kertaluvun n syklisen ryhmän generaattori , a - syklisestä aliryhmästä, p - alkuluku, c - luotettavuusparametri, joka yleensä on 10 tai luku, joka on lähellä tätä arvoa (käytetään algoritmin toteuttamiseen tietokone, jos henkilö päättää, sitä ei ole asetettu).

Tehtävä : etsi x sellainen, että . $g^{x}\equiv c$

Valitse tekijäkanta S = { p 1 , p 2 , p 3 , …, p t } (Jos G = Z * p , niin kanta koostuu ensimmäisestä t alkuluvusta).
Nostetaan g satunnaiseen potenssiin k , jossa k on sellainen, että . Me saamme . $0\leqslant k<n$ $g^{k}$
Edustamme g k :tä seuraavasti: $g^{k}=\prod _{i=1}^{t}p_{i}^{a_{i)),$ missä (eli yritämme jakaa sen tekijöihin). Jos se ei toimi, palaa vaiheeseen 2. $a_{i}\geqslant 0$
Kohdasta 3 seuraa ilmaus $k\equiv \sum _{i=1}^{t}a_{i}\log _{g}p_{i}\mod n,$ saadaan ottamalla logaritmi (vertailu otetaan modulo ryhmän järjestyksessä, koska työskentelemme eksponentin kanssa, mutta ryhmässä G ). Logaritmit ovat tuntemattomia tässä lausekkeessa. Niitä on t . On tarpeen saada sellaiset yhtälöt t + c kappaletta, jos tämä ei ole mahdollista, palataan vaiheeseen 2 (kun se toteutetaan tietokoneella) tai hankitaan tarvittava määrä yhtälöitä kaikkien tuntemattomien logaritmien löytämiseksi (kun ne on ratkaistu). $g^{n}\equiv 1$
Ratkaisemme tuloksena olevan yhtälöjärjestelmän t tuntemattomilla ja t + c -vertailuilla.
Valitsemme satunnaisluvun k siten, että . Me laskemme . $0\leqslant k<n$ $cg^{k}$
Toistamme kohdan 3 vain numerolle . Jos se ei toimi, palataan kuudenteen kappaleeseen. $cg^{k}$
Samoin kuin kohdassa 4, saamme: $x=\log _{g}c=\sum _{i=1}^{t}a_{i}\log _{g}p_{i}-k\mod n$ , missä ( ), missä . Tässä vaiheessa ratkaisimme diskreetin logaritmin ongelman etsimällä . ${\displaystyle \log _{g}p_{i))$ $1\leqslant i\leqslant t$ $k=\log _{g}g^{k}\mod n$ $x=\log _{g}c$

Lähtö : . $x=\log _{g}c$

Esimerkki

Ratkaise yhtälö: $17\equiv 10^{x}\;(mod47)$

Valitse tekijäkanta Olkoon k = 7 Laske $S=\{2,3,5\}$ $g^{k}$

$k=1\;\;\;\;10^{1}mod47=10=2*5$

$k=2\;\;\;\;10^{2}mod47\equiv 6=2*3$

$k=3\;\;\;\;10^{3}mod47\equiv 13$

$k=4\;\;\;\;10^{4}mod47\equiv 36=2*2*3*3$

$k=5\;\;\;\;10^{5}mod47\equiv 31$

$k=6\;\;\;\;10^{6}mod47\equiv 28=2*2*7$

$k=7\;\;\;\;10^{7}mod47\equiv 45=3*3*5$

Otamme logaritmin ja merkitsemme Ja saamme yhtälöjärjestelmän $U_{i}=log_{g}p_{i}$ $\left\{{\begin{matrix}U_{1}+U_{3}=1\\U_{1}+U_{2}=2\\2U_{1}+2U_{2}=4\\2U_ {2}+U_{3}=7\end{matrix}}\oikea.$

Me ratkaisemme sen

$u_{2}={\frac {8}{3}}(mod46)=8*3^{-1}(mod46)=\{\varphi (46)=\varphi (2*23)\ }=22=8*3^{22}(mod46)\equiv 18$

Todellakin , siis , $10^{18}mod47\equiv 3$ $U_{1}=30$ $U_{2}=18$ $U_{3}=17$

Löydämme k sellaista $cg^{k}={\displaystyle \prod _{i=1}^{t}p_{i}^{a_{i}}}$

$17*10^{1}(mod47)=29$

$17*10^{2}(mod47)=8=2*2*2$

Näin ollen $k = 2$

Otetaan tämän lausekkeen logaritmi ja saadaan

$log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46\equiv 42$

Vastaus : $x = 42$

Vaikeus

Tässä algoritmissa iteraatioiden määrä riippuu sekä p :n koosta että tekijäkannan koosta. Mutta valitsemme tekijäkannan etukäteen, ja sen koko on kiinteä. Siksi lopullinen monimutkaisuus määräytyy vain alkuluvun koon mukaan ja on yhtä suuri kuin: , missä , ovat joitain vakioita, jotka riippuvat välilaskutoimituksista, erityisesti tekijäkannan valinnasta. $O(c_{1}*2^{(c_{2}+o(1)){\sqrt {logp\;loglogp))})$ $c_{1}$ $c_{2}$

Parannukset

Nopeutettu tilauslaskentaalgoritmi , jonka ydin on indeksitaulukon käyttö.

Vaikeus

Laskennallinen monimutkaisuus on vähennetty alkuperäiseen algoritmiin verrattuna. $O(2log_{2}(p))$

Tilauksen laskenta-algoritmi

Historia

Diskreetin logaritmiongelman lause

Algoritmi

Esimerkki

Vaikeus

Parannukset

Vaikeus

Katso myös

Linkit