P+1-Williamsova metoda

$p+1$ Williamsova metoda je metoda faktorizace čísel pomocí Lucasových číselných posloupností , kterou vyvinul Hugh Williams v roce 1982. Algoritmus najde prvočíselného dělitele čísla . Podobná Pollardově -metodě , ale používá faktorizaci čísla . Má dobré ukazatele výkonnosti pouze v případě, že je snadné faktorizovat. Zpravidla není v praxi často zaváděn z důvodu nízkého procenta takových případů [1] . $N\in \mathbb {N}$ $p$ $n$ $p-1$ $p+1$ $p+1$

Lucas číselné řady

Pro další výpočty musíme zavést posloupnosti Lucasových čísel a uvést některé jejich vlastnosti.

Dovolit a být nějaká pevná celá čísla. Lucasovy číselné řady jsou definovány jako [1] : $P$ $Q$

U_{0}(P,Q)=0,\quad U_{1}(P,Q)=1,\quad U_{n+2}(P,Q)=P\cdot U_{n+ 1 }(P,Q)-Q\cdot U_{n}(P,Q),n\geq 0

V_{0}(P,Q)=2,\quad V_{1}(P,Q)=P,\quad V_{n+2}(P,Q)=P\cdot V_{n+ 1 }(P,Q)-Q\cdot V_{n}(P,Q),n\geq 0

Nechte také $\Delta =P^{2}-4Q.$

Sekvence mají následující vlastnosti:

\left\{{\begin{matrix}U_{2n}=V_{n}\cdot U_{n},\\V_{2n}=V_{n}^{2}-2Q_{n}^ {2}\end{matrix}}\right.\quad (1)

\left\{{\begin{matrix}U_{2n-1}=U_{n}^{2}-Q\cdot U_{n-1}^{2},\\V_{2n-1 }=V_{n}\cdot V_{n-1}-P\cdot Q^{n-1}\end{matrix}}\right.\quad (2)

\left\{{\begin{matrix}\Delta U_{n}=P\cdot V_{n}-2Q\cdot V_{n-1},\\V_{n}=P\cdot U_{ n}-2Q\cdot U_{n-1}\end{matrix}}\right.\quad (3)

\left\{{\begin{matrix}U_{n+m}=U_{m}\cdot U_{n+1}-Q\cdot U_{m-1}\cdot U_{n},\ \\Delta U_{n+m}=V_{m}\cdot V_{n+1}-Q\cdot V_{m-1}\cdot V_{n}\end{matrix}}\right.\quad ( čtyři)

\left\{{\begin{matrix}U_{n}(V_{k}(P,Q),Q^{k})=U_{nk}(P,Q)/U_{k}( P,Q),\\V_{n}(V_{k}(P,Q),Q^{k})=V_{nk}(P,Q)\end{matice}}\vpravo.\quad ( 5)

Chcete-li tyto vlastnosti prokázat, zvažte explicitní vzorce pro posloupnost Lucasových čísel :

U_{n}(P,Q)={\frac {\alpha ^{n}-\beta ^{n)){\alpha -\beta ))

V_{n}(P,Q)=\alpha ^{n}+\beta ^{n},

kde a jsou kořeny charakteristického polynomu $\alpha$ $\beta$

x^{2}-P\cdot x+Q

Použití explicitních vzorců a Viettovy věty :

P=\alpha +\beta ;\quad Q=\alpha \cdot \beta ,

dostáváme výrazy a $(1), (2), (3), (4)$ $(5).$

Dále zvýrazníme ještě jednu vlastnost:

Pokud GCD a pak: a odkud $(N,Q)=1\quad$ $P^{\prime }Q\equiv P^{2}-2Q\mod N,\quad$ $P^{\prime }\equiv \alpha /\beta +\beta /\alpha \quad$ $Q^{\prime }\equiv 1,\quad$

U_{2m}(P,Q)\equiv P\cdot Q^{m-1}\cdot U_{m}(P^{\prime },1)\mod N\quad (6)

A nakonec formulujeme větu:

Pokud je p liché prvočíslo a Legendreův symbol je , pak:

p\mid Q

\epsilon =(\Delta /p)

\left\{{\begin{matrix}U_{(p-\epsilon )m}(P,Q)\equiv 0\mod p,\\V_{(p-\epsilon )m}(P, Q)\equiv 2Q^{m(1-\epsilon )/2}\mod p\end{matrix}}\right.\quad (T1)

Důkaz této věty je pracný a lze jej nalézt v knize D. G. Lemera [2] .

První krok algoritmu

Nechť je prvočíslo dělitel faktorizovatelného čísla a rozšíření se provede: $p$ $N$

p+1=\prod _{i=1}^{k}q_{i}^{\alpha _{i)),

kde jsou prvočísla. $Qi}$

Nechat $B=\max\{q_{i}^{\alpha _{i}}|\forall i:1\leq i\leq k\}.$

Uveďme číslo , kde jsou stupně voleny tak, že $R=\prod _{i=1}^{k}q_{i}^{\beta _{i)),$ $\beta _{i}$ $q_{i}^{\beta _{i}}\leq B,q_{i}^{\beta _{i}+1}>B\quad \forall i:1\leq i\leq k .$

Potom [1] $p+1|R.$

Dále, podle věty, pokud gcd pak $(T1),$ $(N,Q)=1,(\Delta /p)=-1,$ $p|U_{R}(P,Q).$

A proto se najde GCD , tedy dělitel požadovaného čísla [1] . $p|$ $(U_{R}(P,Q),N),$ $N$

Stojí za zmínku, že čísla nejsou v počáteční fázi problému známa. Proto pro zjednodušení úlohy uděláme následující: od té doby podle vlastnosti (2) Dále použijeme vlastnost (6) a získáme: $P,Q,p$ $p|U_{R}(P,Q),$ $p|U_{2R}(P,Q).$ $p|U_{R}(P^{\prime },1).$

Bez ztráty obecnosti tedy můžeme tvrdit, že [1] $Q=1.$

Dále použijeme větu, ze které vyvozujeme, že $(T1),$

V_{(p-\epsilon )m}(P,1)\equiv 2\mod p;

A proto [1] $p|(V_{R}(P,1)-2).$

Nyní vyberte nějaké číslo , například gcd $P$ $(P^{2}-4,N)=1;$

Označujeme:

V_{n}(P)=V_{n}(P,1),\quad U_{n}(P)=U_{n}(P,1).

Nakonec musíte najít GCD [1] $(V_{R}(P)-2,N).$

Při hledání postupujte následovně [1] : $V_{R}(P)$

1) rozložit do binárního tvaru: kde . $R$ $R=\sum _{i=0}^{t}b_{i}2^{ti},$ $b_{i}=0,1$

2) zavedeme posloupnost přirozených čísel . Ve stejnou dobu ; ${\displaystyle \{f_{n}\}:f_{0}=1;f_{k+1}=2f_{k}+b_{k+1))$ $f_{t}=R$

3) hledáme dvojice hodnot podle následujícího pravidla: $(V_{f_{k+1)),V_{f_{k+1}-1})$

(V_{f_{k+1)),V_{f_{k+1}-1})=\left\{{\begin{matrix}(V_{2f_{k)),V_{2f_{ k}-1}),when\quad b_{k+1}=0;\\(V_{2f_{k}+1},V_{2f_{k}}),when\quad b_{k+1} =1\end{matrix}}\right.

kde

V_{0}(P)=2,V_{1}(P)=P

4) hodnoty se hledají podle pravidel (která vyplývají z vlastností a definice posloupnosti Lucasových čísel ): $V_{2f_{k}-1},V_{2f_{k)),V_{2f_{k}+1}$ $(1), (2)$

\left\{{\begin{matrix}V_{2f-1}\equiv V_{f}V{f-1}-P\mod N;\\V_{2f}\equiv V_{f}^ {2}-2\mod N;\\V_{2f+1}\equiv PV_{f}^{2}-V_{f}V_{f-1}-P\mod N\end{matrix}}\ že jo.

Pro výchozí hodnoty, to znamená, dostaneme výsledek: $N=451889,R=2520,P=6$

374468

Zkontrolujeme tuto hodnotu. K tomu uvažujeme GCD GCD a . $(V_{R}(P)-2,N)=$ $(374468-2.451889)=139$ $\quad 451889\vdots 139$

Pokud jsme v prvním kroku neúspěšně vybrali čísla , to znamená, že se ukázalo, že GCD , musíme přistoupit ke druhému kroku. V opačném případě je práce dokončena [1] . $R,P$ $(V_{R}(P)-2,N)=1$

Druhý krok algoritmu

Nechť číslo má nějakého prvočíselného dělitele většího , ale menšího než některé , to znamená: $p+1$ $s$ $B$ $B_{2}$

p=s\cdot (\prod _{i=1}^{k}q_{i}^{\alpha _{i)))-1

, kde

{\displaystyle B<s\leq B_{2))

Zadejte posloupnost prvočísel . ${\displaystyle \{s_{j}:B<s_{j}\leq B_{2}\quad \forall j=1,2,...,k\))$

Představujeme další sekvenci: ${\displaystyle \{d_{j}:2d_{j}=s_{j+1}-s_{j}\quad \forall j=1,2,...,k-1\))$

Dále definujeme:

T[s_{i}]\equiv \Delta U_{s_{i}R}(P)/U_{R}(P)\mod N

Pomocí vlastnosti získáme první prvky: $(5)$

\left\{{\begin{matrix}T[s_{1}]\equiv PV[s_{1}]-2V[s_{1}-1]\mod N;\\T[s_{1 }-1]\ekviv 2V[s_{1}]-PV[s_{1}-1]\mod N\end{matrix}}\vpravo.

Dále použijeme vlastnost a získáme: $(čtyři)$

\left\{{\begin{matrix}T[s_{i+1}]\equiv T[s_{i}]U[2d_{i}+1]-T[s_{i}-1] U[2d_{i}]\mod N,\\T[s_{i+1}-1]\ekviv T[s_{i}]U[2d_{i}]-T[s_{i}-1] U[2d_{i}-1]\mod N\end{matrix}}\vpravo.

Tak počítáme $T[s_{i}],\forall i=1,2,\ldots ,k$

Dále uvažujeme:

H_{t}=

GCD pro

(\prod _{i=1}^{t}T[s_{i}],N)

t=1,2,\ldots ,k

Jakmile dostaneme , zastavíme výpočty [1] . $H_{t}\neq 1$

Pro výchozí hodnoty, to znamená, dostaneme výsledek: $N=451889,B=10,B_{2}=50,P=7$

139,

což je správná odpověď.

Porovnání rychlosti

Autor této metody provedl testy a metody na stroji AMDAHL 470-V7 na 497 různých číslech, které ukázaly, že v průměru je první krok algoritmu asi 2krát pomalejší než první krok algoritmu a druhý krok krok je asi 4x pomalejší [1] . $p-1$ $p+1$ $p+1$ $p-1$

Aplikace

Vzhledem k tomu, že metoda faktorizace je rychlejší, je -metoda v praxi používána jen zřídka [1] . $p-1$ $p+1$

Záznamy

V tuto chvíli (14. prosince 2013) se tři největší prvočíselníci [3] nalezení touto metodou skládají z 60, 55 a 53 desetinných míst. $P+1$

Počet číslic	p	Dělitel čísel	Nalezeno (kdo)	Nalezeno (kdy)	B	B2
60	725516237739635905037132916171116034279215026146021770250523	$L_{2366}$	A. Kruppa P. Montgomery	31.10.2007	$10^{11}$	$10^{15}$
55	1273305908528677655311178780176836847652381142062038547	$782\cdot 6^{782}+1$	P. Leyland	16.05.2011	$10^{{9}}$	$10^{13}$
53	60120920503954047277077441080303862302926649855338567	$682\cdot 5^{682}-1$	P. Leyland	26.02.2011	$10^{8}$	$10^{12}$

Zde je 2366. člen Lucasovy číselné řady. $L_{2366}$

Poznámky

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982 .
↑ Lehmer, 1930 .
↑ Faktory záznamu nalezené metodou p+1 . Datum přístupu: 13. prosince 2013. Archivováno z originálu 18. prosince 2013. (neurčitý)

Literatura

Williams HC Metoda faktoringu p+1 = Metoda faktorizace p+1 // American Mathematical Society. - 1982. - T. 39 , no. 159 . - S. 225-234 . — ISSN 00255718 .
D. H. Lehmer. Rozšířená teorie Lucasových funkcí (anglicky) = Rozšířená teorie Lucasových funkcí // Ann. matematiky.. - 1930. - V. 31 , čís. 2 . - S. 419-448 .
Ishmukhametov Sh. T. Metody rozkladu přirozených čísel: Učebnice . - Kazaň: Kazaňská univerzita, 2011. - S. 60-61. — 190 str.

Odkazy

https://web.archive.org/web/20170222131210/http://www.mersennewiki.org/index.php/P_Plus_1_Factorization_Method