Olimpia

Scusate! esercizio 10 del foglio 1

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

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.

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

"Registrata prenotazione all'Compito"

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

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!!

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"!!

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...?

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.

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...)

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??

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).

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 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?

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

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

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!

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?

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