TEN 2007

Ciao, qualcuno sa spiegarmi il metodo "rho" di Pollard? ma poi in pratica lo può dare sul compito?

arale ha scritto:

Scusa un attimo.. tu hai detto che, dato che n non divide x, allora mcd(x,n)=1. Ma nè x nè n sono necessariamente primi, quindi potrebbero avere un fattore in comune.. o mi sfugge qualcosa?

Effettivamente tocca specificare bene se x ed n sono primi,in tal caso la dimostrazione è vera!
Per il punto b invece mi sembra ok...
Voi che ne dite?

Secondo me, il fatto che l'mcd(n, x)=1 non era da dimostrare, perchè per definizione in H ci sono solo elementi di Zp*... era da dimostrare, come accennava lionel, che avesse i requisiti dei sottogruppi, ovvero:
1)e=elemento neutro appartiene ad H
2) se x appartiene ad H, anche il suo inverso appartiene ad H

Che sono ovvietà.. per il punto b ci ha già pensato Tony (x è il suo inverso), per il punto a, 1^2 è 1 -> 1 appartiene ad H!

arale ha scritto:

Secondo me, il fatto che l'mcd(n, x)=1 non era da dimostrare, perchè per definizione in H ci sono solo elementi di Zp*... era da dimostrare, come accennava lionel, che avesse i requisiti dei sottogruppi, ovvero:
1)e=elemento neutro appartiene ad H
2) se x appartiene ad H, anche il suo inverso appartiene ad H

Che sono ovvietà.. per il punto b ci ha già pensato Tony (x è il suo inverso), per il punto a, 1^2 è 1 -> 1 appartiene ad H!

Ci sarebbe anche da dimostrare che per ogni h1 e h2 in H => h1*h2 è ancora in H...che ne dite?

marte ha scritto:

Ciao, qualcuno sa spiegarmi il metodo "rho" di Pollard? ma poi in pratica lo può dare sul compito?

Potrebbe dare un esercizio del genere es.11 foglio 1

Esercizio 1 foglio 3 (molto sensibile ad erroti di calcolo):

a)g=6

b)i=26 calcolato sia per tentativi che con il metodo baby step-giant step

c) La spiegazione è negli appunti....(si fa vedere che se x=g^i mod p e poi abbiamo x=g^(1+(p-1)) quest ultimo sarà uguale a x=g^i*g^(p-1)=g^i =>il logaritmo è da considerarsi classe p-1...)

Voi come l'avete fatto?Avete preso in considerazione la stessa radice primitiva?