Dixonův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. května 2021; kontroly vyžadují 4 úpravy .

Dixonův algoritmus je faktorizační algoritmus , který v zásadě využívá Legendrovu myšlenku , která spočívá v nalezení dvojice celých čísel a takových , $X$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

Dixonova metoda je zobecněním Fermatovy metody .

Historie [1]

Ve 20. letech 20. století Maurice Krajczyk (1882-1957), zobecňující Fermatovu větu, navrhl namísto dvojic čísel vyhovujících rovnici hledat dvojice čísel vyhovující obecnější rovnici . Krajczyk si všiml několika skutečností užitečných k řešení. V roce 1981 publikoval John Dickson metodu faktorizace, kterou vyvinul pomocí Kraitzikových myšlenek a vypočítal její výpočetní složitost. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Popis algoritmu [3]

Vytvořte základ faktoru sestávající ze všech prvočísel , kde . $\Beta = \left\{ {p_1,p_2,\tečky,p_h} \vpravo\}$ $p <= M = L\left({n}\right)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\right)}$
Vyberte náhodně $b, \sqrt{n}<b<n$
Vypočítejte . $a = b^2\bmod{n}$
Zkontrolujte hladkost čísla zkušebními děleními. Pokud je -smooth number , to znamená , měli byste si zapamatovat vektory a : $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}\ dobře dobře)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\right)\bmod{2}}\right)$ .
Opakujte postup generování čísel, dokud nenajdete hladká čísla . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
Pomocí Gaussovy metody najděte lineární vztah mezi vektory : $\vec{\varepsilon}\left({b_1}\right), \tečky, \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$ a dát: $x=b_{i_1} \dots b_{i_t}\bmod{n}$ $y=\prod_{p\isin\Beta}p^{\left({ \alpha_p\left({b_{i_1}}\right)+\tečky+\alpha_p\left({b_{i_t}}\right) } \right) \over{2}}\bmod{n}$ .
Zkontrolujte . Pokud ano, opakujte postup generování. Pokud ne, pak je nalezen netriviální rozklad: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({xy,n}\right).$

Důkaz správnosti [4]

Aby byl vzorec správný, musí být součet sudý. Pojďme to dokázat: $y$ $\alpha_p\left({b_{i_1}}\right)+\tečky+\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\tečky\oplus \varepsilon\left({b_{i_t}}\right) = 0$
$x^2 \equiv y^2\pmod{n}$ vyplývá z toho, že: $x^2 = b_{i_1}^2 \tečky b_{i_t}^2 \equiv \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\tečky+ \alpha_p\left({b_{i_t}}\right) }}\pmod{n}$ $y^2 = \prod_{p\isin\Beta}p^{{ \alpha_p\left({b_{i_1}}\right)+\tečky+\alpha_p\left({b_{i_t}}\right) }}$

Příklad

Rozložme číslo na faktor . $n=89755$

L(89755) = 194,174...

M = 13,934...

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

Všechna nalezená čísla s odpovídajícími vektory jsou zapsána do tabulky. $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	jeden	5	0	2	0
430	5390	jeden	0	jeden	2	jeden
519	96	5	jeden	0	0	0
600	980	2	0	jeden	2	0
670	125	0	0	3	0	0
817	39204	2	čtyři	0	0	2
860	21560	3	0	jeden	2	jeden

Řešením lineárního systému rovnic získáme, že . Pak $\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}

Tudíž,

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

Ukázalo se, že rozklad $89755 = 3095\cdot 29$

Výpočetní složitost [5]

Označte počtem celých čísel tak, že a je -hladké číslo, kde . Z de Bruijn-Erdősovy věty , kde . To znamená, že každé -hladké číslo v průměru narazí na pokusy. Chcete-li zkontrolovat, zda je číslo -hladké, musíte provést dělení . Podle algoritmu je nutné najít -hladké číslo. Tedy výpočetní náročnost hledání čísel $\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\left({u^{u}\cdot h^{2}}\vpravo)

Výpočtová složitost Gaussovy metody z rovnic $h$

T_2 = O\levý({h^3}\vpravo)

Proto celková složitost Dixonova algoritmu

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

Vezmeme-li v úvahu, že počet prvočísel je menší, než odhaduje vzorec , a že po zjednodušení dostaneme $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})\vpravo )

$M$ je zvolena tak, aby byla minimální. Pak nahrazením dostaneme $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)

Odhad provedený Pomeranzem na základě přísnější věty, než uvádí de Bruijn-Erdösova věta [6] , zatímco Dixonův původní odhad složitosti dává . $T = O\left({L\left({n}\right)}^{2}\right)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\right)$

Další strategie [7]

Zvažte další strategie, které urychlí činnost algoritmu.

LP strategie

Strategie LP (Large Prime Variation) používá velká prvočísla k urychlení procesu generování čísel . $b$

Algoritmus

Nechť číslo nalezené v položce 4 není hladké. Pak může být reprezentován tam, kde není dělitelné čísly z faktorové základny. Je zřejmé, že . Pokud navíc , pak s je prvočíslo a zahrneme ho do faktorové báze. To vám umožní najít další -hladká čísla, ale zvýší počet požadovaných hladkých čísel o 1. Chcete-li se vrátit k původní základně faktoru po kroku 5, proveďte následující. Pokud je nalezeno pouze jedno číslo, jehož expanze je zahrnuta v lichém stupni, musí být toto číslo vymazáno ze seznamu a odstraněno z faktorové základny. Pokud jsou například dvě taková čísla a , pak je třeba je přeškrtnout a přidat číslo . Indikátor bude vstupovat do expanze v sudé míře a bude chybět v systému lineárních rovnic. $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}$

Variace strategie

Je možné použít strategii LP s několika prvočísly, která nejsou obsažena ve faktorové bázi. V tomto případě se k vyloučení dalších prvočísel používá teorie grafů .

Výpočetní složitost

Teoretický odhad složitosti algoritmu pomocí strategie LP, který provedl Pomerants, se neliší od odhadu původní verze Dixonova algoritmu:

T_{LP} = O\left({L\left({n}\right)}^{2}\right)

Strategie EAS

Strategie EAS (early break) eliminuje některé úvahy tím, že nedokončí test plynulosti . $b$ $A$

Algoritmus

volí se pevné . V Dixonově algoritmu je faktorizován zkušebním dělením podle . Ve strategii se zvolí EAS a číslo se nejprve rozloží zkušebními děleními a pokud po rozkladu zůstane nerozložená část větší než , pak se daná zahodí. $0 < k, l, m < 1$ $A$ $p < M = L\left({n}\right)^{\frac{1}{2}}$ $M = L\left({n}\right)^{k}$ $p < M^l = L\left({n}\right)^{kl}$ $n^{1-m}$ $b$

Variace strategie

Je možné použít strategii EAS s více přestávkami, tedy s nějakou vzestupnou sekvencí a sestupnou sekvencí . $l_j$ $m_{j}$

Výpočetní složitost

Odhaduje se Dixonův algoritmus využívající strategii EAS pro $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))}\vpravo)

PS strategie

Strategie PS používá algoritmus Pollard-Strassen , který pro a najde minimálního prvočíselného dělitele počtu gcd v . [osm] $z, t \in \mathbb{N}$ $y=z^2$ $(t, y!)$ $O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\right)$

Algoritmus

Je vybráno pevné . V Dixonově algoritmu je faktorizován zkušebním dělením podle . Ve strategii PS, . věříme . Aplikujeme Pollard-Strassenův algoritmus, vybereme pro nerozloženou část, získáme expanzi . $0<k<1$ $A$ $p < M = L\left({n}\right)^{\frac{1}{2}}$ $M = L\left({n}\right)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a$ $t$ $A$

Výpočetní složitost

Složitost Dixonova algoritmu se strategickým PS je minimální a rovná se $k = \frac{1}{\sqrt{3))$

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

Poznámky

↑ Ishmukhametov, 2011 , str. 115.
↑ Dixon, J.D.Asymptoticky rychlá faktorizace celých čísel // Math . Comp. : deník. - 1981. - Sv. 36 , č. 153 . - S. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Cheryomushkin, 2001 , str. 77-79.
↑ Vasilenko, 2003 , s. 79.
↑ Cheryomushkin, 2001 , str. 79-80.
↑ C. Pomerance. Analýza a srovnání některých algoritmů faktoringu celočíselných // HW Lenstra a R. Tijdeman, Eds., Computational Methods in Number Theory, Math Center Tracts — Část 1. Math Centrum, Amsterdam: Článek. - 1982. - S. 89-139 . Archivováno z originálu 6. listopadu 2021.
↑ Vasilenko, 2003 , s. 81-83.
↑ Cheryomushkin, 2001 , str. 74-75.

Literatura

Vasilenko O. N. Číselné teoretické algoritmy v kryptografii . — M .: MTsNMO , 2003. — S. 78-83. — 328 s. — ISBN 5-94057-103-4 . Archivováno 27. ledna 2007 na Wayback Machine
Cheremushkin AV Přednášky o aritmetických algoritmech v kryptografii . - M. : MTSNMO , 2001. - S. 74-80. — 104 str. — ISBN 5-94057-060-7 . Archivováno 31. května 2013 na Wayback Machine
Ishmukhametov Sh. T. Faktorizační metody pro přirozená čísla: návod . - Kazaň: Kazaň. un., 2011. - S. 115-117. — 190 str.