Pollards rho algoritme

Stefan Budde August 8, 2016 P 0 0
FONT SIZE:
fontsize_dec
fontsize_inc

Pollards rho algoritme er en generel formål primtalsopløsning algoritme. Det blev opfundet af John Pollard i 1975. Det er særligt effektiv for et sammensat tal, der har en lille prime faktor.

Core ideer

Den ρ algoritme er baseret på Floyds cyklus-finding algoritme og på den iagttagelse, at t tilfældige tal x1, x2, ..., xt i området vil indeholde en gentagelse med sandsynlighed P & gt; 0,5 hvis t & gt; 1.177p. Den konstante 1,177 kommer fra mere generelle resultat, at hvis P er sandsynligheden for, at t tilfældige tal i intervallet indeholder en gentagelse, så er P & gt; 1 - exp {- t / 2n}. Således P & gt; 0.5 forudsat 1/2 & lt; exp {- t / 2n}, eller t & gt; 2nln 2, eller t & gt; 2n ln 2, eller t & gt; n = 1.177n.

Den ρ algoritmen benytter g. et polynomium modulo n som generator for en pseudotilfældig sekvens. (Den mest anvendte funktion er g = x mod n.) Lad os antage n = pq. Algoritmen frembringer sekvensen x1 = g, x2 = g (g), x3 = g (g (g)), og så videre. To forskellige sekvenser vil i praksis blive kører på samme tid - sekvensen {xk} og sekvensen {xk mod p}. Da p & lt; n, sidstnævnte sekvens er tilbøjelige til at gentage tidligere end den tidligere sekvens. Gentagelsen af ​​det mod p-sekvensen vil blive opdaget ved, at gcd = p, hvor k & lt; m. Når en gentagelse opstår, vil sekvensen cyklus, fordi hvert udtryk kun afhænger af foregående. Navnet ρ algoritme stammer fra ligheden i udseende til det græske bogstav ρ. Når det er cykling, vil Floyds cyklus-fund algoritme til sidst opdage en gentagelse. Algoritmen lykkes, når sekvensen {xk mod p} gentager før sekvensen {xk}. Den randomisering funktionen g skal være et polynomium modulo n, så det vil arbejde både modulo p og modulo n. Det vil sige, således at g ≡ g.

Algoritme

Algoritmen tager sit input n, det hele tal, der skal indregnes; og g, en poynomial p beregnet modulo n. Dette vil sikre, at hvis p | n, og x ≡ y mod p, derefter g ≡ g mod s. I den oprindelige algoritme, g = x - 1 mod n, men i dag er det mere almindeligt at anvende g = x + 1 mod n. Outputtet er enten en ikke-triviel faktor n, eller fiasko. Det udfører følgende trin:

  • x ← 2; y ← 2; d ← 1;
  • Mens d = 1:
    • x ← g
    • y ← g (g)
    • d ← gcd
  • Hvis d = n, returnere fiasko.
  • Else, tilbage d.

Bemærk, at denne algoritme kan ikke finde en nontrivial faktor, selv når n er sammensat. I så fald kan du prøve igen, ved hjælp af en startværdi andet end 2 eller en anden g. Navnet ρ algoritmen kommer fra det faktum, at værdierne af x sidst gentages med perioden d, hvilket resulterer i en ρ form, når man afbilder værdierne.

Varianter

I 1980, Richard Brent offentliggjort en hurtigere variant af rho-algoritmen. Han brugte den samme kerne ideer som Pollard, men en anden metode til påvisning cyklus, der erstatter Floyds cyklus-finding algoritme med relateret Brent cyklus fund metode.

En yderligere forbedring blev foretaget af Pollard og Brent. De bemærkede, at hvis, så også for ethvert positivt heltal b. Især i stedet for computing ved hvert skridt, er det tilstrækkeligt at definere z som produktet af 100 på hinanden følgende perioder modulo n, og derefter beregne en enkelt. En større hastighed op resultater som 100 GCD trin erstattes med 99 multiplikationer modulo n og en enkelt gcd. Lejlighedsvis kan det medføre, at algoritmen til at mislykkes ved at indføre en gentagen faktor, for eksempel når n er et kvadrat. Men det så tilstrækkeligt at gå tilbage til den forrige GCD sigt, hvor og af den regelmæssige ρ algoritme derfra.

Ansøgning

Algoritmen er meget hurtigt for tal med små faktorer, men langsommere i tilfælde, hvor alle faktorer er store. Den ρ algoritme mest bemærkelsesværdige succes var faktorisering af det ottende Fermat nummer, F8 = 1238926361552897 * 9346163971537977769164558199606896584051237541638188580280321. Den ρ algoritmen var et godt valg til F8, fordi den primære faktor p = 12389263661552897 er meget mindre end den anden faktor. Den faktorisering tog 2 timer på en UNIVAC 1100/42.

Eksempel faktorisering

Lad n = 8051 og g = mod 8051.

97 er en ikke-triviel faktor 8051. bortset x = y = 2 startværdier kan give cofaktor i stedet for 97.

Eksemplet n = 10403 = 101. 103

Her indfører vi en anden variant, hvor kun en enkelt sekvens er beregnet, og GCD beregnes inden for omkredsen, der registrerer cyklussen.

C ++ pseudokode

Følgende pseudokode finder faktor 101 i 10403 med en start værdi af x = 2.

Resultaterne

I nedenstående tabel den anden og fjerde kolonne indeholder hemmelige oplysninger ikke kendt til den person, der forsøger at faktor pq = 10403. De er medtaget for at vise, hvordan algoritmen fungerer. Hvis vi starter med x = 2 og følger den algoritme, vi får følgende numre:

Den første gentagelse modulo 101 er 97, som forekommer i trin 17. gentagelse registreres ikke, før trin 22, når x = xfixed. Dette bevirker GCD = GCD at være p = 101, og en faktor er fundet.

Kompleksitet

Hvis pseudotilfældige nummer x = g forekommer i Pollard ρ algoritme var et virkeligt tilfældige tal, følger det heraf, at succes ville være opnået halvdelen af ​​tiden, af fødselsdag paradoks. Det menes, at den samme analyse gælder såvel til den faktiske rho algoritme, men dette er en heuristisk krav, og stringent analyse af algoritmen forbliver åben.

  Like 0   Dislike 0
Forrige artikel Pigen der ventede
Næste artikel Roland AX-Synth
Kommentarer (0)
Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha