Dixons algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. maj 2021; checks kræver 4 redigeringer .

Dixons algoritme er en faktoriseringsalgoritme , der grundlæggende bruger Legendres idé , som består i at finde et par heltal og sådan, at og $x$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

Dixons metode er en generalisering af Fermats metode .

Historie [1]

I 1920'erne foreslog Maurice Krajczyk (1882-1957), der generaliserede Fermats teorem, i stedet for talpar, der opfylder ligningen , at kigge efter talpar, der opfylder en mere generel ligning . Krajczyk bemærkede flere fakta, der var nyttige til at løse. I 1981 udgav John Dickson en faktoriseringsmetode, som han udviklede ved hjælp af Kraitziks ideer og beregnede dens beregningsmæssige kompleksitet. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Beskrivelse af algoritmen [3]

Lav en faktorbase bestående af alle primtal , hvor . $\Beta = \venstre\{ {p_1,p_2,\dots,p_h} \right\}$ $p <= M = L\venstre({n}\højre)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Vælg tilfældigt $b, \sqrt{n}<b<n$
Beregn . $a = b^2\bmod{n}$
Kontroller tallet for jævnhed ved prøveopdelinger. Hvis er et -glat tal , det vil sige , skal du huske vektorerne og : $-en$ $-en$ $\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}\ højre)}\right)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\right)\bmod{2}}\right)$ .
Gentag talgenereringsproceduren, indtil der findes jævne tal . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Brug Gauss-metoden til at finde en lineær sammenhæng mellem vektorerne : $\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$ og læg: $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}$ .
Tjek . Hvis det er tilfældet, så gentag genereringsproceduren. Hvis ikke, så findes en ikke-triviel nedbrydning: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({xy,n}\right).$

Korrekthedsbevis [4]

For at formlen er korrekt, skal summen være lige. Lad os bevise 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ølger af, at: $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) }}$

Eksempel

Lad os faktorisere tallet . $n=89755$

L(89755) = 194,174...

M = 13.934...

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

Alle de fundne tal med de tilsvarende vektorer er skrevet i tabellen. $b$ ${\vec {\alpha }}(b)$

$b$	$-en$	$\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	en	5	0	2	0
430	5390	en	0	en	2	en
519	96	5	en	0	0	0
600	980	2	0	en	2	0
670	125	0	0	3	0	0
817	39204	2	fire	0	0	2
860	21560	3	0	en	2	en

Ved at løse et lineært ligningssystem får vi det . Derefter $\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ølgelig,

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

Det viste sig nedbrydning $89755 = 3095\cdot 29$

Beregningsmæssig kompleksitet [5]

Betegn med antallet af heltal sådan, at og er et -glat tal, hvor . Fra de Bruijn-Erdős sætning , hvor . Det betyder, at hvert -glat tal i gennemsnit vil komme på tværs af forsøg. For at kontrollere, om et tal er -glat, skal der udføres divisioner . Ifølge algoritmen er det nødvendigt at finde et -glat tal. Altså den beregningsmæssige kompleksitet ved at finde tal $\Psi(n, M)$ $-en$ $1 < a \leqslant n$ $-en$ $\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\venstre({u^{u}\cdot h^{2}}\højre)

Beregningsmæssig kompleksitet af Gauss-metoden ud fra ligninger $h$

T_2 = O\venstre({h^3}\højre)

Derfor er den samlede kompleksitet af Dixons algoritme

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

Under hensyntagen til, at antallet af primtal er mindre end estimeret af formlen , og at vi efter forenkling 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$ er valgt på en sådan måde, at den er minimal. Så erstatter vi, får vi $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)

Estimatet lavet af Pomeranz på grundlag af en mere stringent sætning end de Bruijn-Erdös sætning [6] giver , mens Dixons oprindelige estimat af kompleksitet giver . $T = O\venstre({L\venstre({n}\højre)}^{2}\højre)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\right)$

Yderligere strategier [7]

Overvej yderligere strategier, der fremskynder driften af algoritmen.

LP strategi

LP-strategien (Large Prime Variation) bruger store primtal til at fremskynde talgenereringsproceduren . $b$

Algoritme

Lad tallet fundet i punkt 4 være ujævnt. Så kan det repræsenteres hvor er ikke deleligt med tal fra faktorgrundlaget. Det er åbenlyst . Hvis derudover , så er s primtal, og vi inkluderer det i faktorgrundlaget. Dette giver dig mulighed for at finde yderligere -glatte tal, men øger antallet af nødvendige glatte tal med 1. For at vende tilbage til den oprindelige faktorbase efter trin 5, gør følgende. Findes der kun ét tal, hvis udvidelse indgår i ulige grad, så skal dette tal slettes fra listen og slettes fra faktorgrundlaget. Hvis der for eksempel er to sådanne numre og , så skal de streges over og tallet tilføjes . Indikatoren vil gå ind i udvidelsen i en jævn grad og vil være fraværende i systemet af lineære ligninger. $-en$ $\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 af strategi

Det er muligt at bruge LP-strategien med flere primtal, der ikke er indeholdt i faktorbasen. I dette tilfælde bruges grafteori til at udelukke yderligere primtal .

Beregningsmæssig kompleksitet

Det teoretiske skøn over kompleksiteten af algoritmen ved hjælp af LP-strategien, lavet af Pomerants, adskiller sig ikke fra estimatet af den originale version af Dixon-algoritmen:

T_{LP} = O\venstre({L\venstre({n}\højre)}^{2}\højre)

EAS-strategi

EAS-strategien (early break) eliminerer nogle af overvejelserne ved ikke at fuldføre glathedstesten . $b$ $-en$

Algoritme

faste er valgt . I Dixons algoritme er det faktoriseret ved forsøgsdivisioner med . I strategien vælges EAS, og tallet faktoriseres først ved forsøgsdivisioner med , og hvis den udekomponerede del efter nedbrydning forbliver større end , så kasseres den givne. $0 < k, l, m < 1$ $-en$ $p < M = L\venstre({n}\højre)^{\frac{1}{2}}$ $M = L\venstre({n}\højre)^{k}$ $p < M^l = L\venstre({n}\højre)^{kl}$ $n^{1-m}$ $b$

Variation af strategi

Det er muligt at bruge en EAS-strategi med flere pauser, det vil sige med en stigende sekvens og en faldende sekvens . $l_j$ $m_{j}$

Beregningsmæssig kompleksitet

Dixons algoritme ved hjælp af EAS-strategien for er estimeret $k = \sqrt{\frac{2}{7}}, l = \frac{1}{2}, m = \frac{1}{7}$

T_{EAS} = O\venstre({L\venstre({n}\højre)}^{\sqrt{\frac{7}{2))}\højre)

PS-strategi

PS-strategien bruger Pollard-Strassen-algoritmen , som for og finder den mindste prime divisor af antallet af gcd'er i . [otte] $z, t \in \mathbb{N}$ $y=z^2$ $(t, y!)$ $O\venstre(z \cdot \ln^2{z} \cdot \ln^2{t}\højre)$

Algoritme

Fixed er valgt . I Dixons algoritme er det faktoriseret ved forsøgsdivisioner med . I PS-strategien . Vi tror . Vi anvender Pollard-Strassen-algoritmen, idet vi vælger den usammensatte del, vi opnår udvidelsen . $0<k<1$ $-en$ $p < M = L\venstre({n}\højre)^{\frac{1}{2}}$ $M = L\venstre({n}\højre)^{k}$ $z = [L\venstre({n}\højre)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\venstre({n}\højre)^{k}, t = a$ $t$ $-en$

Beregningsmæssig kompleksitet

Kompleksiteten af Dixons algoritme med strategi PS er minimal ved og er lig med $k = \frac{1}{\sqrt{3))$

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

Noter

↑ Ishmukhametov, 2011 , s. 115.
↑ Dixon, J.D.Asymptotisk hurtig faktorisering af heltal // Matematik . Comp. : journal. - 1981. - Bd. 36 , nr. 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. Analyse og sammenligning af nogle heltalsfaktoreringsalgoritmer // HW Lenstra og R. Tijdeman, red., Computational Methods in Number Theory, Math Center Tracts —Del 1. Math Centrum, Amsterdam: Artikel. - 1982. - S. 89-139 . Arkiveret fra originalen den 6. november 2021.
↑ Vasilenko, 2003 , s. 81-83.
↑ Cheryomushkin, 2001 , s. 74-75.

Litteratur

Vasilenko O. N. Talteoretiske algoritmer i kryptografi . — M .: MTsNMO , 2003. — S. 78-83. — 328 s. — ISBN 5-94057-103-4 . Arkiveret 27. januar 2007 på Wayback Machine
Cheremushkin AV Forelæsninger om aritmetiske algoritmer i kryptografi . - M. : MTSNMO , 2001. - S. 74-80. — 104 s. — ISBN 5-94057-060-7 . Arkiveret 31. maj 2013 på Wayback Machine
Ishmukhametov Sh. T. Faktoriseringsmetoder for naturlige tal: en tutorial . - Kazan: Kazan. un., 2011. - S. 115-117. — 190 s.