Olimpia

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

Salve a tutti,
qualcuno sa spiegarmi come funziona il calcolo del logaritmo discreto quando si vuole spezzare il problema in due sottogruppi?
Grazie.

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?

Sui primi due punti sono d'accordo (forse sul primo dovresti dimostrare anche che per ogni elemento di H, anche l'inverso si trova in H).

Dato che l'inverso è definito come x*x^-1=1 e ogni elemento di H elevato al quadrato da 1...per definizione l'inverso di x in H è.... x!!! quindi ogni elemento di H possiede un inverso (che in questo caso è se stesso) :wink:

Scusa ho fatto confusione con un esempio fatto per autoconvincermi (n=15)... :lol: :lol:

Comunque per n=91, H={1, 27, 64, 90}

Sui primi due punti sono d'accordo (forse sul primo dovresti dimostrare anche che per ogni elemento di H, anche l'inverso si trova in H).
Il punto "c" non l'ho capito... 4^2=16 è non è 1 mod91!!!
Non ho interpretato bene l'esercizio??

Ho appena finito il 4° del foglio numero 2 (ditemi cosa ne pensate):

a)Zn*={x: mcd(x,n)=1)
H={x: x^2=1 mod n} = {x=+-1 mod n}

=> n|x^2-1 => n|(x+1)*(x-1)

di conseguenza n dividerà uno dei due fattori ma non x, per cui, in ogni caso, varrà che mcd(x,n)=1.
Quindi tutti gli elementi che sono in H hanno mcd(x,n)=1 e di conseguenza H è un sottogruppo di Zn*.

Nota: forse si dovrebbe controllare che presi due elementi h1 e h2 di H il loro prodotto sia ancora in H....(?)

b) se supponiamo che n=p*q (2 divisori)
=>p*q|(x+1)*(x-1) le possibili soluzioni sono 4: p|x+1, p|x-1, q|x+1, q|x-1... e così via se ci sono 3 divisori di n
=> 2^(divisori di n)

c)H={1,4,11,14} per n=91

Siete daccordo?(La notazione è più che minimale per ovvi motivi di tempo...)

Desumi bene!!!
Comunque la dimostrazione pseudo formale potrebbe essere che non esiste un gruppo di 16 elementi , tutti di ordine 2!
Infatti il più grande gruppo che ha tutti gli elementi di ordine 2 è Z(24)* che ne ha 8.

In realtà non ho risolto quell'esercizio, ho solo tenuto conto dei risultati !! :lol:
Anche perchè il prof non l'ha inserito tra i "candidati"!!

:lol: :lol: :lol: incoraggiante....desumo che non hai fatto neanche il 6 del 2° foglio allora...non riesco a dare una dimostrazione "pseudo"-formale...hai qualche idea...?

In realtà non ho risolto quell'esercizio, ho solo tenuto conto dei risultati !! :lol:
Anche perchè il prof non l'ha inserito tra i "candidati"!!

c)Cerco conferme: Possiamo usare la proposizione che mette in relazione i due insiemi : C(p-1/d)=Bd ? O quella relazione vale solo per numeri primi?

Non credo si possa fare così... Se controlli meglio per n>24 non vale più che per ogni x, x^2=1.
Io avrei risposto che sono tutti gli interi non primi tali che la Eulero( n ) = (potenza di 2).
Deve essere potenza di due perchè essendo tutti gli elementi di ordine 2, il gruppo deve essere isomorfo a Z(2)xZ(2)x...
Cmq, controlla l'esercizio del foglio 2 numero 9 e capirai la mia risposta.

Afferrato il concetto! Ma posso chiederti come si determina il massimo ogni volta nell'esercizio 9?
Thanks lionel!!

"Registrata prenotazione all'Compito"

Non si smentisce mai :lol: :lol: :lol:

Il prof. ha attivato finalmente la pagina di prenotazione al compito dell'11

c)Cerco conferme: Possiamo usare la proposizione che mette in relazione i due insiemi : C(p-1/d)=Bd ? O quella relazione vale solo per numeri primi?

Non credo si possa fare così... Se controlli meglio per n>24 non vale più che per ogni x, x^2=1.
Io avrei risposto che sono tutti gli interi non primi tali che la Eulero( n ) = (potenza di 2).
Deve essere potenza di due perchè essendo tutti gli elementi di ordine 2, il gruppo deve essere isomorfo a Z(2)xZ(2)x...
Cmq, controlla l'esercizio del foglio 2 numero 9 e capirai la mia risposta.

Ragazzi,una domanda :

"qualcuno di voi ha risolto l'esercizio 4.b??"
Che metodo avete usato per risolvere l'esercizio...io stavo pensando di usare il crivello quadratico...

Grazie,ciao

Scusate! esercizio 10 del foglio 1

Esercizio 10:

b) Si elencano tutti gli elementi di Z(24)* (sono 8 ) e si svolgono i quadrati facendo vedere che sono tutti =1 modulo 24

c)Cerco conferme: Possiamo usare la proposizione che mette in relazione i due insiemi : C(p-1/d)=Bd ? O quella relazione vale solo per numeri primi?

Nell'esercizio 3 del foglio 5, punto b) e c) qualcuno di voi sa cosa vuol dire ord2 (pedice) ?????? :shock:

ma di quale foglio è questo esercizio? e che numero è?

4° esercizio del 1° foglio

ma di quale foglio è questo esercizio? e che numero è?