P+1-Williams metod

$p+1$ Williams -metoden är en metod för att faktorisera tal med hjälp av Lucas talsekvenser , utvecklad av Hugh Williams 1982. Algoritmen hittar en primtalsdelare av talet . Liknar Pollards -metod , men använder faktorisering av ett tal . Den har bra prestandaindikatorer endast i de fall då det är lätt att faktorisera. Som regel genomförs det inte ofta i praktiken på grund av den låga andelen sådana fall [1] . $N\in \mathbb {N}$ $sid$ $n$ $p-1$ $p+1$ $p+1$

Lucas nummersekvenser

För ytterligare beräkningar måste vi introducera sekvenser av Lucas-tal och lista några av deras egenskaper.

Låt och vara några fasta heltal. Lucas nummersekvenser definieras som [1] : $P$ $F$

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

Låt också $\Delta =P^{2}-4Q.$

Sekvenser har följande egenskaper:

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

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

För att bevisa dessa egenskaper, överväg de explicita formlerna för sekvensen av Lucas-tal :

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

och

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

var och är rötterna till det karakteristiska polynomet $\alfa$ $\beta$

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

Använd explicita formler och Viettes sats :

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

vi får uttryck och $(1),(2),(3),(4)$ $(5).$

Därefter lyfter vi fram ytterligare en egenskap:

Om GCD och sedan: och varifrån $(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)

Och slutligen formulerar vi teoremet:

Om p är ett udda primtal och Legendre-symbolen är , då:

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)

Beviset för detta teorem är mödosamt, och det kan hittas i boken av D. G. Lemer [2] .

Det första steget i algoritmen

Låt vara en primtalsdelare av ett faktoriserbart tal , och expansionen utförs: $sid$ $N$

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

var finns primtal. $q_{i}$

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

Låt oss introducera ett nummer där examina är valda på ett sådant sätt att $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 .$

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

Vidare, enligt satsen, om gcd då $(T1),$ $(N,Q)=1,(\Delta /p)=-1,$ $p|U_{R}(P,Q).$

Och därför hittas GCD , det vill säga divisorn för det önskade talet [1] . $p|$ $(U_{R}(P,Q),N),$ $N$

Det är värt att notera att siffrorna inte är kända i det inledande skedet av problemet. Därför, för att förenkla uppgiften, kommer vi att göra följande: sedan dess av egenskap (2) Därefter använder vi egenskap (6) och får: $P,Q,p$ $p|U_{R}(P,Q),$ $p|U_{2R}(P,Q).$ $p|U_{R}(P^{\prime },1).$

Således, utan förlust av allmänhet, kan vi hävda att [1] $Q=1.$

Därefter använder vi satsen från vilken vi drar slutsatsen att $(T1),$

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

Och därför [1] $p|(V_{R}(P,1)-2).$

Välj nu något nummer så att gcd $P$ $(P^{2}-4,N)=1;$

Vi utser:

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

Slutligen måste du hitta GCD [1] $(V_{R}(P)-2,N).$

För att söka , fortsätt enligt följande [1] : $V_{R}(P)$

1) bryts ner till binär form: där . $R$ $R=\sum _{i=0}^{t}b_{i}2^{ti},$ $b_{i}=0.1$

2) vi introducerar en sekvens av naturliga tal . Samtidigt ; ${\displaystyle \{f_{n}\}:f_{0}=1;f_{k+1}=2f_{k}+b_{k+1))$ $f_{t}=R$

3) vi letar efter värdepar enligt följande regel: $(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}),när\quad b_{k+1}=0;\\(V_{2f_{k}+1},V_{2f_{k}}),när\quad b_{k+1} =1\end{matris}}\right.

vart i

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

4) värden söks enligt reglerna (som följer av egenskaperna och definitionen av sekvensen av Lucas-nummer ): $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{matris}}\ höger.

För standardvärden, det vill säga vi får resultatet: $N=451889,R=2520,P=6$

374468

Låt oss kontrollera detta värde. För att göra detta överväger vi GCD GCD och . $(V_{R}(P)-2,N)=$ $(374468-2.451889)=139$ $\quad 451889\vdots 139$

Om vi utan framgång valde nummer i det första steget , det vill säga det visade sig att GCD , måste vi gå vidare till det andra steget. I annat fall är arbetet avslutat [1] . $R,P$ $(V_{R}(P)-2,N)=1$

Det andra steget i algoritmen

Låt talet ha någon primtalsdelare större än men mindre än några , det vill säga: $p+1$ $s$ $B$ $B_{2}$

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

, var

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

Ange en sekvens av primtal . ${\displaystyle \{s_{j}:B<s_{j}\leq B_{2}\quad \forall j=1,2,...,k\))$

Vi introducerar en annan sekvens: ${\displaystyle \{d_{j}:2d_{j}=s_{j+1}-s_{j}\quad \forall j=1,2,...,k-1\))$

Därefter definierar vi:

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

Med hjälp av egenskapen får vi de första elementen: $(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{matris}}\right.

Därefter använder vi fastigheten och får: $(fyra)$

\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{matrix}}\right.

Så räknar vi $T[s_{i}],\forall i=1,2,\ldots ,k$

Därefter överväger vi:

H_{t}=

GCD för

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

t=1,2,\ldots ,k

Så fort vi får stoppar vi beräkningarna [1] . $H_{t}\neq 1$

För standardvärden, det vill säga vi får resultatet: $N=451889,B=10,B_{2}=50,P=7$

139,

vilket är det rätta svaret.

Hastighetsjämförelse

Författaren till denna metod genomförde tester och metoder på AMDAHL 470-V7-maskinen på 497 olika nummer, vilket visade att det första steget i algoritmen i genomsnitt är ungefär 2 gånger långsammare än det första steget i algoritmen , och det andra steget är cirka 4 gånger långsammare [1] . $p-1$ $p+1$ $p+1$ $p-1$

Applikation

På grund av att faktoriseringsmetoden är snabbare används -metoden sällan i praktiken [1] . $p-1$ $p+1$

Records

För tillfället (14 december 2013) består de tre största primtalsdivisorerna [3] som hittas av metoden av 60, 55 och 53 decimalsiffror. $P+1$

Antal siffror	sid	Nummerdelare	Hittade (av vem)	Hittade (när)	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	2011-05-16	$10^{{9}}$	$10^{13}$
53	60120920503954047277077441080303862302926649855338567	$682\cdot 5^{682}-1$	P. Leyland	26.02.2011	$10^{8}$	$10^{12}$

Här är den 2366:e medlemmen i Lucas nummersekvens. $L_{2366}$

Anteckningar

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982 .
↑ Lehmer, 1930 .
↑ Rekordfaktorer hittade av p+1-metoden . Datum för åtkomst: 13 december 2013. Arkiverad från originalet 18 december 2013. (obestämd)

Litteratur

Williams HC En p+1-metod för faktorisering = En p+1-metod för faktorisering // American Mathematical Society. - 1982. - T. 39 , nr. 159 . - S. 225-234 . — ISSN 00255718 .
D.H. Lehmer. An extended theory of Lucas' functions (engelska) = An extended theory of Lucas' functions // Ann. of Math.. - 1930. - V. 31 , nr. 2 . - S. 419-448 .
Ishmukhametov Sh. T. Metoder för faktorisering av naturliga tal: Lärobok . - Kazan: Kazan University, 2011. - S. 60-61. — 190 sid.

Länkar

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