P+1-Williamsin menetelmä

$p+1$ Williamsin menetelmä on Hugh Williamsin vuonna 1982 kehittämä menetelmä lukujen laskemiseen Lucas - lukusarjoja käyttäen . Algoritmi löytää luvun alkujakajan . Samanlainen kuin Pollardin -menetelmä , mutta käyttää luvun tekijöitä . Sillä on hyvät suorituskykyindikaattorit vain siinä tapauksessa, että se on helppo jakaa. Käytännössä sitä ei yleensä oteta usein käyttöön tällaisten tapausten alhaisen prosenttiosuuden vuoksi [1] . $N\in \mathbb {N}$ $s$ $n$ $p-1$ $p+1$ $p+1$

Lucas-numerosarjat

Lisälaskelmia varten meidän on esitettävä Lucas-lukujonoja ja lueteltava joitakin niiden ominaisuuksia.

Olkoon ja joitain kiinteitä kokonaislukuja. Lucas- numerosarjat määritellään [1] : $P$ $K$

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

Anna myös $\Delta =P^{2}-4Q.$

Sekvensseillä on seuraavat ominaisuudet:

\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 ( neljä)

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

Todistaaksesi nämä ominaisuudet, harkitse eksplisiittisiä kaavoja Lucas-lukujen sarjalle :

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

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

missä ja ovat ominaispolynomin juuret $\alpha$ $\beeta$

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

Käyttämällä eksplisiittisiä kaavoja ja Vietten lausetta :

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

saamme ilmaisuja ja ${\näyttötyyli (1), (2), (3), (4)}$ $(5).$

Seuraavaksi korostamme vielä yhtä ominaisuutta:

Jos GCD ja sitten: ja mistä $(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)

Ja lopuksi muotoilemme lauseen:

Jos p on pariton alkuluku ja Legendre-symboli on , niin:

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)

Tämän lauseen todistaminen on työlästä, ja se löytyy D. G. Lemerin kirjasta [2] .

Algoritmin ensimmäinen vaihe

Antaa olla kertoimien luvun alkujakaja , ja laajennus suoritetaan: $s$ $N$

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

missä ovat alkuluvut. $q_{i}$

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

Esitetään luku , jossa asteet valitaan siten, että $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 .$

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

Lisäksi lauseen mukaan jos gcd niin ${\näyttötyyli (T1),}$ $(N,Q)=1,(\Delta /p)=-1,$ $p|U_{R}(P,Q).$

Ja siksi GCD , eli halutun luvun [1] jakaja löytyy . $p|$ ${\näyttötyyli (U_{R}(P,Q),N),}$ $N$

On syytä huomata, että numerot eivät ole tiedossa ongelman alkuvaiheessa. Siksi tehtävän yksinkertaistamiseksi teemme seuraavaa: siitä lähtien ominaisuudella (2) Seuraavaksi käytämme ominaisuutta (6) ja saamme: $P,Q,p$ $p|U_{R}(P,Q),$ $p|U_{2R}(P,Q).$ $p|U_{R}(P^{\prime },1).$

Näin ollen yleisyyttä menettämättä voimme väittää, että [1] $Q=1.$

Seuraavaksi käytämme lausetta , josta päättelemme sen ${\näyttötyyli (T1),}$

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

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

Valitse nyt jokin numero , kuten gcd $P$ ${\näyttötyyli (P^{2}-4,N)=1;}$

Nimeämme:

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

Lopuksi sinun on löydettävä GCD [1] ${\näyttötyyli (V_{R}(P)-2,N).}$

Tee haku seuraavasti [1] : $V_{R}(P)$

1) hajoaa binäärimuotoon: missä . $R$ $R=\sum _{i=0}^{t}b_{i}2^{ti},$ $b_{i}=0,1$

2) otamme käyttöön luonnollisten lukujen sarjan . Samaan aikaan ; ${\displaystyle \{f_{n}\}:f_{0}=1;f_{k+1}=2f_{k}+b_{k+1))$ $f_{t}=R$

3) etsimme arvopareja seuraavan säännön mukaisesti: ${\näyttötyyli (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\loppu{matriisi}}\oikea.

jossa

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

4) arvoja etsitään sääntöjen mukaan (jotka seuraavat Lucas -lukujonon ominaisuuksista ja määrittelystä ): $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}}\ oikein.

Oletusarvoille, eli saamme tuloksen: $N=451889,R=2520,P=6$

374468

Tarkastetaan tämä arvo. Tätä varten harkitsemme GCD GCD :tä ja . ${\näyttötyyli (V_{R}(P)-2,N)=}$ $(374468-2.451889)=139$ $\quad 451889\vdots 139$

Jos valitsimme epäonnistuneesti numerot ensimmäisessä vaiheessa , eli kävi ilmi, että GCD , meidän on edettävä toiseen vaiheeseen. Muuten työ on valmis [1] . $R,P$ $(V_{R}(P)-2,N)=1$

Algoritmin toinen vaihe

Olkoon luvulla jokin alkujakaja , joka on suurempi kuin mutta pienempi kuin jotkut , eli: $p+1$ $s$ $B$ $B_{2}$

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

, missä

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

Syötä alkulukujen sarja . ${\displaystyle \{s_{j}:B<s_{j}\leq B_{2}\quad \forall j=1,2,...,k\))$

Esittelemme toisen sarjan: ${\displaystyle \{d_{j}:2d_{j}=s_{j+1}-s_{j}\quad \forall j=1,2,...,k-1\))$

Seuraavaksi määrittelemme:

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

Ominaisuutta käyttämällä saamme ensimmäiset elementit: ${\näyttötyyli (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{matrix}}\right.

Seuraavaksi käytämme omaisuutta ja saamme: $(neljä)$

\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.

Näin laskemme $T[s_{i}],\forall i=1,2,\ldots ,k$

Seuraavaksi harkitsemme:

H_{t}=

GCD varten

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

t=1,2,\ldots ,k

Heti kun saamme , lopetamme laskelmat [1] . $H_{t}\neq 1$

Oletusarvoille, eli saamme tuloksen: $N=451889,B=10,B_{2}=50,P=7$

139,

mikä on oikea vastaus.

Nopeusvertailu

Tämän menetelmän kirjoittaja suoritti testejä ja menetelmiä AMDAHL 470-V7 -koneella 497 eri numerolla, jotka osoittivat, että keskimäärin algoritmin ensimmäinen vaihe on noin 2 kertaa hitaampi kuin algoritmin ensimmäinen vaihe , ja toinen askel on noin 4 kertaa hitaampi [1] . $p-1$ $p+1$ $p+1$ $p-1$

Sovellus

Koska faktorointimenetelmä on nopeampi, -menetelmää käytetään harvoin käytännössä [1] . $p-1$ $p+1$

Records

Tällä hetkellä (14.12.2013) menetelmällä löydetyt kolme suurinta alkujakajaa [3] koostuvat 60, 55 ja 53 desimaaliluvusta. $P+1$

Numeroiden määrä	s	Numeronjakaja	Löytäjä (kenenkä)	Löyty (milloin)	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.5.2011	$10^{{9}}$	$10^{13}$
53	60120920503954047277077441080303862302926649855338567	$682\cdot 5^{682}-1$	P. Leyland	26.02.2011	$10^{8}$	$10^{12}$

Tässä on Lucasin numerosarjan 2366. jäsen. $L_{2366}$

Muistiinpanot

↑ 1 2 3 4 5 6 7 8 9 10 11 12 Williams, 1982 .
↑ Lehmer, 1930 .
↑ Tallenna p+1-menetelmällä löydetyt tekijät . Käyttöpäivä: 13. joulukuuta 2013. Arkistoitu alkuperäisestä 18. joulukuuta 2013. (määrätön)

Kirjallisuus

Williams HC A p+1 factoring-menetelmä = A p+1 factoring-menetelmä // American Mathematical Society. - 1982. - T. 39 , no. 159 . - S. 225-234 . — ISSN 00255718 .
D. H. Lehmer. An Extended Theory of Lucas' functions (englanniksi) = An Extended theory of Lucas' functions // Ann. Math.. - 1930. - V. 31 , no. 2 . - S. 419-448 .
Ishmukhametov Sh. T. Luonnollisten lukujen kertolaskumenetelmät: Oppikirja . - Kazan: Kazanin yliopisto, 2011. - S. 60-61. - 190 s.

Linkit

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