Pollards rho algortime

Du kan da også prøve hvilken ulige tal der går op tallet. Det skulle højst tage lidt over 500 forsøg. Det er ingenting i et program. Det kan også klares ret nemt i et regneark

Du kan jo også bruge dit CAS værktøj

se https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

Peter lind, tror ikke helt jeg forstår dit svar, eller måske forstår du ikke hvad jeg søger. Mit problem er jeg ikke helt forstår Pollards rho algoritme og dermed søger en slags vejledning til hvordan med faktoriserer 262063 med en funktion som er f(x)=x^2+1

Algoritmen er beskrevet i henvisningen i #1

Hvis der er noget du ikke forstår der må du vende tilbage med en forklaring om hvad du ikke forstår

Jamen tror jeg mangler en forståelse af algoritmen og har læst dit link til wikipedia nu, men har stadig nogle ting jeg undrer mig over, men som jeg ikke kan forklare. Men en ting jeg søger svar på er dog, hvordan RSA kan angribes med pollards rho

Har du adgang til maple?

I RSA er der et hemmeligt tal n=p*q Algoritmen bliver brudt hvis man kender p og q. Kodningen sker med et tal e. Med euklids udviddede algoritme kan man nemt finde d, og så er algoritmen brudt

Jeg har ikke maple

Jamen det forstår jeg godt, det jeg bare ikke forstår er hvordan man gør det med pollards rho.

Har fået denne tilsendt, men forstår ikke, hvad 13 og 503 betyder

Den implementere bare pollands algoritme'

I stedet for at starte med x=2 starter den med et tilfældigt tal mellem 1 og n-1

Hvad den ikke siger men hvad den gør i eksemplet er at rækkefølgen af x er derefter derefter x, f(x), f(f(x)), f(f(f(x))) ... o.s.v.

det er let at kontrollere at man i eksemplet bruger 2, f(2) = 5, f(5) = 26, f(26) = 677

Der er da ikke noget 13 og 503

Tusind tak for hjælpen det hjalp en del, men i nede i højre hjørne af billedet får man svaret 13 og 503

13 er antal af iterationer

503 er et tal, som går op i 262063

Er det rigtigt forstået at f(2)=5 f(5)=26 osv. når jeg har gjort det 13 gange så får jeg 262063?

Ja bortset fra at du ikke får 262063 men får 503 der går op i 262063. Du har altså fundet en faktor i 262063

Ja 503 er en primfaktor i 262063, men de 13 iterationer forstår jeg ikke helt. Hvad er det der er 13 gentagelser af?

Det er antal gange den har kørt gennem algoritmen og i dette tilfælde antal gange den har beregnet GCD. I eksemplet på internettet er det angivet som i. Her er den kørt 4 gange gennem algoritmen

Det begynder at give mening, men når du siger GCD, så er det jo det samme som sfd (største fælles divisor) så for hvad er 503 fælles. Men det kan da ikke passe for både tallet selv 262063 og 521 er større og går op i 262063?

Skal man altid starte med f(2)?

Glem de 2 forrige spørgsmål. Ud fra vedhæftet fil, kan du så forklare mig, hvorfor jeg ikke får 521 efter de 13 iterationer?

Okay har fundet ud af mine forhen værende spørgsmål, så bare glem dem, og indtil videre tusind tak Peter Lind. Nu har jeg brugt en del af dagen på at selv studere, jeg er kommet en del længere. Ved godt at når jeg har lavet et vis antal iterationer og får den ene primfaktor, så kan jeg regne den anden ud. Her får jeg 503 og kan udregne at 521 er den anden. Hvordan kan man angribe RSA med dette system? Er det fordi man kan bruge det til at udregne phi(N) eller N eller noget helt tredje?

Man kender jo e. For d gælder at e*d ≡ mod (p-1))(q-1)+1  dvs. at d er den inverse til e modulo (p-1)(q-1)+1. Den kan man finde ved hjælp af euklids udvidede algoritme

Ja ved godt man kan bruge euklids algoritme, men hvordan kan man bruge pollards rho til at angribe RSA?