Dixon algoritmusa

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. május 28-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

Dixon algoritmusa egy faktorizációs algoritmus, amely alapvetően Legendre ötletét használja, amely abból áll , hogy találunk egy pár egész számot , és $x$ $y$ $x^2 \equiv y^2\pmod{n}$ $x \not\equiv \pm y\pmod{n}.$

A Dixon-módszer a Fermat-módszer általánosítása .

Előzmények [1]

Az 1920-as években Maurice Krajczyk (1882-1957) Fermat tételét általánosítva azt javasolta, hogy az egyenletet kielégítő számpárok helyett keressenek olyan számpárokat, amelyek kielégítik egy általánosabb egyenletet . Krajczyk több, a megoldáshoz hasznos tényt is észrevett. 1981-ben John Dickson közzétett egy faktorizációs módszert, amelyet Kraitzik ötletei alapján fejlesztett ki, és kiszámította a számítási bonyolultságát. [2] $x^2 - y^2 = n$ $x^2 \equiv y^2\pmod{n}$

Az algoritmus leírása [3]

Készíts egy faktorbázist az összes prímszámból , ahol . $\Beta = \left\{ {p_1,p_2,\pontok,p_h} \jobbra\}$ $p <= M = L\left({n}\right)^{\frac{1}{2}}$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\jobbra)}$
Válassz véletlenszerű lehetőséget $b, \sqrt{n}<b<n$
Számolja ki . $a = b^2\bmod{n}$
Ellenőrizze a szám simaságát próbaosztásonként. Ha egy -sima szám , azaz , akkor emlékeznie kell a vektorokra és 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}\ jó jó)$ $\vec{\varepsilon}\left({b}\right)=\left({\alpha_{p_1}\left({b}\right)\bmod{2}, \dots, \alpha_{p_h}\left ({b}\jobbra)\bmod{2}}\jobbra)$ .
Ismételje meg a számgenerálási eljárást , amíg -sima számokat nem talál . $b$ $h+1$ $\mathrm{B}$ $b_1,...,b_{h+1}$
A Gauss-módszerrel keressen lineáris összefüggést a vektorok között : $\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$ és tedd: $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) } \jobbra) \over{2}}\bmod{n}$ .
Ellenőrizze . Ha igen, ismételje meg a generálási eljárást. Ha nem, akkor egy nem triviális dekompozíciót találunk: $x \equiv \pm y \pmod{n}$ $n=u\cdot v,u=gcd\left({x+y,n}\right),v=gcd\left({xy,n}\right).$

A helyesség igazolása [4]

Ahhoz, hogy a képlet helyes legyen, az összegnek párosnak kell lennie. Bizonyítsuk be: $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}$ abból következik, hogy: $x^2 = b_{i_1}^2 \pontok 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) }}$

Példa

Tényezőzzük a számot . $n=89755$

L(89755) = 194,174...

M = 13,934...

\Béta = \left\{ 2, 3, 5, 7, 11, 13 \jobbra\}

Az összes talált szám a megfelelő vektorokkal együtt be van írva a táblázatba. $b$ ${\vec {\alpha }}(b)$

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

Lineáris egyenletrendszert megoldva azt kapjuk, hogy . Akkor $\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}

Következésképpen,

u=gcd(86660,89755)=3095

v=gcd(83636,89755)=29

Kiderült, bomlás $89755 = 3095\cdot 29$

Számítási összetettség [5]

Jelölje az egész számok számát úgy, hogy és egy -sima szám, ahol . A de Bruijn-Erdős tételből , ahol . Ez azt jelenti, hogy minden -sima szám átlagosan próbálkozásból származik. Annak ellenőrzéséhez, hogy egy szám -sima-e, osztásokat kell végrehajtani . Az algoritmus szerint egy -sima számot kell találni. Tehát a számok megtalálásának számítási bonyolultsága $\Psi(n, M)$ $a$ $1 < a \leqslant n$ $a$ $\mathrm{B}$ $\Béta = \{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\bal({u^{u}\cdot h^{2}}\jobb)

A Gauss-módszer számítási összetettsége egyenletekből $h$

T_2 = O\bal({h^3}\jobb)

Ezért a Dixon-algoritmus teljes összetettsége

T = T_1 + T_2 = O\bal({u^{u}\cpont h^{2}+h^{3}}\jobb)

Figyelembe véve, hogy a prímszámok száma kisebb a képlet által becsültnél , és egyszerűsítés után azt kapjuk, hogy $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})\jobb )

$M$ úgy van megválasztva, hogy az minimális legyen. Aztán kicserélve kapjuk $T$ $L\left({n}\right)=\exp{\left({\sqrt{\ln{n}\cdot \ln{\ln{n))))\jobbra)}$

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

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

Pomeranz becslése a de Bruijn-Erdös tételnél szigorúbb tétel alapján [6] ad , míg Dixon eredeti komplexitásbecslése . $T = O\bal({L\bal({n}\jobb)}^{2}\jobb)$ $T=O\left({L\left({n}\right)}^{3{\sqrt {2))}\jobbra)$

További stratégiák [7]

Fontolja meg a további stratégiákat, amelyek felgyorsítják az algoritmus működését.

LP stratégia

Az LP (Large Prime Variation) stratégia nagy prímszámokat használ a számgenerálási eljárás felgyorsítására . $b$

Algoritmus

Legyen a 4. pontban talált szám ne -sima. Ekkor ábrázolható ahol nem osztható számokkal a faktoralapból. Nyilvánvaló, hogy . Ha járulékosan , akkor s prím, és bevesszük a faktorbázisba. Ez lehetővé teszi további -sima számok megtalálását, de 1-gyel növeli a szükséges sima számok számát. Az 5. lépés után az eredeti faktoralaphoz való visszatéréshez tegye a következőket. Ha csak egy szám található, melynek bővítése páratlan mértékben szerepel, akkor ezt a számot törölni kell a listából és törölni kell a faktorbázisból. Ha például két ilyen szám van és , akkor ezeket át kell húzni, és a számot hozzá kell adni . A mutató egyenletes mértékben lép be a bővülésbe , és hiányzik a lineáris egyenletrendszerből. $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}$

A stratégia variációja

Az LP stratégia több, a faktorbázisban nem szereplő prímszámmal is használható. Ebben az esetben a gráfelméletet a további prímszámok kizárására használják .

Számítási összetettség

Az LP stratégiát használó algoritmus bonyolultságának Pomerants által készített elméleti becslése nem tér el a Dixon algoritmus eredeti verziójának becslésétől:

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

EAS stratégia

Az EAS (korai szünet) stratégia kiküszöböl néhány szempontot azáltal, hogy nem tölti ki a simasági tesztet . $b$ $a$

Algoritmus

fixeket választanak . A Dixon-algoritmusban próbaosztással faktorizálják a -val . A stratégiában az EAS-t választjuk , és a számot először próbaosztással faktorizáljuk -vel , és ha a felbontatlan rész nagyobb marad, mint , akkor az adott eldobásra kerül. $0 < k, l, m < 1$ $a$ $p < M = L\left({n}\right)^{\frac{1}{2}}$ $M = L\bal({n}\jobb)^{k}$ $p < M^l = L\bal({n}\jobb)^{kl}$ $n^{1-m}$ $b$

A stratégia variációja

Lehetőség van több töréses EAS-stratégia használatára, azaz bizonyos növekvő és csökkenő sorozatokkal . $l_j$ $m_{j}$

Számítási összetettség

Megbecsülik a Dixon-féle algoritmust az EAS stratégiát használva $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))}\jobb)

PS stratégia

A PS-stratégia a Pollard-Strassen algoritmust használja , amely megkeresi a gcd - k számának minimális prímosztóját . [nyolc] $z, t \in \mathbb{N}$ $y=z^2$ $(t, y!)$ $O\left(z \cdot \ln^2{z} \cdot \ln^2{t}\jobbra)$

Algoritmus

A Fix ki van választva . A Dixon-algoritmusban próbaosztással faktorizálják a -val . A PS stratégiában . hiszünk . Alkalmazzuk a Pollard-Strassen algoritmust, a fel nem bontott részre választva a kiterjesztést kapjuk . $0<k<1$ $a$ $p < M = L\left({n}\right)^{\frac{1}{2}}$ $M = L\bal({n}\jobb)^{k}$ $z = [L\left({n}\right)^{\frac{k}{2}}] + 1, y = z^2 \geqslant L\left({n}\right)^{k}, t = a$ $t$ $a$

Számítási összetettség

A Dixon-algoritmus összetettsége PS stratégiával minimális és egyenlő $k = \frac{1}{\sqrt{3))$

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

Jegyzetek

↑ Ismukhametov, 2011 , p. 115.
↑ Dixon, J.D.Egész számok aszimptotikusan gyors faktorizálása // Math . Összeg. : folyóirat. - 1981. - 1. évf. 36 , sz. 153 . - P. 255-260 . - doi : 10.1090/S0025-5718-1981-0595059-1 . — .
↑ Cserjomuskin, 2001 , p. 77-79.
↑ Vasilenko, 2003 , p. 79.
↑ Cserjomuskin, 2001 , p. 79-80.
↑ C. Pomerance. Néhány egészszámú faktorálási algoritmus elemzése és összehasonlítása // HW Lenstra és R. Tijdeman, szerk., Computational Methods in Number Theory, Math Center Tracts – Part 1. Math Centrum, Amsterdam: Cikk. - 1982. - S. 89-139 . Archiválva az eredetiből 2021. november 6-án.
↑ Vasilenko, 2003 , p. 81-83.
↑ Cserjomuskin, 2001 , p. 74-75.

Irodalom

Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában . — M .: MTsNMO , 2003. — S. 78-83. — 328 p. — ISBN 5-94057-103-4 . Archiválva 2007. január 27-én a Wayback Machine -nél
Cheremushkin AV Előadások a kriptográfiai aritmetikai algoritmusokról . - M. : MTSNMO , 2001. - S. 74-80. — 104 p. — ISBN 5-94057-060-7 . Archiválva : 2013. május 31. a Wayback Machine -nél
Ishmukhametov Sh. T. Faktorizációs módszerek természetes számokhoz: oktatóanyag . - Kazan: Kazan. un., 2011. - S. 115-117. — 190 p.