Pollardin rho-menetelmä diskreetille logaritmille

Pollardin ro-menetelmä diskreetille logaritmille ( -method ) on algoritmi diskreetille logaritmille jäännösten renkaassa modulo alkuluku, jolla on eksponentiaalinen monimutkaisuus . Brittiläisen matemaatikon John Pollardin vuonna 1978 ehdottama algoritmin perusideat ovat hyvin samankaltaisia kuin Pollardin lukukerroinlaskentaan tarkoitetun ro-algoritmin . Tätä menetelmää tarkastellaan nollasta poikkeavien tähteiden ryhmälle modulo , jossa on alkuluku, joka on suurempi kuin . $\rho$ $s$ $s$ $3$

Diskreetin logaritmiongelman lause

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

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

(yksi)

jossa on elementin muodostaman syklisen ryhmän elementti . $b$ $G$ $a$

Ro-menetelmän algoritmi

Tarkastellaan kokonaislukuparien sarjaa modulo ja kokonaislukujen sarjaa modulo , jotka määritellään seuraavasti: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $s$

\{u_i\}, \{v_i\}, \{z_i\},\ i\in N,

(2)

u_0=v_0=0,\ z_0=1;

u_{i+1} = \begin{cases} u_i+1\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2u_i\;\bmod\; (p-1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ u_i\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{cases}

(3)

v_{i+1} = \begin{cases} v_i\;\bmod\;(p-1), & 0<z_i<\frac{p}{3};\\ 2v_i\;\bmod\;(p -1), & \frac{p}{3}<z_i<\frac{2}{3}p;\\ v_i+1\;\bmod\;(p-1), & \frac{2}{ 3}p<z_i<p; \end{cases}

(neljä)

z_{i+1}\equiv b^{u_{i+1}}a^{v_{i+1}} \pmod{p} = \begin{cases} bz_i\;\bmod\;p, & 0 <z_i<\frac{p}{3};\\ z_i^2\;\bmod\;p, & \frac{p}{3}<z_i<\frac{2}{3}p;\\ az_i \;\bmod\;p, & \frac{2}{3}p<z_i<p; \end{cases}

(5)

Huomautus: kaikissa lausekkeissa otetaan huomioon pienimmät ei-negatiiviset tähteet.

Huomautus 2 : Yleisemmässä tapauksessa on mahdollista jakaa 3 osajoukkoa hieman eri tavalla: jaamme ryhmän kolmeen suunnilleen samankokoiseen osajoukkoon, jotta se ei kuulu osajoukkoon . $G$ $S_1, S_2, S_3$ $yksi$ $S_{2}$

Koska jokainen kolmas segmentistä, johon elementti kuuluu, ei todennäköisesti liity sekvenssien elementteihin , tuloksena oleva sekvenssi on näennäissatunnainen. Siksi voi olla numeroita ja sellaisia, että . Jos löydät tällaisen numeroparin, saat: $\{u_i, v_i\}$ $j$ $k$ $z_k = z_j$

b^{u_j}a^{v_j}\equiv b^{u_k}a^{v_k} \pmod{p}.

(6)

Jos luku on suhteellisen alkuluku , niin tämä vertailu voidaan ratkaista ja diskreetti logaritmi löytyy: $u_j - u_k$ $p - 1$

b^{u_j - u_k}\equiv a^{v_k - v_j} \pmod{p}.

x\equiv\log_a{b}\equiv(u_j-u_k)^{-1}(v_k-v_j)\pmod{p-1}.

(7)

Jos lukujen suurin yhteinen jakaja ja on yhtä suuri kuin luku , niin tälle vertailulle on ratkaisu modulo . Olkoon , sitten haluttu luku , josta voi ottaa arvot . Siksi, jos luku on riittävän pieni, ongelma ratkaistaan laskemalla kaikki mahdolliset arvot . Pahimmassa tapauksessa - kun - menetelmä ei ole parempi kuin täydellinen luettelo kaikista mahdollisista arvoista diskreetille logaritmille. $u_j - u_k$ $p - 1$ $d > 1$ $x$ $(p - 1) / d$ $x = x_0$ $(mod (p - 1)/d)$ $x = x_0 + m(p - 1)/d$ $m$ $0, 1, ... , d - 1$ $d$ $m$ $d = p - 1$

Indeksien etsimiseen käytetään Floydin syklihakualgoritmia . Tätä algoritmia käytettäessä -: nnessä vaiheessa on arvot ja haetaan numero , jolle . Pienintä arvoa , jolla tämä ehto täyttyy, kutsutaan epact . Jos samaan aikaan , niin $j$ $k$ $i$ $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ $i$ $z_i = z_{2i}$ $i$ $(u_{2i}-u_i,\p-1)=1$

x\equiv\log_a{b}\equiv(u_{2i}-u_i)^{-1}(v_{i}-v_{2i})\pmod{p-1 }.

(kahdeksan)

Po-menetelmä pisteryhmälle elliptisellä käyrällä

Olkoon elliptisen käyrän (EC) pisteiden ryhmä annettu . Yleisyyttä menettämättä voimme olettaa, että ja on alkuluku. Merkitse järjestysalaryhmää ja korjaa generoiva elementti . Ryhmän mielivaltaiselle elementille diskreetin logaritmin ongelma on löytää elementti $E(F_p)$ $p>3$ $s$ $E(F_p)$ $n$ $G$ $P$ $Q = xP$ $1<x<n.$

Ryhmä on edustettuna liittona , jossa on mielivaltaisia joukkoja, joilla on suunnilleen sama kardinaliteetti. Iterointifunktio määritellään seuraavasti $G$ $G = S_1 \kuppi S_2 \kuppi S_3$ $Si$ $f\colon G\to G$

R_{i+1} = f(R_i) = \begin{cases} Q + R_i, & R_i \in S_1; \\ 2R_i, & R_i \in S_2;\\ P + R_i, & R_i \in S_3; \end{cases}

(9)

Siten missä kertoimet määritellään seuraavasti $R_i = a_iP + b_iQ$

a_{i+1} = \begin{cases} a_i, & R_i \in S_1; \\ 2a_i, & R_i \in S_2;\\ a_i + 1, & R_i \in S_3; \end{cases}

(kymmenen)

b_{i+1} = \begin{cases} b_i + 1, & R_i \in S_1; \\ 2b_i, & R_i \in S_2;\\ b_i, & R_i \in S_3; \end{cases}

(yksitoista)

Valitsemalla mielivaltainen alkuarvo , kaksi sekvenssiä ja rakennetaan, kunnes törmäys löytyy jossain . Kaavojen (10) ja (11) perusteella diskreetti logaritmiongelma ratkaistaan: $R_{0}$ $R_i$ $R_{2i}$ $m : R_m = R_{2m}$

x = \frac{a_{2m} - a_m}{b_m - b_{2m}}

(12)

On tärkeää, että törmäyksen aikana saatu arvo riippuu alkuarvosta ja määrittää Pollard-menetelmän laskennallisen monimutkaisuuden. $m$ $R_{0}$

Algoritmin monimutkaisuus

Algoritmin päätehtävänä on sekvenssien laskeminen . Nämä laskelmat vaativat kolme modulo-kertoa päästäkseen seuraavaan iteraatioon. Tarvittavan muistin koko on minimaalinen, koska sekvenssien kaikista aikaisemmista elementeistä ei tarvitse tallentaa tietoja. Siten algoritmin monimutkaisuus vähenee epactin löytämisen ongelman monimutkaisuuteen, jolla puolestaan on heuristinen monimutkaisuusestimaatti , ja eri tapauksissa vakion arvot voivat olla melko erilaisia, mutta esim. sääntö, sijaitsevat sisällä . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt p$ $[1;3]$

Vertailu muihin algoritmeihin

Muihin diskreetteihin logaritmialgoritmeihin verrattuna Pollardin algoritmi on halvempi sekä binäärioperaatioiden että tarvittavan muistimäärän kannalta. Esimerkiksi riittävän suurille lukuarvoille tämä algoritmi on tehokkaampi monimutkaisuuden suhteen kuin COS- algoritmi ja Adleman-algoritmi , joilla on monimutkaisuus . Verrattuna Shanks-algoritmiin , jolla on myös monimutkaisuus , Pollard-algoritmi on edullisempi käytettävän muistin suhteen - Shanks-algoritmi vaatii muistia, kun taas vaaditun muistin koko on vakio tälle algoritmille (olettaen, että Floydin syklin hakualgoritmi on käytetty). $\rho-$ $s$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Menetelmän rinnastaminen

Hajautetut muistijärjestelmät

Pollardin hajautettujen muistijärjestelmien menetelmän ideana on erottaa pisteiden iterointi asiakastyöasemien välillä ja palvelimen törmäyksen etsiminen. Olkoon annettu joukko asiakastyöasemia Palvelin määrittää järjestelmän yhteiset parametrit, jotkin osajoukot ja alustaa työasemat. Asiakastyöasema rakentaa pistesarjan ja lähettää pisteet elementti kerrallaan palvelimelle. Jos piste ei ole tietokannassa, palvelin lisää pisteen tietokantaan, muussa tapauksessa se laskee diskreetin logaritmin arvon. $\rho-$ $S = \vasen \{ S_i \mid i = 1 ... r\oikea \}.$ $D\alajoukko G$ $Si$ $R_{ij} \alajoukko D$

Jaetut muistijärjestelmät

Tämän menetelmän ideana on rinnastaa iteraatiofunktio ja törmäyksentunnistusalgoritmi erikseen. Iterointifunktio rinnastetaan sekvenssien laskentavaiheessa ja . On huomattava, että kiinteän arvon ja rinnakkainen laskenta sekä sitä seuraava vertailu on tehotonta. Tämä johtuu siitä, että virtojen käyttöön liittyvä yleiskustannukset ovat laskennallisesti kalliimpia kuin laskennalliset kustannukset , joten sekvenssit on suositeltavaa laskea siten, että overhead on tasattu. Tämä voidaan saavuttaa järjestämällä laskelmat sekvenssien muotoa ja , missä on laskentalohkon koko, . Törmäyksentunnistustoiminto Pollard-menetelmässä vertaa ja . Tämä vertailu voidaan rinnastaa käyttämällä iterointialgoritmia jaetuille muistijärjestelmille. Pisteiterointifunktion suorittamisen tulos on kaksi pistettä ja , joita verrataan lohko lohkolta, eli kahden ytimen tapauksessa. $R_i$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $minä_{0}$ $R_{2i_0} = f (R_{2i_{0} - 2})$ $\left \{ R_{iw+j}\right \}^l_{i=0}$ $\vasen \{ R_{2(iw+j)}\oikea \}^l_{i=0}$ $w$ $0 \leqslant j < w, l = \left \lceil \frac{m}{w} \right \rceil$ $\rho-$ $R_m$ $R_{2m}$ $\left \{ R_{i}\right \}^w_{i=0}$ $\left \{ R_{2i}\right \}^w_{i=0}$ $R_i = R_{2i}, i = 1 ...\frac{w}{2}$ $R_i = R_{2i}, i = \frac{w}{2} ... w$

Yhdistetty menetelmä

Hajautettujen muistijärjestelmien Pollard-menetelmää voidaan laajentaa käytettäväksi moniytimisissä työasemissa. Menetelmän ideana on, että asiakastyöasemien pisteiden iterointi tapahtuu tietyn algoritmin mukaisesti, jonka ydin on, että on olemassa asiakastyöasema, joka rakentaa pistejonon . Seuraavaksi työasema valitsee pisteiden osajoukon ja lähettää sen palvelimelle. Osajoukkoon kuulumisen tarkistus suoritetaan rinnakkaistilassa: ja (kahden ytimen tapauksessa). Palvelin lisää pisteitä ja tietokantaan, kunnes se löytää jo olemassa olevan pisteen. $\rho-$ $Si$ $\vasen \{ R_{ij}\oikea \}^w_{j=0}$ $Si$ $\vasen \{ R_{ij}\oikea \}^w_{j=0} \cap D$ $R_{ij} \in D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, i = \frac{w}{2} ... w$ $\vasen \{ R_{ij}\oikea \}^w_{j=0} \cap D$

Muutokset ja optimoinnit

Algoritmiin on tehty useita merkittäviä parannuksia erilaisiin temppuihin perustuen.

Yksi parannus on kuvattu julkaisussa [Teske 1998]. Työssä esitetyn menetelmän ero on monimutkaisessa iteratiivisessa funktiossa - se sisältää 20 eri haaraa edellä kuvattujen kolmen sijaan. Numeeriset kokeet osoittavat, että tällainen parannus johtaa satunnaiskävelyalgoritmin keskimääräiseen nopeuteen 20 %.

$\lambda-$ Pollardin menetelmä

Diskreettien logaritmien laskemista koskevassa työssään Pollard ehdotti myös menetelmää, joka on saanut nimensä, koska kreikkalaisen kirjaimen muoto muistuttaa kuvaa, jossa kaksi polkua yhdistyy yhdeksi. Menetelmän ideana on kulkea kahta tietä kerralla: yksi luvusta, jonka diskreetti logaritmi on löydettävä, ja toinen numerosta, jonka diskreetti logaritmi on jo tiedossa. Jos nämä kaksi polkua lähentyvät, on mahdollista löytää luvun diskreetti logaritmi . Pollard ehdotti, että kunkin polun askeleita pidettäisiin kenguruhyppyinä, minkä vuoksi tätä algoritmia kutsutaan joskus "kengurumenetelmäksi". Jos tiedetään, että haluttu diskreetti logaritmi on jossain lyhyessä välissä, niin kengurumenetelmää voidaan mukauttaa, nimittäin käyttämällä kenguruja lyhyemmillä hyppyillä. $\lambda-$ $b$ $B$ $b$

Yksi lambda-menetelmän tärkeä ominaisuus on se, että se on helppo jakaa useille tietokoneille. Jokainen hajautetun laskennan osallistuja valitsee satunnaisluvun ja alkaa tehdä näennäissatunnaisia askelia luvusta , jossa on se ryhmän elementti, jolle diskreetti logaritmi haetaan. Jokainen osallistuja käyttää samaa helposti laskettavaa näennäissatunnaista funktiota , jossa on suhteellisen pieni joukko lukuja, joiden keskiarvo on verrattavissa ryhmän kokoon , jolla on järjestys . Tehot lasketaan etukäteen . Sitten "vaeltaminen", alkaen elementistä , saa muodon: $r$ $b^r$ $b$ $f\colon G\to S$ $S$ $G$ $n$ $a^s$ $s\in S$ $b^r$ $w_0 = b^r, w_1 = w_0a^{f(w_0)}, w_2 = w_1a^{f(w_1)}, ...$

Anna toisen osallistujan, valitessaan alkuluvun , saada sekvenssi Jos se leikkaa jonon , eli joillekin , niin, kun otetaan huomioon, että , seuraava pitää paikkansa: $r^\prime$ $w^\prime_0, w^\prime_1, w^\prime_2, ...$ $w_0, w_1, w_2, ...$ $w^\prime_i = w_j$ $i, j$ $b = a^x$

b^{r^\prime}a^{f(w^\prime_0) + f(w^\prime_1) + ... + f(w^\prime_{i-1})} = b^ra^{ f(w_0) + f(w_1) + ... + f(w_{j-1})}

(13)

(r^\prime - r)x \equiv \sum^{j-1}_{\mu=0} {f(w_\mu)} - \sum^{i-1}_{\nu=0} {f(w^\prime_\nu)} \pmod n

(neljätoista)

Tyypillisesti tätä menetelmää käytetään, kun ryhmäjärjestys on yksinkertainen. Siitä lähtien, jos kaikki laskelmien alussa valitut luvut ovat erilaisia absoluuttisesti , niin vertailu voidaan helposti ratkaista diskreetin logaritmin löytämiseksi . Pieni vaikeus on, että vastaavuus voi tapahtua samassa sarjassa, mikä tarkoittaa, että . Kuitenkin, jos osallistujien määrä laskelmissa on riittävän suuri, niin sekvenssien välisen yhteensopivuuden todennäköisyys on suurempi kuin saman sekvenssin osuvuuden todennäköisyys. $n$ $r$ $n$ $(neljätoista)$ $x$ $r = r^\alkuluku$

On mahdollista käyttää pseudosatunnaisfunktiota . Tässä tapauksessa kaikki osumat ovat hyödyllisiä: saman sekvenssin osumaa voidaan käyttää myös diskreetin logaritmin laskemiseen. Tällaisen vastaavuuden tapauksessa menetelmä yksinkertaisesti muuttuu menetelmäksi. Jos kuitenkin tiedetään, että haluttu diskreetti logaritmi on lyhyellä aikavälillä, voidaan käyttää alkuperäistä menetelmää. Tällöin ajoaika on noin neliöjuuri intervallin pituudesta. Tässä tapauksessa joukon kokonaislukujen keskiarvon tulee olla pienempi, jotta "kengurut" hyppäävät vain halutun pituisen intervallin yli. $(5)$ $\lambda-$ $\rho-$ $S$

Keskustietokoneen on seurattava otteluiden kaikkia jaksoja kaikilta osallistujilta. Syntymäpäiväparadoksin mukaan vastaavuus odotetaan, kun elementtien lukumäärä kaikissa sarjoissa on luokkaa ). Ilmeisesti kuvatussa muodossa tämä menetelmä vaatii suuren määrän keskustietokoneen muistia. Seuraava van Orschotin teoksessa kuvattu idea vähentää huomattavasti muistivaatimuksia ja tekee tästä menetelmästä soveltuvan monimutkaisten ongelmien ratkaisemiseen. Ajatuksena on ottaa huomioon niin sanotut valitut kohdat. Oletetaan, että ryhmän elementtejä edustavat kokonaisluvut (tai mahdollisesti kokonaislukujoukot). Erottuva binääripituuskenttä tällaisessa numerossa koostuu kaikista nollista noin osan ajasta. Satunnainen kävely kulkee tällaisten valittujen pisteiden läpi keskimäärin joka askeleella. Jos kaksi satunnaista sekvenssiä leikkaa jossain, ne leikkaavat edelleen ja pääsevät yhdessä seuraavaan valittuun pisteeseen. Ideana on siis lähettää vain nämä valitut pisteet keskustietokoneelle, mikä pienentää tarvittavaa muistin kokoa kertoimella. $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Kirjallisuus

Vasilenko O.N. Numeroteoreettiset algoritmit kryptografiassa . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Crandall R., Pomerance K. Alkuluvut . Kryptografiset ja laskennalliset näkökohdat. — M.: URSS, 2011 — s. 664. — ISBN 978-5-453-00016-6
Pollard, JM Monte Carlo menetelmät indeksin laskemiseen (mod p ). Laskennan matematiikka - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Pollardin rho-menetelmän nopeuttaminen diskreettien logaritmien laskemiseen. Algorithmic Number Theory Symposium (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. Pollard-algoritmin rinnakkaismenetelmät diskreetin logaritmin ongelman ratkaisemiseksi järjestelmissä, joissa on jaettu muisti — 2012
PC van Oorschot, MJ Wiener Rinnakkaistörmäyshaku kryptanalyyttisten sovellusten kanssa - Journal of Cryptology 12 (1) - 1-28 - 1999