Matematik

Pollards rho algortime

25. marts kl. 15:54 af andersmogense - Niveau: A-niveau

Hej er der nogen som kan hjælpe mig med at forstå pollards rho algortime

Hvordan faktoriser man 262063
ved hjælp af Pollards ρ algoritme med funktionen ??(??) = ??^2 + 1.

Det ville være aller bedst hvis der en som kan uploade et maple dokument, hvor det er vist, men ellers er det fint med en beskrivelse nedenfor


Brugbart svar (0)

Svar #1
25. marts kl. 16:28 af peter lind

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


Svar #2
25. marts kl. 17:10 af andersmogense

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


Brugbart svar (0)

Svar #3
25. marts kl. 17:14 af peter lind

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


Svar #4
25. marts kl. 17:43 af andersmogense

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?


Brugbart svar (0)

Svar #5
25. marts kl. 18:05 af peter lind

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


Svar #6
25. marts kl. 19:25 af andersmogense

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

Vedhæftet fil:pollard rho.PNG

Brugbart svar (0)

Svar #7
25. marts kl. 19:37 af peter lind


Brugbart svar (0)

Svar #8
25. marts kl. 19:50 af peter lind

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


Svar #9
25. marts kl. 21:34 af andersmogense

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


Brugbart svar (0)

Svar #10
25. marts kl. 21:45 af peter lind

13 er antal af iterationer

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


Svar #11
25. marts kl. 21:55 af andersmogense

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?


Brugbart svar (0)

Svar #12
25. marts kl. 22:18 af peter lind

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


Svar #13
25. marts kl. 22:30 af andersmogense

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


Brugbart svar (0)

Svar #14
25. marts kl. 22:54 af peter lind

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


Svar #15
25. marts kl. 23:06 af andersmogense

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?


Svar #16
26. marts kl. 11:31 af andersmogense

Skal man altid starte med f(2)?


Svar #17
26. marts kl. 12:45 af andersmogense

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?

Vedhæftet fil:Udklip.PNG

Svar #18
26. marts kl. 16:16 af andersmogense

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?


Brugbart svar (0)

Svar #19
26. marts kl. 17:01 af peter lind

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


Svar #20
26. marts kl. 21:07 af andersmogense

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


Forrige 1 2 Næste

Der er 26 svar til dette spørgsmål. Der vises 20 svar per side. Spørgsmålet kan besvares på den sidste side. Klik her for at gå til den sidste side.