P+1-metoda Williams

$p+1$ Metoda Williams este o metodă de factorizare a numerelor folosind secvențe de numere Lucas , dezvoltată de Hugh Williams în 1982. Algoritmul găsește un divizor prim al numărului . Similar cu metoda lui Pollard , dar folosește factorizarea unui număr . Are indicatori buni de performanță doar în cazul în care este ușor de factorizat. De regulă, acesta nu este adesea implementat în practică din cauza procentului scăzut de astfel de cazuri [1] . $N\in \mathbb {N}$ $p$ $n$ $p-1$ $p+1$ $p+1$

secvențe de numere Lucas

Pentru calcule suplimentare, trebuie să introducem secvențe de numere Lucas și să enumerăm câteva dintre proprietățile lor.

Fie și să fie niște numere întregi fixe. Secvențele de numere Lucas sunt definite ca [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

Lasa si $\Delta =P^{2}-4Q.$

Secvențele au următoarele proprietăți:

\left\{{\begin{matrix}U_{2n}=V_{n}\cdot U_{n},\\V_{2n}=V_{n}^{2}-2Q_{n}^ {2}\end{matrice}}\dreapta.\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{matrice}}\dreapta.\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{matrice}}\dreapta.\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{matrice}}\right.\quad ( patru)

\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{matrice}}\dreapta.\quad ( 5)

Pentru a demonstra aceste proprietăți, luați în considerare formulele explicite pentru șirul numerelor Lucas :

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

și

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

unde și sunt rădăcinile polinomului caracteristic $\alfa$ $\beta$

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

Folosind formule explicite și teorema lui Viette :

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

primim expresii și $(1),(2),(3),(4)$ $(5).$

În continuare, evidențiem încă o proprietate:

Dacă GCD și apoi: și de unde $(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)

Și, în final, formulăm teorema:

Dacă p este un număr prim impar și simbolul Legendre este , atunci:

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{matrice}}\right.\quad (T1)

Demonstrarea acestei teoreme este laborioasă și poate fi găsită în cartea lui D. G. Lemer [2] .

Primul pas al algoritmului

Fie un divizor prim al unui număr factorizabil , iar expansiunea se realizează: $p$ $N$

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

unde sunt numere prime. $q_{i}$

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

Să introducem un număr în care gradele sunt alese în așa fel încât $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 .$

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

În plus, conform teoremei, dacă gcd atunci $(T1),$ $(N,Q)=1,(\Delta /p)=-1,$ $p|U_{R}(P,Q).$

Și, prin urmare, GCD , adică divizorul numărului dorit [1] se găsește . $p|$ $(U_{R}(P,Q),N),$ $N$

Este de remarcat faptul că numerele nu sunt cunoscute în stadiul inițial al problemei. Prin urmare, pentru a simplifica sarcina, vom face următoarele: de atunci prin proprietatea (2) În continuare, folosim proprietatea (6) și obținem: $P,Q,p$ $p|U_{R}(P,Q),$ $p|U_{2R}(P,Q).$ $p|U_{R}(P^{\prime },1).$

Astfel, fără pierderi de generalitate, putem afirma că [1] $Q=1.$

În continuare, folosim teorema din care concluzionăm că $(T1),$

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

Și prin urmare [1] $p|(V_{R}(P,1)-2).$

Acum alegeți un număr astfel încât gcd $P$ $(P^{2}-4,N)=1;$

Noi desemnam:

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

În cele din urmă, trebuie să găsiți GCD [1] $(V_{R}(P)-2,N).$

Pentru a căuta , procedați după cum urmează [1] : $V_{R}(P)$

1) se descompune în formă binară: unde . $R$ $R=\sum _{i=0}^{t}b_{i}2^{ti},$ $b_{i}=0,1$

2) introducem o succesiune de numere naturale . În același timp ; ${\displaystyle \{f_{n}\}:f_{0}=1;f_{k+1}=2f_{k}+b_{k+1))$ $f_{t}=R$

3) căutăm perechi de valori conform următoarei reguli: $(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}), când\quad b_{k+1}=0;\\(V_{2f_{k}+1},V_{2f_{k}}),când\quad b_{k+1} =1\end{matrice}}\dreapta.

în care

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

4) valorile sunt căutate conform regulilor (care decurg din proprietățile și definiția succesiunii de numere Lucas ): $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}}\ dreapta.

Pentru valorile implicite, adică, obținem rezultatul: $N=451889,R=2520,P=6$

374468

Să verificăm această valoare. Pentru a face acest lucru, luăm în considerare GCD GCD și . $(V_{R}(P)-2,N)=$ $(374468-2.451889)=139$ $\quad 451889\vdots 139$

Dacă am ales fără succes numere în primul pas , adică s-a dovedit că GCD , atunci trebuie să trecem la al doilea pas. În caz contrar, lucrarea este finalizată [1] . $R,P$ $(V_{R}(P)-2,N)=1$

Al doilea pas al algoritmului

Fie ca numărul să aibă un divizor prim mai mare decât unii, dar mai mic decât unii , adică: $p+1$ $s$ $B$ $B_{2}$

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

, Unde

B<s\leq B_{2)

Introduceți o succesiune de numere prime . $\{s_{j}:B<s_{j}\leq B_{2}\quad \forall j=1,2,...,k\)$

Introducem o altă secvență: $\{d_{j}:2d_{j}=s_{j+1}-s_{j}\quad \forall j=1,2,...,k-1\)$

În continuare, definim:

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

Folosind proprietatea , obținem primele elemente: $(5)$

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

Apoi, folosim proprietatea și obținem: $(patru)$

\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]\equiv T[s_{i}]U[2d_{i}]-T[s_{i}-1] U[2d_{i}-1]\mod N\end{matrice}}\right.

Astfel calculăm $T[s_{i}],\forall i=1,2,\ldots ,k$

În continuare, luăm în considerare:

H_{t}=

GCD pentru

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

t=1,2,\ldots ,k

Imediat ce ajungem la , oprim calculele [1] . $H_{t}\neq 1$

Pentru valorile implicite, adică, obținem rezultatul: $N=451889,B=10,B_{2}=50,P=7$

139,

care este răspunsul corect.

Comparația vitezei

Autorul acestei metode a efectuat teste și metode pe mașina AMDAHL 470-V7 pe 497 de numere diferite, ceea ce a arătat că, în medie, primul pas al algoritmului este de aproximativ 2 ori mai lent decât primul pas al algoritmului , iar al doilea pasul este de aproximativ 4 ori mai lent [1] . $p-1$ $p+1$ $p+1$ $p-1$

Aplicație

Datorită faptului că metoda de factorizare este mai rapidă, metoda - este rar folosită în practică [1] . $p-1$ $p+1$

Înregistrări

În prezent (14 decembrie 2013), cei mai mari trei divizori primi [3] găsiți prin metodă constau din 60, 55 și 53 de cifre zecimale. $P+1$

Numărul de cifre	p	Divizor de număr	Găsit (de cine)	Găsit (când)	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}$

Iată al 2366-lea membru al secvenței de numere Lucas. $L_{2366}$

Note

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982 .
↑ Lehmer, 1930 .
↑ Înregistrați factorii găsiți prin metoda p+1 . Data accesului: 13 decembrie 2013. Arhivat din original la 18 decembrie 2013. (nedefinit)

Literatură

Williams HC A p+1 method of factoring = A p+1 method of factoring // American Mathematical Society. - 1982. - T. 39 , nr. 159 . - S. 225-234 . — ISSN 00255718 .
D. H. Lehmer. O teorie extinsă a funcțiilor lui Lucas (engleză) = An extended theory of Lucas' functions // Ann. de Matematică.. - 1930. - V. 31 , nr. 2 . - S. 419-448 .
Ishmukhametov Sh. T. Metode de factorizare a numerelor naturale: Manual . - Kazan: Universitatea din Kazan, 2011. - S. 60-61. — 190 p.

Link -uri

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