Dixons algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 maj 2021; kontroller kräver 4 redigeringar .

Dixons algoritm är en faktoriseringsalgoritm som i grunden använder Legendres idé , som går ut på att hitta ett par heltal och så att och $x$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

Dixons metod är en generalisering av Fermats metod .

Historik [1]

På 1920 -talet föreslog Maurice Krajczyk (1882-1957), som generaliserade Fermats teorem, att istället för att siffror skulle uppfylla ekvationen , leta efter siffror som uppfyller en mer allmän ekvation . Krajczyk märkte flera fakta användbara för att lösa. 1981 publicerade John Dickson en faktoriseringsmetod som han utvecklade med Kraitziks idéer och beräknade dess beräkningskomplexitet. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Beskrivning av algoritmen [3]

Gör en faktorbas bestående av alla primtal , där . $\Beta = \left\{ {p_1,p_2,\dots,p_h} \right\}$ $p <= M = L\vänster({n}\höger)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Välj slumpmässigt $b, \sqrt{n}<b<n$
Beräkna . $a = b^2\bmod{n}$
Kontrollera numret för jämnhet genom provdelningar. Om är ett -jämnt tal , det vill säga, bör du komma ihåg vektorerna och : $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}\ visst visst)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\right)\bmod{2}}\right)$ .
Upprepa siffergenereringsproceduren tills jämna siffror hittas . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Använd Gauss-metoden, hitta ett linjärt samband mellan vektorerna : $\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$ och sätt: $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}$ .
Kontrollera . Om så är fallet, upprepa genereringsproceduren. Om inte, så hittas en icke-trivial nedbrytning: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({xy,n}\right).$

Korrekthetsbevis [4]

För att formeln ska vara korrekt måste summan vara jämn. Låt oss bevisa det: $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}$ följer av det faktum att: $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) }}$

Exempel

Låt oss faktorisera antalet . $n=89755$

L(89755) = 194,174...

M = 13,934...

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

Alla hittade tal med motsvarande vektorer skrivs i tabellen. $b$ ${\vec {\alpha }}(b)$

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

När vi löser ett linjärt ekvationssystem får vi det . Sedan $\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}

Följaktligen,

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

Det blev sönderfall $89755 = 3095\cdot 29$

Beräkningskomplexitet [5]

Beteckna med antalet heltal så att och är ett -jämnt tal, där . Från de Bruijn-Erdős sats , där . Detta innebär att varje -jämnt nummer i genomsnitt kommer att stöta på försök. För att kontrollera om ett tal är jämnt måste divisioner utföras . Enligt algoritmen är det nödvändigt att hitta ett -jämnt tal. Alltså den beräkningsmässiga komplexiteten i att hitta tal $\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\vänster({u^{u}\cdot h^{2}}\höger)

Beräkningskomplexitet för Gauss-metoden från ekvationer $h$

T_2 = O\vänster({h^3}\höger)

Därför är den totala komplexiteten i Dixons algoritm

T = T_1 + T_2 = O\vänster({u^{u}\cdot h^{2}+h^{3}}\höger)

Med hänsyn till att antalet primtal är mindre än vad som uppskattas av formeln , och att vi efter förenkling får $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})\right )

$M$ är vald på ett sådant sätt att den är minimal. Sedan ersätter vi, vi får $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)

Uppskattningen som gjorts av Pomeranz på grundval av en mer rigorös sats än de Bruijn-Erdös sats [6] ger , medan Dixons ursprungliga uppskattning av komplexitet ger . $T = O\left({L\left({n}\höger)}^{2}\höger)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\right)$

Ytterligare strategier [7]

Överväg ytterligare strategier som påskyndar driften av algoritmen.

LP strategi

LP-strategin (Large Prime Variation) använder stora primtal för att påskynda talgenereringsproceduren . $b$

Algoritm

Låt numret som finns i punkt 4 inte vara jämnt. Då kan det representeras där inte är delbart med tal från faktorbasen. Det är uppenbart att . Om dessutom är s primtal och vi inkluderar det i faktorbasen. Detta gör att du kan hitta ytterligare -släta tal, men ökar antalet nödvändiga jämna tal med 1. För att återgå till den ursprungliga faktorbasen efter steg 5, gör följande. Om endast ett tal hittas, vars expansion ingår i udda grad, måste detta tal tas bort från listan och raderas från faktorbasen. Om det till exempel finns två sådana nummer och , måste de strykas över och numret läggas till . Indikatorn kommer att gå in i expansionen i en jämn grad och kommer att vara frånvarande i systemet med linjära ekvationer. $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}$

Variation av strategi

Det är möjligt att använda LP-strategin med flera primtal som inte ingår i faktorbasen. I det här fallet används grafteori för att utesluta ytterligare primtal .

Beräkningskomplexitet

Den teoretiska uppskattningen av komplexiteten hos algoritmen med hjälp av LP-strategin, gjord av Pomerants, skiljer sig inte från uppskattningen av den ursprungliga versionen av Dixon-algoritmen:

T_{LP} = O\left({L\left({n}\höger)}^{2}\höger)

EAS-strategi

EAS-strategin (early break) eliminerar några av övervägandena genom att inte slutföra jämnhetstestet . $b$ $a$

Algoritm

fasta väljs . I Dixons algoritm faktoriseras den genom försöksdivisioner med . I strategin väljs EAS och numret faktoriseras först genom försöksdivisioner med , och om efter sönderdelning den oupplösta delen förblir större än , så kasseras den givna. $0 < k, l, m < 1$ $a$ $p < M = L\vänster({n}\höger)^{\frac{1}{2}}$ $M = L\vänster({n}\höger)^{k}$ $p < M^l = L\vänster({n}\höger)^{kl}$ $n^{1-m}$ $b$

Variation av strategi

Det är möjligt att använda en EAS-strategi med flera pauser, det vill säga med en stigande sekvens och en fallande sekvens . $l_j$ $m_{j}$

Beräkningskomplexitet

Dixons algoritm som använder EAS-strategin för uppskattas $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))}\right)

PS-strategi

PS-strategin använder Pollard-Strassen-algoritmen , som för och hittar den lägsta primtalsdivisorn för antalet gcds i . [åtta] $z, t \in \mathbb{N}$ $y=z^2$ $(tack!)$ $O\vänster(z \cdot \ln^2{z} \cdot \ln^2{t}\höger)$

Algoritm

Fixed är valt . I Dixons algoritm faktoriseras den genom försöksdivisioner med . I PS-strategin, . Vi tror . Vi tillämpar Pollard-Strassen-algoritmen, väljer för den oupplösta delen, vi får expansionen . $0<k<1$ $a$ $p < M = L\vänster({n}\höger)^{\frac{1}{2}}$ $M = L\vänster({n}\höger)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a$ $t$ $a$

Beräkningskomplexitet

Komplexiteten i Dixons algoritm med strategi PS är minimal vid och är lika med $k = \frac{1}{\sqrt{3))$

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

Anteckningar

↑ Ishmukhametov, 2011 , sid. 115.
↑ Dixon, J.D.Asymptotiskt snabb faktorisering av heltal // Math . Comp. : journal. - 1981. - Vol. 36 , nr. 153 . - S. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Cheryomushkin, 2001 , sid. 77-79.
↑ Vasilenko, 2003 , sid. 79.
↑ Cheryomushkin, 2001 , sid. 79-80.
↑ C. Pomerance. Analys och jämförelse av några heltalsfaktoreringsalgoritmer // HW Lenstra och R. Tijdeman, Eds., Computational Methods in Number Theory, Math Center Tracts —Del 1. Math Centrum, Amsterdam: Artikel. - 1982. - S. 89-139 . Arkiverad från originalet den 6 november 2021.
↑ Vasilenko, 2003 , sid. 81-83.
↑ Cheryomushkin, 2001 , sid. 74-75.

Litteratur

Vasilenko O. N. Talteoretiska algoritmer i kryptografi . — M .: MTsNMO , 2003. — S. 78-83. — 328 sid. — ISBN 5-94057-103-4 . Arkiverad 27 januari 2007 på Wayback Machine
Cheremushkin AV Föreläsningar om aritmetiska algoritmer i kryptografi . - M. : MTSNMO , 2001. - S. 74-80. — 104 sid. — ISBN 5-94057-060-7 . Arkiverad 31 maj 2013 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder för naturliga tal: en handledning . - Kazan: Kazan. un., 2011. - S. 115-117. — 190 sid.