Algoritmul lui Dixon

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 mai 2021; verificările necesită 4 modificări .

Algoritmul lui Dixon este un algoritm de factorizare care folosește practic ideea lui Legendre , care constă în găsirea unei perechi de numere întregi și astfel încât și $X$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

Metoda lui Dixon este o generalizare a metodei lui Fermat .

Istoric [1]

În anii 1920, Maurice Krajczyk (1882-1957), generalizând teorema lui Fermat, a sugerat în loc de perechi de numere care să satisfacă ecuația , să caute perechi de numere care să satisfacă o ecuație mai generală . Krajczyk a observat câteva fapte utile pentru rezolvare. În 1981, John Dickson a publicat o metodă de factorizare pe care a dezvoltat-o folosind ideile lui Kraitzik și a calculat complexitatea ei de calcul. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Descrierea algoritmului [3]

Faceți o bază de factori formată din toate numerele prime , unde . $\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}$ $p <= M = L\stanga({n}\dreapta)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Alege la întâmplare $b, \sqrt{n}<b<n$
Calculați . $a = b^2\bmod{n}$
Verificați numărul pentru netezime pe divizii de încercare. Dacă este un număr neted , adică , ar trebui să vă amintiți vectorii și : $A$ $A$ $\mathrm{B}$ $a = \prod_{p\isin \Beta}p^{\alpha_{p}\left({b}\right)}$ $\vec{\alpha}\left({b}\dreapta)$ $\vec{\varepsilon}\left({b}\dreapta)$ $\vec{\alpha}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right), \dots, \alpha_{p_h}\left({b}\ corect corect)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\dreapta)\bmod{2}}\dreapta)$ .
Repetați procedura de generare a numerelor până când sunt găsite numere netede . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Folosind metoda Gauss, găsiți o relație liniară între vectori : $\vec{\varepsilon}\left({b_1}\right), \dots, \vec{\varepsilon}\left({b_{h+1}}\right)$ $\vec{\varepsilon}\left({b_{i_1}}\right)\oplus\dots\oplus\vec{\varepsilon}\left({b_{i_t}}\right)=\vec{0}, 1 \leqslant t \leqslant m$ si pune: $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}$ .
Verificați . Dacă da, atunci repetați procedura de generare. Dacă nu, atunci se găsește o descompunere non-trivială: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\dreapta), v=gcd\left({xy,n}\right).$

Dovada corectitudinii [4]

Pentru ca formula să fie corectă, suma trebuie să fie pară. Să demonstrăm: $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}$ rezultă din faptul că: $x^2 = b_{i_1}^2 \dots 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) }}$

Exemplu

Să factorizăm numărul . $n=89755$

L(89755) = 194,174...

M = 13,934...

\Beta = \left\{ 2, 3, 5, 7, 11, 13 \right\}

Toate numerele găsite cu vectorii corespunzători sunt scrise în tabel. $b$ ${\vec {\alpha }}(b)$

$b$	$A$	$\alpha_2\left({b}\dreapta)$	$\alpha_3\left({b}\dreapta)$	$\alpha_5\left({b}\dreapta)$	$\alpha_7\left({b}\dreapta)$	$\alpha_{11}\left({b}\dreapta)$
337	23814	unu	5	0	2	0
430	5390	unu	0	unu	2	unu
519	96	5	unu	0	0	0
600	980	2	0	unu	2	0
670	125	0	0	3	0	0
817	39204	2	patru	0	0	2
860	21560	3	0	unu	2	unu

Rezolvând un sistem liniar de ecuații, obținem că . Apoi $\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}

Prin urmare,

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

S-a dovedit descompunere $89755 = 3095\cdot 29$

Complexitatea computațională [5]

Se notează cu numărul de numere întregi astfel încât și este un număr neted, unde . Din teorema lui de Bruijn-Erdős , unde . Aceasta înseamnă că fiecare număr neted va veni, în medie, prin încercări. Pentru a verifica dacă un număr este neted, trebuie efectuate împărțiri . Conform algoritmului, este necesar să se găsească un număr neted. Deci complexitatea de calcul a găsirii numerelor $\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\stânga({u^{u}\cdot h^{2}}\dreapta)

Complexitatea computațională a metodei Gauss din ecuații $h$

T_2 = O\stânga({h^3}\dreapta)

Prin urmare, complexitatea totală a algoritmului lui Dixon

T = T_1 + T_2 = O\left({u^{u}\cdot h^{2}+h^{3}}\right)

Ținând cont de faptul că numărul de numere prime este mai mic decât este estimat prin formula și că , după simplificare, obținem $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})\dreapta )

$M$ este ales în așa fel încât să fie minim. Apoi înlocuind , obținem $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)}}\right)

Estimarea făcută de Pomeranz pe baza unei teoreme mai riguroase decât teorema de Bruijn-Erdös [6] dă , în timp ce estimarea originală a complexității lui Dixon dă . $T = O\stânga({L\stânga({n}\dreapta)}^{2}\dreapta)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2)}}\right)$

Strategii suplimentare [7]

Luați în considerare strategii suplimentare care accelerează funcționarea algoritmului.

Strategia LP

Strategia LP (Large Prime Variation) folosește numere prime mari pentru a accelera procedura de generare a numerelor . $b$

Algoritm

Numărul găsit la articolul 4 să nu fie neted. Apoi poate fi reprezentat acolo unde nu este divizibil cu numere din baza factorilor. Este evident că . Dacă în plus , atunci s este prim și îl includem în baza factorilor. Acest lucru vă permite să găsiți numere netede suplimentare, dar crește numărul de numere netede necesare cu 1. Pentru a reveni la baza factorilor inițiali după pasul 5, procedați în felul următor. Dacă se găsește un singur număr, a cărui extindere este inclusă într-un grad impar, atunci acest număr trebuie șters din listă și șters din baza factorilor. Dacă, de exemplu, există două astfel de numere și , atunci acestea trebuie tăiate și numărul adăugat . Indicatorul va intra în expansiune într-un grad egal și va fi absent în sistemul de ecuații liniare. $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}$

Variația strategiei

Este posibil să se utilizeze strategia LP cu mai multe numere prime care nu sunt cuprinse în baza factorilor. În acest caz , teoria grafurilor este folosită pentru a exclude numere prime suplimentare .

Complexitate computațională

Estimarea teoretică a complexității algoritmului folosind strategia LP, realizată de Pomerants, nu diferă de estimarea versiunii originale a algoritmului Dixon:

T_{LP} = O\stânga({L\stânga({n}\dreapta)}^{2}\dreapta)

Strategia EAS

Strategia EAS (pauza timpurie) elimină unele dintre considerente prin nefinalizarea testului de netezime. $b$ $A$

Algoritm

se aleg cele fixe . În algoritmul lui Dixon, este factorizat prin diviziuni de probă cu . În strategie, se alege EAS și numărul este mai întâi factorizat prin diviziunile de probă cu , iar dacă după descompunere partea necompusă rămâne mai mare decât , atunci cea dată este aruncată. $0 < k, l, m < 1$ $A$ $p < M = L\stanga({n}\dreapta)^{\frac{1}{2}}$ $M = L\stânga({n}\dreapta)^{k}$ $p < M^l = L\stânga({n}\dreapta)^{kl}$ $n^{1-m}$ $b$

Variația strategiei

Este posibil să folosiți o strategie EAS cu pauze multiple, adică cu o secvență ascendentă și o secvență descrescătoare . $l_j$ $m_{j}$

Complexitate computațională

Algoritmul lui Dixon care utilizează strategia EAS pentru este estimat $k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}$

T_{EAS} = O\stanga({L\stanga({n}\dreapta)}^{\sqrt{\frac{7}{2))}\dreapta)

PS Strategy

Strategia PS folosește algoritmul Pollard-Strassen , care pentru și găsește divizorul prim minim al numărului de mcd-uri în . [opt] $z, t \in \mathbb{N}$ $y=z^2$ $(Multumesc!)$ $O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)$

Algoritm

Fix este selectat . În algoritmul lui Dixon, este factorizat prin diviziuni de probă cu . În strategia PS, . noi credem . Aplicăm algoritmul Pollard-Strassen, alegând pentru partea necompusă, obținem expansiunea . $0<k<1$ $A$ $p < M = L\stanga({n}\dreapta)^{\frac{1}{2}}$ $M = L\stânga({n}\dreapta)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a$ $t$ $A$

Complexitate computațională

Complexitatea algoritmului lui Dixon cu strategia PS este minimă la și este egală cu $k = \frac{1}{\sqrt{3))$

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

Note

↑ Ișmukhametov, 2011 , p. 115.
↑ Dixon, J.D.Factorizarea rapidă asimptotic a numerelor întregi // Math . Comp. : jurnal. - 1981. - Vol. 36 , nr. 153 . - P. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Cheryomushkin, 2001 , p. 77-79.
↑ Vasilenko, 2003 , p. 79.
↑ Cheryomushkin, 2001 , p. 79-80.
↑ C. Pomerance. Analiza și compararea unor algoritmi de factoring întregi // HW Lenstra și R. Tijdeman, Eds., Computational Methods in Number Theory, Math Center Tracts —Part 1. Math Centrum, Amsterdam : Articolul. - 1982. - S. 89-139 . Arhivat din original pe 6 noiembrie 2021.
↑ Vasilenko, 2003 , p. 81-83.
↑ Cheryomushkin, 2001 , p. 74-75.

Literatură

Vasilenko O. N. Algoritmi teoretici numeric în criptografie . — M .: MTsNMO , 2003. — S. 78-83. — 328 p. — ISBN 5-94057-103-4 . Arhivat pe 27 ianuarie 2007 la Wayback Machine
Cheremushkin AV Prelegeri despre algoritmi aritmetici în criptografie . - M. : MTSNMO , 2001. - S. 74-80. — 104 p. — ISBN 5-94057-060-7 . Arhivat pe 31 mai 2013 la Wayback Machine
Ishmukhametov Sh. T. Metode de factorizare pentru numere naturale: un tutorial . - Kazan: Kazan. un., 2011. - S. 115-117. — 190 p.