Williams p + 1 algoritm

I beräkningstalteorin är Williams p + 1 algoritm en heltalsfaktoriseringsalgoritm , en av familjen av algebraiska gruppfaktoriseringsalgoritmer . Den uppfanns av Hugh C. Williams 1982.

Det fungerar bra om talet N som ska faktoriseras innehåller en eller flera primtalsfaktorer p så att p + 1 är jämnt , dvs p + 1 innehåller bara små faktorer. Den använder Lucas-sekvenser för att utföra exponentiering i ett kvadratiskt fält .

Det är analogt med Pollards p − 1 algoritm .

Algoritm

Välj något heltal A större än 2 som kännetecknar Lucas-sekvensen :

$V_{0}=2,V_{1}=A,V_{j}=AV_{j-1} -V_{j-2}$

där alla operationer utförs modulo N .

delar alla udda primtal p $\gcd(N,V_{M}-2)$ när M är en multipel av $p-( D/p)$ , där $D=A^{2}-4$ och $(D/p)$ är Jacobi-symbolen .

Vi kräver att ${\displaystyle (D/p)=-1} ,$ det vill säga D ska vara en kvadratisk icke-rester modulo p . Men eftersom vi inte vet p i förväg, kan mer än ett värde på A behövas innan man hittar en lösning. Om $(D/p)=+1$ urartar denna algoritm till en långsam version av Pollards p − 1 algoritm .

Så för olika värden på M beräknar vi ${\displaystyle \gcd(N,V_{M}-2)} ,$ och när resultatet inte är lika med 1 eller N , har vi hittade en icke-trivial faktor av N .

Värdena på M $V_{M-1}$ används är successiva faktorialer, och $V_{M}$ är det M -:te värdet av sekvensen som kännetecknas av .

För att hitta det M -:te elementet V i sekvensen som kännetecknas av B , fortsätter vi på ett sätt som liknar vänster-till-höger-exponentiering:

     x := B y := (B ^ 2 − 2) mod N  för varje  bit av  M  till höger om den mest signifikanta biten  gör  om  biten är 1  då  x := (x × y − B) mod N y : = (y ^ 2 − 2) mod N  annars  y := (x × y − B) mod N x := (x ^ 2 − 2) mod NV := x 

Exempel

Med N =112729 och A =5 är successiva värden för ${\displaystyle V_{M}} :$

V ₁ av följande(5) = V _1! av seq(5) = 5

V ₂ av seq(5) = V _2! av seq(5) = 23

V ₃ av seq(23) = V _3! av sekv(5) = 12098

V4 av sekv(12098) = _{V4 !} av seq(5) = 87680

V ₅ av seq(87680) = V _5! av seq(5) = 53242

V ₆ av seq(53242) = V _6! av sekv(5) = 27666

V7 av sekv(27666) = _{V7 !} av seq(5) = 110229.

Vid denna tidpunkt är gcd(110229-2,112729) = 139, så 139 är en icke-trivial faktor på 112729. Lägg märke till att p+1 = 140 = 2 2 ^× 5 × 7. Talet 7! är den lägsta faktorn som är multipel av 140, så den korrekta faktorn 139 hittas i detta steg.

Med ett annat initialvärde, säg A = 9, får vi:

V ₁ av följande(9) = V _1! av seq(9) = 9

V ₂ av seq(9) = V _2! av sekv(9) = 79

V3 av sekv(79) = _{V3 !} av seq(9) = 41886

V ₄ av seq(41886) = V _4! av seq(9) = 79378

V ₅ av seq(79378) = V _5! av seq(9) = 1934

V ₆ av seq(1934) = V _6! av sekv(9) = 10582

V7 av sekv(10582) = _{V7 !} av seq(9) = 84241

V ₈ av seq(84241) = V _8! av sekv(9) = 93973

V9 av sekv(93973) = _{V9 !} av seq(9) = 91645.

Vid denna tidpunkt är gcd(91645-2,112729) = 811, så 811 är en icke-trivial faktor på 112729. Lägg märke till att p−1 = 810 = 2 × 5 × 3 ⁴ . Siffran 9! är den lägsta faktorn som är multipel av 810, så den korrekta faktorn 811 hittas i detta steg. Faktorn 139 hittas inte denna gång eftersom p−1 = 138 = 2 × 3 × 23 vilket inte är en divisor av 9!

Som kan ses i dessa exempel vet vi inte i förväg om det primtal som kommer att hittas har en jämn p+1 eller p−1.

Generalisering

Baserat på Pollards p − 1 och Williams p +1 faktoriseringsalgoritmer utvecklade Eric Bach och Jeffrey Shallit tekniker för att faktorisera n effektivt förutsatt att den har en primfaktor p så att varje k: ^te cyklotomiskt polynom Φ _{k (} p ) är jämnt . De första få cyklotomiska polynomen ges av sekvensen Φ ₁ ( p ) = p −1, Φ ₂ ( p ) = p +1, Φ ₃ ( p ) = p ² + p +1, och Φ ₄ ( p ) = p ² +1.

•    Williams, HC (1982), "A p+1 method of factoring", Mathematics of Computation , 39 (159): 225–234, doi : 10.2307/2007633 , JSTOR 2007633 , MR 0658227

externa länkar

• P + 1 faktoriseringsmetod på Prime Wiki