Pollard rho módszere diszkrét logaritmushoz

Pollard ro-metódusa diszkrét logaritmushoz ( -method ) egy algoritmus a diszkrét logaritmushoz a maradékok gyűrűjében modulo prím, exponenciális összetettséggel . Az 1978 - ban John Pollard brit matematikus által javasolt algoritmus alapötlete nagyon hasonlít Pollard számfaktorizációs ro - algoritmusához . Ezt a módszert a nem nulla maradékok modulo csoportjára tekintjük , ahol egy prímszám nagyobb, mint . $\rho$ $p$ $p$ $3$

A diszkrét logaritmus feladat utasítása

Adott prímszámra és két egészre, és meg kell találni egy olyan egész számot , amely kielégíti az összehasonlítást: $p$ $a$ $b$ $x$

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

(egy)

ahol az elem által generált ciklikus csoport egy eleme . $b$ $G$ $a$

A ro-metódus algoritmus

A modulo egész számpárok sorozatát és a modulo egész számok sorozatát tekintjük, a következőképpen definiálva: $\{u_i,\ v_i\}$ $p-1$ $\{z_i\}$ $p$

\{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}

(négy)

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)

Megjegyzés: minden kifejezésben a legkisebb, nem negatív maradékokat veszik figyelembe.

2. megjegyzés : általánosabb esetben 3 részhalmazra kicsit eltérő módon is fel lehet osztani: a csoportot három , megközelítőleg egyenlő méretű részhalmazra osztjuk úgy, hogy ne tartozzon a részhalmazba . $G$ $S_1, S_2, S_3$ $egy$ $S_{2}$

Mivel annak a szegmensnek minden harmadik része, amelyhez egy elem tartozik, valószínűleg nincs kapcsolatban a sorozatok elemeivel , a kapott sorozat álvéletlen. Ezért létezhetnek olyan számok , amelyek . Ha talál ilyen számpárt, akkor a következőket kapja: $\{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)

Ha a szám relatív prímszám -hoz , akkor ez az összehasonlítás megoldható, és a diszkrét logaritmus megtalálható: $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)

Ha a számok legnagyobb közös osztója és egyenlő a számmal , akkor van megoldás erre az összehasonlításra a modulo -ra . Legyen , majd a kívánt szám , ahol felveheti az értékeket . Ezért, ha elég kicsi a szám, akkor a problémát az összes lehetséges érték felsorolásával oldjuk meg . A legrosszabb esetben - amikor - a módszer nem bizonyul jobbnak, mint a diszkrét logaritmus összes lehetséges értékének teljes felsorolása. $u_j - u_k$ $p - 1$ $d > 1$ $x$ $(p - 1) / d$ $x = x_0$ $(mód (p - 1)/d)$ $x = x_0 + m(p - 1)/d$ $m$ $0, 1, ... , d - 1$ $d$ $m$ $d = p - 1$

Az indexek kereséséhez a Floyd cikluskeresési algoritmust használjuk . Ennek az algoritmusnak a használatakor a -edik lépésben értékek vannak, és egy számot kell keresni , amelyhez . Azt a legkisebb értéket , amelynél ez a feltétel teljesül, epactnak nevezzük . Ha ugyanakkor , akkor $j$ $k$ $én$ $(z_i,\ u_i,\ v_i,\ z_{2i},\ u_{2i},\ v_{2i})$ $én$ $z_i = z_{2i}$ $én$ $(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}.

(nyolc)

Po-módszer egy elliptikus görbén lévő pontcsoporthoz

Legyen adott egy elliptikus görbe (EC) pontcsoportja . Az általánosság elvesztése nélkül feltételezhetjük, hogy és prímszám. Jelölje a sorrendi alcsoportot és rögzítse a generáló elemet . A csoport tetszőleges eleme esetén a diszkrét logaritmus problémája az elem megtalálása $E(F_p)$ $p>3$ $p$ $E(F_p)$ $n$ $G$ $P$ $Q=xP$ $1<x<n.$

A csoportot unióként ábrázoljuk , ahol közel azonos kardinalitású tetszőleges halmazok vannak. Az iterációs függvény definíciója: $G$ $G = S_1 \pohár S_2 \pohár S_3$ $S_i$ $f\colon G\to G$

R_{i+1} = f(R_i) = \begin{esetek} 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)

Így ahol az együtthatók a következők szerint vannak definiálva $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}

(tíz)

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

(tizenegy)

Egy tetszőleges kezdeti érték kiválasztásával két és szekvenciát készítünk, amíg ütközést nem találunk . A (10) és (11) képlet alapján megoldódik a diszkrét logaritmus feladat: $R_{0}$ $R_i$ $R_{2i}$ $m : R_m = R_{2m}$

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

(12)

Fontos, hogy az ütközés során kapott érték a kezdeti értéktől függ, és meghatározza a Pollard-módszer számítási bonyolultságát. $m$ $R_{0}$

Az algoritmus összetettsége

Az algoritmus fő feladata a sorozatok kiszámítása . Ezekhez a számításokhoz három modulo szorzás szükséges a következő iterációhoz való továbblépéshez. A szükséges memória mérete minimális, mivel nincs szükség a sorozatok összes korábbi elemére vonatkozó információ tárolására. Így az algoritmus összetettsége az epact megtalálásának problémájának összetettségére redukálódik, aminek viszont van egy heurisztikus komplexitásbecslése , és különböző esetekben az állandó értékei egészen eltérőek lehetnek, de pl. egy szabály, feküdj belül . $\{x_i\}, \{x_{2i}\}$ $O(\sqrtp)$ $C\sqrt p$ $[1;3]$

Összehasonlítás más algoritmusokkal

Más diszkrét logaritmus-algoritmusokhoz képest a Pollard-algoritmus olcsóbb mind a bináris műveletek, mind a szükséges memóriamennyiség tekintetében. Például kellően nagy számértékek esetén ez az algoritmus a komplexitás szempontjából hatékonyabb, mint a COS algoritmus és az Adleman algoritmus , amelyek összetettsége . A szintén összetett Shanks algoritmushoz képest a Pollard algoritmus előnyösebb a felhasznált memória szempontjából - a Shanks algoritmus memóriát igényel, míg ennél az algoritmusnál a szükséges memória mérete állandó (feltéve, hogy a Floyd ciklus keresési algoritmusa használt). $\rho-$ $p$ $O(exp{((\log{p}\log{\log{p)))^{1/2})})$ $O(\sqrtp)$ $O(p)$

Módszer párhuzamosítás

Elosztott memóriarendszerek

A Pollard elosztott memóriarendszerekre vonatkozó módszerének ötlete az, hogy elválasztja a pontok iterációját a kliens munkaállomások között és a szerver általi ütközés keresését. Adjuk meg a kliens munkaállomások halmazát A szerver meghatározza a rendszerben közös paramétereket, néhány részhalmazt és inicializálja a munkaállomásokat. A kliens munkaállomás pontsorozatot épít fel, és a pontokat elemenként küldi el a szervernek. Ha a pont nincs az adatbázisban, akkor a szerver hozzáadja a pontot az adatbázishoz, ellenkező esetben kiszámítja a diszkrét logaritmus értékét. $\rho-$ $S = \left \{ S_i \mid i = 1 ... r\right \}.$ $D\G részhalmaz$ $S_i$ $R_{ij} \D részhalmaz$

Osztott memória rendszerek

Ennek a módszernek az az ötlete, hogy az iterációs függvényt és az ütközésészlelési algoritmust külön-külön párhuzamosítsák. Az iterációs függvény párhuzamosításra kerül a sorozatok és szekvenciák kiszámításának szakaszában .. Megjegyzendő, hogy a és a fix érték párhuzamos számítása és az azt követő összehasonlítás nem hatékony. Ennek az az oka, hogy az adatfolyamok használatához kapcsolódó többletköltség számításilag drágább, mint a számítástechnika , ezért célszerű a sorozatokat úgy kiszámítani, hogy a többletterhelés egyenletes legyen. Ezt úgy érhetjük el, hogy rendszerezzük a számításokat a és formájú sorozatok , ahol a számítási blokk mérete, . A Pollard-módszer ütközésészlelési funkciója összehasonlítja és . Ez az összehasonlítás párhuzamosítható egy iterációs algoritmus használatával megosztott memóriarendszerekhez. A pontiterációs függvény végrehajtásának eredménye két ponthalmaz és , amelyeket blokkonként, azaz két kernel esetén összehasonlítunk. $R_i$ $R_{2i}$ $R_{i_0}$ $R_{2i_0}$ $én_{0}$ $R_{2i_0} = f (R_{2i_{0} - 2})$ $\left \{ R_{iw+j}\right \}^l_{i=0}$ $\left \{ R_{2(iw+j)}\right \}^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$

Kombinált módszer

Az elosztott memóriarendszerek Pollard-módszere kiterjeszthető többmagos munkaállomásokon való használatra. A módszer lényege, hogy a pontok kliens munkaállomások általi iterációja egy bizonyos algoritmus szerint történik, aminek a lényege, hogy van egy kliens munkaállomás, amely pontsorozatot épít fel . Ezután a munkaállomás kiválasztja a pontok egy részhalmazát, és elküldi a szervernek. Az egy részhalmazhoz való tartozás ellenőrzése párhuzamos módban történik: és (két mag esetén). A szerver pontokat és pontokat ad hozzá az adatbázishoz, amíg meg nem talál egy már létező pontot. $\rho-$ $S_i$ $\left \{ R_{ij}\right \}^w_{j=0}$ $S_i$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$ $R_{ij} \in D, i = 1 ...\frac{w}{2}$ $R_{ij} \in D, i = \frac{w}{2} ... w$ $\left \{ R_{ij}\right \}^w_{j=0} \cap D$

Módosítások és optimalizálások

Az algoritmuson számos jelentős fejlesztés található különböző trükkök alapján.

Egy fejlesztést ír le [Teske 1998]. A cikkben bemutatott módszer különbsége a bonyolult iteratív függvényben rejlik - a fent leírt három helyett 20 különböző ágat tartalmaz. A numerikus kísérletek azt mutatják, hogy egy ilyen javulás a véletlenszerű séta algoritmusának átlagosan 20%-os gyorsulásához vezet.

$\lambda-$ Pollard módszere

A diszkrét logaritmusok kiszámításáról szóló munkájában Pollard egy módszert is javasolt, amelyet azért neveztek el, mert egy görög betű alakja két út egyesülésének képére hasonlít. A módszer lényege, hogy egyszerre két úton haladunk: az egyik abból a számból indul ki, amelynek diszkrét logaritmusát kell megtalálni, a másikat abból a számból, amelynek a diszkrét logaritmusa már ismert. Ha ez a két út konvergál, lehetségessé válik egy szám diszkrét logaritmusának megtalálása . Pollard azt javasolta, hogy az egyes utak lépéseit kengurugrásnak kell tekinteni, ezért ezt az algoritmust néha "kenguru-módszernek" is nevezik. Ha tudjuk, hogy a kívánt diszkrét logaritmus valamilyen rövid intervallumban rejlik, akkor a kenguru módszer adaptálható, mégpedig rövidebb ugrású kenguruk használatával. $\lambda-$ $b$ $B$ $b$

A lambda módszer egyik fontos tulajdonsága, hogy könnyen elosztható több számítógép között. Az elosztott számítástechnikában minden résztvevő választ egy véletlen számot , és álvéletlen lépéseket kezd a számból , ahol a csoport azon eleme, amelyre a diszkrét logaritmust keresik. Minden résztvevő ugyanazt a könnyen kiszámítható pszeudo-véletlen függvényt használja , ahol a számok viszonylag kis halmaza, amelynek átlagos értéke összehasonlítható a csoport méretével , amelynek sorrendje van . A teljesítményeket előre kiszámítják. Ekkor a "vándorlás" az elemből kiindulva a következő alakot ölti: $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)}, ...$

Hagyja, hogy a másik résztvevő a kezdő számot választva a sorozatot kapja Ha metszi a sorozatot , azaz egyeseknél , akkor, figyelembe véve, hogy , a következő igaz: $r^\prime$ $w^\prím_0, w^\prím_1, w^\prím_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

(tizennégy)

Ezt a módszert általában akkor használják, ha a csoport sorrendje egyszerű. Azóta, ha a számítások elején kiválasztott összes szám abszolút értékben különbözik , akkor az összehasonlítás könnyen megoldható a diszkrét logaritmus meghatározásához . Egy kis nehézséget jelent, hogy az egyezés előfordulhat ugyanabban a sorozatban, ami azt jelenti, hogy . Ha azonban a számításokban részt vevők száma elég nagy, akkor a sorozatok közötti egyezés valószínűsége nagyobb, mint az azonos sorozaton belüli egyezés valószínűsége. $n$ $r$ $n$ $(tizennégy)$ $x$ $r = r^\prím$

Lehetséges pszeudo-véletlen függvény használata . Ebben az esetben az összes egyezés hasznos lesz: az azonos sorozaton belüli egyezés felhasználható a diszkrét logaritmus kiszámítására is. Egy ilyen egyezés esetén a metódus egyszerűen metódussá válik . Ha azonban tudjuk, hogy a kívánt diszkrét logaritmus egy rövid intervallumban található, akkor az eredeti módszer használható. Ekkor a futási idő körülbelül az intervallum hosszának négyzetgyöke lesz. Ebben az esetben a halmaz egészeinek átlagértékének kisebbnek kell lennie, hogy a "kenguruk" csak a kívánt hosszúságú intervallumon ugorjanak át. $(5)$ $\lambda-$ $\rho-$ $S$

A központi számítógépnek nyomon kell követnie minden résztvevőtől a mérkőzések összes sorozatát. A születésnapi paradoxon szerint egyezés akkor várható, ha az elemek száma az összes sorozatban ). Nyilvánvaló, hogy a leírt formában ez a módszer nagy mennyiségű memóriát igényel a központi számítógéptől. A következő, van Orschot munkájában leírt ötlet nagymértékben lecsökkenti a memóriaigényt, és így alkalmazhatóvá teszi ezt a módszert összetett problémák megoldására. Az ötlet az, hogy figyelembe vegyük az úgynevezett kiválasztott pontokat. Feltételezzük, hogy a csoport elemeit egész számok (vagy esetleg egész számok halmazai) reprezentálják. Egy ilyen számban lévő megkülönböztetett bináris hosszúságú mező az idő körülbelül harmadáig minden nullából áll . Egy véletlenszerű séta átlagosan minden lépésben áthalad az ilyen kiválasztott pontokon. Ha két véletlenszerű sorozat valahol metszi egymást, akkor tovább metszik egymást, és együtt jutnak el a következő kiválasztott ponthoz. Tehát az ötlet az, hogy csak ezeket a kiválasztott pontokat küldjük a központi számítógépnek, ami egy faktorral csökkenti a szükséges memória méretét. $O(\sqrt{n})$ $k$ $1/2k$ $2^k$ $2^k$

Irodalom

Vasilenko O.N. Számelméleti algoritmusok a kriptográfiában . - M .: MTSNMO , 2003. - S. 328. - ISBN 5-94057-103-4 . Archiválva 2007. január 27-én a Wayback Machine -nél
Crandall R., Pomerance K. Prímszámok . Kriptográfiai és számítási szempontok. — M.: URSS, 2011 — 664. o. — ISBN 978-5-453-00016-6
Pollard, JM Monte Carlo módszerek indexszámításhoz (mod p ). Számítási matematika - 32(143), 1978-918-924 - JSTOR 2006496
Teske, Pollard rho módszerének felgyorsítása diszkrét logaritmusok kiszámítására. Algoritmikus számelméleti szimpózium (ANTS IV), 1998-541-553
Gorbenko I. D., Kachko E. G. A Pollard-algoritmus párhuzamosítási módszerei a diszkrét logaritmus problémájának megoldására osztott memóriával rendelkező rendszerekben - 2012
PC van Oorschot, MJ Wiener Párhuzamos ütközéskeresés kriptoanalitikai alkalmazásokkal - Journal of Cryptology 12 (1) - 1-28 - 1999