Dixonin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.5.2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Dixonin algoritmi on faktorointialgoritmi , joka periaatteessa käyttää Legendren ideaa , joka koostuu kokonaislukuparin löytämisestä ja sellaisesta , että ja $x$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

Dixonin menetelmä on yleistys Fermatin menetelmästä .

Historia [1]

1920-luvulla Maurice Krajczyk (1882-1957) yleisti Fermatin lauseen, ja ehdotti yhtälön täyttävien lukuparien sijasta etsimään lukupareja , jotka täyttävät yleisemmän yhtälön . Krajczyk huomasi useita ratkaisemiseen hyödyllisiä tosiasioita. Vuonna 1981 John Dickson julkaisi Kraitzikin ideoita käyttäen kehittämänsä faktorointimenetelmän ja laski sen laskennallisen monimutkaisuuden. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Algoritmin kuvaus [3]

Tee kaikista alkuluvuista koostuva tekijäkanta , jossa . $\Beta = \vasen\{ {p_1,p_2,\pisteet,p_h} \oikea\}$ $p <= M = L\vasen({n}\oikea)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Valitse satunnainen $b, \sqrt{n}<b<n$
Laske . $a = b^2\bmod{n}$
Tarkista numeron tasaisuus kokeilujakoittain. Jos on -tasainen luku , eli sinun tulee muistaa vektorit ja : $a$ $a$ $\mathrm{B}$ $a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ $\vec{\alpha}\left({b}\right)$ $\vec{\varepsilon}\left({b}\right)$ $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\ oikea)}\oikea)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\oikea)\bmod{2}}\oikea)$ .
Toista numeroiden luontitoimenpide, kunnes -tasaisia lukuja löytyy . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Etsi Gaussin menetelmällä lineaarinen suhde vektorien välillä : $\vec{\varepsilon}\vasen({b_1}\oikea), \pisteet, \vec{\varepsilon}\vasen({b_{h+1}}\oikea)$ $\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1 \leqslant t \leqslant m$ ja laita: $x=b_{i_1} \dots b_{i_t}\bmod{n}$ $y=\prod_{p\isin\Beta}p^{\left({ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) } \right) \over{2}}\bmod{n}$ .
Tarkista . Jos näin on, toista luontimenettely. Jos ei, niin ei-triviaali hajoaminen löytyy: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({xy,n}\right).$

Oikeustodistus [4]

Jotta kaava olisi oikea, summan on oltava parillinen. Todistetaan se: $y$ $\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right)$ $(\alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right))\bmod{2} = (\varepsilon_p\left({b_{i_1} }\right)+\dots+\varepsilon_p\left({b_{i_t}}\right))\bmod{2} = {\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus \varepsilon\left({b_{i_t}}\right) = 0$
$x^2 \equiv y^2\pmod{n}$ seuraa siitä tosiasiasta, että: $x^2 = b_{i_1}^2 \pistettä b_{i_t}^2 \equiv \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+ \alpha_p\left({b_{i_t}}\right) }}\pmod{n}$ $y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\dots+\alpha_p\left({b_{i_t}}\right) }}$

Esimerkki

Otetaan luku tekijöihin . $n = 89755$

L(89755) = 194,174...

M = 13,934...

\Beta = \vasen\{ 2, 3, 5, 7, 11, 13 \oikea\}

Kaikki löydetyt luvut vastaavilla vektoreilla kirjoitetaan taulukkoon. $b$ ${\vec {\alpha }}(b)$

$b$	$a$	$\alpha_2\left({b}\oikea)$	$\alpha_3\left({b}\oikea)$	$\alpha_5\left({b}\oikea)$	$\alpha_7\left({b}\oikea)$	$\alpha_{11}\left({b}\right)$
337	23814	yksi	5	0	2	0
430	5390	yksi	0	yksi	2	yksi
519	96	5	yksi	0	0	0
600	980	2	0	yksi	2	0
670	125	0	0	3	0	0
817	39204	2	neljä	0	0	2
860	21560	3	0	yksi	2	yksi

Ratkaisemalla lineaarisen yhtälöjärjestelmän saamme, että . Sitten $\vec{\varepsilon}\left(337\right)\oplus\vec{\varepsilon}\left(519\right)=\vec{0}$

x = 337 \cdot 519 \bmod{89755}= 85148

y = 2^3 \cdot 3^3 \cdot 7^1 \bmod{89755} = 1512

85148 \not\equiv \pm 1512 \pmod{89755}

Näin ollen

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

Se osoittautui hajoamiseksi $89755 = 3095\cdot 29$

Laskennallinen monimutkaisuus [5]

Merkitään kokonaislukujen lukumäärällä siten, että ja on -tasainen luku, jossa . De Bruijn-Erdősin lauseesta , jossa . Tämä tarkoittaa, että jokainen -sileä luku tulee keskimäärin vastaan yrityksistä. Jotta voit tarkistaa, onko luku -sileä, jako on suoritettava . Algoritmin mukaan on tarpeen löytää -sileä luku. Joten lukujen löytämisen laskennallinen monimutkaisuus $\Psi(n, M)$ $a$ $1 < a \leqslant n$ $a$ $\mathrm{B}$ $\Beta = \{p : p < M\}$ $\Psi(n, M) = n \cdot u^{-u}$ $u = \frac{\ln{n}}{\ln{M}}$ $\mathrm{B}$ $u^u$ $\mathrm{B}$ $h$ $h+1$ $\mathrm{B}$

T_1 = O\vasen({u^{u}\cdot h^{2}}\oikea)

Gaussin menetelmän laskennallinen monimutkaisuus yhtälöistä $h$

T_2 = O\vasen({h^3}\oikea)

Siksi Dixonin algoritmin kokonaismonimutkaisuus

T = T_1 + T_2 = O\vasen({u^{u}\cpiste h^{2}+h^{3}}\oikea)

Ottaen huomioon, että alkulukujen määrä on pienempi kuin kaavalla on arvioitu ja että yksinkertaistamisen jälkeen saadaan $M$ $h = \frac{M}{\ln{M}}$ $u = \frac{\ln{n}}{\ln{M}}$

T=O\left(exp({\frac {\ln {n}\cdot \ln {\ln {n))}{\ln {M))}+2\ln {M})\oikea )

$M$ valitaan siten, että se on minimaalinen. Sitten korvaamalla saamme $T$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$

M=\left({\frac {L\left({n}\right)}{2}}\right)^{\frac {1}{2}}

T=O\left({L\left({n}\right)}^{2{\sqrt {2))}\oikea)

Pomeranzin tekemä estimaatti de Bruijn-Erdös -lausetta tiukemman lauseen perusteella [6] antaa , kun taas Dixonin alkuperäinen kompleksisuusestimaatti antaa . $T = O\vasen({L\vasen({n}\oikea)}^{2}\oikea)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\oikea)$

Lisästrategiat [7]

Harkitse muita strategioita, jotka nopeuttavat algoritmin toimintaa.

LP-strategia

LP (Large Prime Variation) -strategia käyttää suuria alkulukuja nopeuttamaan numeroiden luontimenettelyä . $b$

Algoritmi

Kohdassa 4 löytyvä luku ei olkoon -sileä. Sitten se voidaan esittää missä ei ole jaollinen luvuilla tekijäkannasta. On selvää, että . Jos lisäksi , niin s on alkuluku ja sisällytämme sen tekijäkantaan. Tämän avulla voit löytää lisää -sileitä lukuja, mutta lisää vaadittujen sileiden lukujen määrää yhdellä. Palataksesi alkuperäiseen kerroinkantaan vaiheen 5 jälkeen toimi seuraavasti. Jos löytyy vain yksi luku, jonka laajennus sisältyy parittomaan asteeseen, tämä numero on poistettava luettelosta ja poistettava tekijäkannasta. Jos esimerkiksi on kaksi tällaista numeroa ja , ne on yliviivattava ja numero on lisättävä . Indikaattori siirtyy laajennukseen tasaisena ja se puuttuu lineaarisesta yhtälöjärjestelmästä. $a$ $\mathrm{B}$ $a = s \cdot \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ $s$ $s > M$ $s < M^2$ $\mathrm{B}$ $s$ $s$ $b_{1}$ $b_{2}$ $b = b_1\cdot b_2$ $s$ $b^2\bmod{n}$

Strategian muunnelma

On mahdollista käyttää LP-strategiaa useilla alkuluvuilla, jotka eivät sisälly tekijäkantaan. Tässä tapauksessa graafiteoriaa käytetään sulkemaan pois ylimääräiset alkuluvut .

Laskennallinen monimutkaisuus

Pomerantsin laatima teoreettinen arvio LP-strategiaa käyttävän algoritmin monimutkaisuudesta ei poikkea Dixon-algoritmin alkuperäisen version arviosta:

T_{LP} = O\vasen({L\vasen({n}\oikea)}^{2}\oikea)

EAS-strategia

EAS (Early Break) -strategia eliminoi osan näkökohdista jättämällä suorittamatta sileystestiä . $b$ $a$

Algoritmi

kiinteät valitaan . Dixonin algoritmissa se kerrotaan koejakoina . Strategiassa valitaan EAS ja luku kerrotaan ensin koejaoilla luvulla , ja jos hajoamisen jälkeen hajoamaton osa jää suuremmaksi kuin , niin annettu hylätään. $0 < k, l, m < 1$ $a$ $p < M = L\vasen({n}\oikea)^{\frac{1}{2}}$ $M = L\vasen({n}\oikea)^{k}$ $p < M^l = L\vasen({n}\oikea)^{kl}$ $n^{1-m}$ $b$

Strategian muunnelma

On mahdollista käyttää EAS-strategiaa, jossa on useita taukoja, eli jossain nousevassa ja laskevassa järjestyksessä . $l_j$ $m_{j}$

Laskennallinen monimutkaisuus

Dixonin algoritmi, joka käyttää EAS-strategiaa for, on arvioitu $k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}$

T_{EAS} = O\left({L\left({n}\right)}^{\sqrt{\frac{7}{2))}\oikea)

PS-strategia

PS-strategia käyttää Pollard-Strassen-algoritmia , joka löytää ja löytää gcd : n lukumäärän minimialkujakajan . [kahdeksan] $z, t \in \mathbb{N}$ $y=z^2$ $(t, y!)$ $O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\oikea)$

Algoritmi

Kiinteä on valittuna . Dixonin algoritmissa se kerrotaan koejakoina . PS-strategiassa . Me uskomme . Käytämme Pollard-Strassen-algoritmia, valitsemalla hajoamattoman osan, saamme laajennuksen . $0<k<1$ $a$ $p < M = L\vasen({n}\oikea)^{\frac{1}{2}}$ $M = L\vasen({n}\oikea)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\oikea)^{k}, t = a$ $t$ $a$

Laskennallinen monimutkaisuus

Dixonin algoritmin monimutkaisuus strategialla PS on minimaalinen ja on yhtä suuri $k = \frac{1}{\sqrt{3))$

T_{PS}=O\left({L\left({n}\right)}^{\sqrt {3}}\right)

Muistiinpanot

↑ Ishmukhametov, 2011 , s. 115.
↑ Dixon, J.D.Asymptoottisen nopea kokonaislukujen tekijöihin jako // Math . Comp. : päiväkirja. - 1981. - Voi. 36 , ei. 153 . - s. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Cheryomushkin, 2001 , s. 77-79.
↑ Vasilenko, 2003 , s. 79.
↑ Cheryomushkin, 2001 , s. 79-80.
↑ C. Pomerance. Joidenkin kokonaislukufaktorointialgoritmien analyysi ja vertailu // HW Lenstra ja R. Tijdeman, toim., Computational Methods in Number Theory, Math Center Tracts — Part 1. Math Centrum, Amsterdam : Artikkeli. - 1982. - S. 89-139 . Arkistoitu alkuperäisestä 6. marraskuuta 2021.
↑ Vasilenko, 2003 , s. 81-83.
↑ Cheryomushkin, 2001 , s. 74-75.

Kirjallisuus

Vasilenko O. N. Lukuteoreettiset algoritmit kryptografiassa . — M .: MTsNMO , 2003. — S. 78-83. — 328 s. — ISBN 5-94057-103-4 . Arkistoitu 27. tammikuuta 2007 Wayback Machinessa
Cheremushkin AV Luennot aritmeettisista algoritmeista kryptografiassa . - M .: MTSNMO , 2001. - S. 74-80. - 104 s. — ISBN 5-94057-060-7 . Arkistoitu 31. toukokuuta 2013 Wayback Machinessa
Ishmukhametov Sh. T. Faktorisointimenetelmät luonnollisille lukuille: opetusohjelma . - Kazan: Kazan. un., 2011. - S. 115-117. - 190 s.