P−1 Pollardova metoda

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é 4. dubna 2019; kontroly vyžadují 2 úpravy .

$p-1$ Pollardova metoda je jednou z celočíselných metod faktorizace .

Poprvé publikoval britský matematik John Pollard v roce 1974 [1] . Právě vzhled tohoto algoritmu vedl [2] ke změně v pojetí silného prvočísla používaného v kryptografii , volně řečeno prvočísla , pro které má dostatečně velké dělitele. V moderních kryptosystémech se snaží [2] používat silná prvočísla, protože to zvyšuje bezpečnost použitých algoritmů a systémů jako celku. $p-1$

Definice a matematické pozadí

Číslo se nazývá - power- smooth [3] , pokud všichni jeho prvočíslí dělitelé v mocninách, ve kterých jsou zahrnuti v rozšíření tohoto čísla , splňují . Podle Fermatovy malé věty pro jakékoli prvočíslo a pro jakékoli celé číslo takové, že a jsou coprime , nebo, což je v tomto případě ekvivalentní, nedělí , máme: $B$ ${\displaystyle p^{\nu ))$ $p^{\nu }\leq B$ $p$ $A$ $A$ $p$ $p$ $A$

a^{(p-1)}\equiv 1\mod p

, navíc .

\forall M=(p-1)l,l\in N\Rightarrow a^{M}\equiv 1\mod p

Původní algoritmus (1974)

John Pollard poprvé publikoval níže popsaný algoritmus ve svém článku „Theorems of Factorization and Primality Testing“ z roku 1974 v časopise Proceedings of the Cambridge Philosophical Society [ 1] . Článek je věnován teoretickému odhadu složitosti faktorizace velkého čísla nebo, v případě prvočísla , jeho kontrole pro jednoduchost. Následující algoritmus byl důsledkem a ilustrací Pollardových teoretických výpočtů. $N$ $N$

První etapa

Úkolem je najít vlastního dělitele jiného čísla než jedničky. Nejprve musíte vybrat dvě čísla taková, aby . $N$ $B,M,$ $1<B<M<{\sqrt {N)),M<B^{2}$
Vypočítejme nyní číslo , kde jsou všechna prvočísla menší než . Zde je povolena určitá volnost ve výběru , , ale je jisté, že pro malé , by mělo být větší než jedna [1] . $M(B)=\prod _{k=1}^{m}p_{k}^{c_{k}}$ $p_{k}$ $B$ $c_{k}$ $p_{k}$ $c_{k}$
Zvolíme malé celé číslo a spočítáme $a>1$

b=a^{M(B)}\mod N

q=(b-1,N)

pokud jsme našli dělitele , jinak přejdeme do druhé fáze.

q\neq 1

N

Druhá fáze

V tomto kroku je nutné vypočítat sekvenci

F_{m}\equiv b^{m-1}-1\mod N,

kde je prvočíslo, doufat, že v nějakém kroku se dostaneme

m

B<m<M

g_{m}=(F_{m},N)>1

Nejjednodušší způsob [1] , jak to udělat, je vypočítat pro každé liché číslo vynásobením číslem , přičemž v pravidelných intervalech. Pokud je dělitel nalezen. Pokud , pak je nutné tuto oblast prostudovat přesněji. $b^m$ $m$ $b^{2}$ $G_{i}=(b^{i},N)$ $1<G_{i}<N$ $G_{i}=N,G_{i-1}=1$

Poznámka

Pomocí této metody budeme schopni najít pouze takové prvotřídní dělitele čísla, pro které platí [1] : $p$ $N$

p-1=A

nebo , kde je -power-smooth a je prvočíslo takové, že [1] .

p-1=Aq

A

B

q

B<q<M

Moderní verze

Tato revidovaná verze algoritmu oproti originálu využívá koncepty power-law smoothness a je zaměřena na praktické aplikace. První stupeň doznal výrazných změn, zatímco druhý zůstal prakticky beze změn, opět z teoretického hlediska nepřibylo nic podstatného oproti předchozí verzi. Je to níže uvedený algoritmus, který je míněn, když lidé mluví o "Pollardově metodě" [4] [5] .

První etapa

Nechte -vyhladit moc a je potřeba najít dělitele čísla . Nejprve se vypočítá počet, kde je součin proveden přes všechna prvočísla v maximálních výkonech $N$ $B$ $N$ $M(B)=\prod _{i}p_{i}^{k_{i))$ $p_{i}$ $k_{i}:p_{i}^{k_{i}}<B$
Potom požadovaný dělitel [4] , kde . $q=(b-1,N)$ $b=a^{M(B)}\mod N$

Existují dva možné případy, kdy výše uvedený algoritmus selže [5] .

V případě, kdy lze s jistotou říci, že y má dělitele, který je -hladká mocnina a jiná volba musí problém vyřešit . $(b-1,N)=N$ $n$ $B$ $A$
V častějším případě, kdy stojí za to přejít na druhou fázi algoritmu, což výrazně zvyšuje pravděpodobnost výsledku, i když to nezaručuje. $(b-1,N)=1$

Příklad

Vyberme si tedy , vezměme a spočítejme nyní a nakonec . $N=10001$ $B=10$ $M(B)=2^{3}\cdot 3^{2}\cdot 5\cdot 7=2520$ $a=2$ $b=a^{M(B)}\mod N=2^{2520}\mod 10001=3578$ $(b-1,N)=(3578-1,10001)=73$

Poznámky

U velkých čísel se číslo může ukázat jako velmi velké, srovnatelné s hodnotou , v takových případech může být vhodné faktorizovat přibližně stejnou hodnotu a vypočítat posloupnost $B$ $M(B)$ $B!$ $M(B)$ ${\displaystyle M(B)=\prod _{i}M_{i))$

a_{1}=a^{M_{1}}\mod N;

a_{k+1}=a_{k}^{M_{k+1}}\mod N

Druhá fáze

Nejprve musíte opravit hranice , obvykle [5] [4] . $B_{1}=B,B_{2}\gg B$ $B_{2}\leq B^{2}$
Druhá fáze algoritmu najde dělitele , takové, že , kde je mocnina -hladká a prvočíslo takové, že . $N$ $p-1=q\cdot A$ $A$ $B$ $q$ ${\displaystyle B_{1}<q<B_{2))$

K tomu, co následuje, budeme potřebovat vektor prvočísel od do , ze kterého lze snadno získat vektor rozdílů mezi těmito prvočísly , navíc jde o relativně malá čísla a , kde je konečná množina [4] . Pro urychlení chodu algoritmu je užitečné si vše předem spočítat [4] a použít hotové hodnoty. $Qi}$ $B_1$ $B_{2}$ ${\displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i))$ $D_{i}$ $D_{i}\in \Delta$ $\Delta$ $b^{\delta _{i)),\forall \delta _{i}\in \Delta$
Nyní je nutné postupně vypočítat , kde , počítáno v první fázi, počítáno v každém kroku . Jakmile , můžete přestat počítat. $c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i))\mod N$ $b_{1}=a^{M(B_{1})}\mod N$ $G=(c_{i}-1,N)$ $G\neq 1$

Podmínky konvergence

Nechť nejmenší dělitel , maximum přebírá všechny mocniny dělení [4] . $p$ $N$ $q^{t}=max(q_{i}^{t_{i)))$ $q_{i}^{t_{i))$ $p-1$
- Jestliže , pak bude dělitel nalezen v první fázi algoritmu
[4] . ${\displaystyle q^{t}<B_{1))$
V opačném případě je pro úspěch algoritmu nutné, aby , a všechny ostatní dělitele tvaru byly menší než [4] . ${\displaystyle q^{t}<B_{2))$ $p-1$ ${\displaystyle q^{r))$ $B_1$

Úpravy a vylepšení

Později sám Pollard vyjádřil názor na možnost urychlení algoritmu pomocí rychlé Fourierovy transformace [4] ve druhé fázi, ale neuvedl skutečné způsoby, jak toho dosáhnout [6] .
Ještě později, v roce 1990, to dokázali matematici Peter Montgomery a Robert Silverman [6] . Autorům se podařilo dosáhnout zvýšení rychlosti provádění druhé fáze algoritmu.

Hodnocení výkonu

Složitost prvního stupně odhadneme jako , ponecháme pouze člen nejvyššího řádu, získáme odhad prvního stupně algoritmu [4] . $O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ $O(B\cdot \ln B\cdot (\ln N)^{2})$
Podle Montgomeryho odhadu je složitost druhého stupně až po termíny nejvyššího řádu [1] [4] , kde je počet prvočísel menší než . Čebyševův odhad dává přibližnou rovnost . $O(\pi (B_{2}))$ $\pi(s)$ $s$ $\pi (s)\cca {\frac {s}{\ln s))$

Záznamy

V tuto chvíli (10. 10. 2016) se tři největší prvočíslí dělitele nalezené metodou P-1 skládají z 66, 64 a 59 desetinných míst [7] .

Počet číslic	p	Dělitel čísel	Nalezen kým	Při nálezu	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 = 2 2 3 5 7 17 23 31 163 401 617 4271 13681 22877 43397 203459 1396027 6995393 13456591 2117 +401281	$960^{119}-1$	T. Nogara	29.06.2006	$10^{8}$	$10^{{10}}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 3 11 1187 9233729 13761367 43294577 51593573 100760321 379192511 2282985164293 + 1	$10^{243}-4\cdot 10^{121}-1$	M. Tervuren	13.09.2012	$10^{{9}}$	$10^{13}$
59	12798830540286697738097001413455268308836003073182603569933 = 2 2 17 59 107 113 20414117 223034797 269477639 439758239 481458247 1015660517 + 1	$8069000260399979023963141^{17}-1$	A. Krupp	30.06.2011	$10^{9}$	$10^{{10}}$

Aplikace

GMP-ECM [8] - balíček obsahuje efektivní aplikaci -metody. $p-1$
Prime95 a MPPrime, oficiální klienti GIMPS , používají metodu k vyřazení kandidátů.

Viz také

Poznámky

↑ 1 2 3 4 5 6 7 Pollard, 1974 .
↑ 1 2 Karaarslan E. Techniky testování primality a význam prvočísel v bezpečnostních protokolech // ICMCA'2000 : Sborník z Třetího mezinárodního sympozia Matematické a výpočetní aplikace - Konya : 2000. - S. 280-287.
↑ Vasilenko, 2003 , s. 60.
↑ 1 2 3 4 5 6 7 8 9 10 11 Ishmukhametov, 2011 , str. 53-55.
↑ 1 2 3 Cohen, 2000 , str. 439.
↑ 1 2 Montgomery, Silverman, 1990 .
↑ Zimmerman, Paul . Faktory záznamu nalezené Pollardovou metodou p- 1 . Les pages des staffs du LORIA et du Centre Inria NGE. Získáno 10. října 2016. Archivováno z originálu 11. října 2016.
↑ InriaForge: GMP-ECM (Metoda eliptické křivky): Domovská stránka projektu . Získáno 15. listopadu 2012. Archivováno z originálu dne 21. července 2012. (neurčitý)

Literatura

Pollard J. M. Theorems on factorization and primality testing (anglicky) // Mathematical Proceedings of the Cambridge Philosophical Society / B. J. Green - Cambridge University Press , 1974. - Vol. 76, Iss. 3. - S. 521-528. - 8p. — ISSN 0305-0041 ; 1469-8064 – doi:10.1017/S0305004100049252
Cohen A. A Course in Computational Algebraic Number Theory - 4th Print Edition - Berlin , Heidelberg , New York : Springer , 2000. - 550 s. - ( Absolventské texty z matematiky ) - ISBN 978-3-540-55640-4 - ISSN 0072-5285 ; 2197-5612
Vasilenko O. N. Číselné teoretické algoritmy v kryptografii - M. : MTsNMO , 2003. - 328 s. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Faktorizační metody pro přirozená čísla : učebnice - Kazan : Kazan University , 2011. - S. 53-55. — 190 str.
Montgomery P. , Silverman R.D. Rozšíření FFT faktoringového algoritmu P-1 // Math . Comp. - AMS , 1990. - Sv. 54, Iss. 190. - S. 839-854. — ISSN 0025-5718 ; 1088-6842 – doi:10.1090/S0025-5718-1990-1011444-3