Olimpia

potresti postarla? Almeno avrei qualcosa su lavorare...dal momento che il tempo è nostro nemico e vorrei, a questo punto, ripassare le cose che ho (più o meno)capito...

Grazie Pax!

Molto volentieri,l'avrei postata anche prima,ma purtroppo non ho a portata di mano il mio quaderno con gli esercizi(che l'ho prestato ad un amico mio e me lo restituisce questa sera)...Fa lo stesso se lo posto stasera???

Onestamente non ricordo la dimostrazione,ho una confusione in testa allucinante con tutte ste formule...

potresti postarla? Almeno avrei qualcosa su lavorare...dal momento che il tempo è nostro nemico e vorrei, a questo punto, ripassare le cose che ho (più o meno)capito...

Grazie Pax!

A quanto pare sono solo soletto oggi.... :cry:

Ho provato a fare l'esercizio 3 del foglio 5, vi posto il punto a) e aspetto qualche anima pia che mi illumini sul significato di ord2(x^2-n)=1 ....
Non ho capito proprio cosa voglia dire, forse perchè sono mancato quando ha spiegato il crivello?BOH! Può essere ord(x^2-n) tutto calcolato modulo 2?

Comunque:

a) x=1+2k (dispari) => (1+2k)^2 - n =4k^2+4k+(1-n) =4k^2+4k-(n-1)

n dispari quindi n-1 sarà pari =>divisibile per due (n-1)=2L:

=2(2k^2+2k-L) (quindi x^2-n è pari)

Sì il ragionamento è corretto,anche a me viene lo stesso.
Per il secondo punto,io credo che quell ord2 ... = 1 voglia dire che l'ordine di x^2-n sia 1 in Z2(*) ...
Ho provato a dimostrarlo così,credo che mi venga pure,però il discorso è che non sono sicuro che vada fatto in questo modo...schoof non l'ha mai detta sta cosa!!

A quanto pare sono solo soletto oggi.... :cry:

Devo ancora iniziare il foglio 4.. devo andare a rivedermi le regole di addizioni sulle curve ellittiche! :wink:

L'esercizio sul fattoriale è stato fatto il aula!!

:shock: :shock:
Spero non sia rivolta a me questa tranquilla risposta.... :lol: :lol:
L'esercizio "del fattoriale", come lo chiami tu, è il 5 del foglio 1

Io ho gentilmente chiesto delucidazioni sul 3 del foglio 5 (per capirci: "Sia n un intero dispari. Far vedere che: a)...b)...c)....)

L'esercizio sul fattoriale è stato fatto il aula!!

A quanto pare sono solo soletto oggi.... :cry:

Ho provato a fare l'esercizio 3 del foglio 5, vi posto il punto a) e aspetto qualche anima pia che mi illumini sul significato di ord2(x^2-n)=1 ....
Non ho capito proprio cosa voglia dire, forse perchè sono mancato quando ha spiegato il crivello?BOH! Può essere ord(x^2-n) tutto calcolato modulo 2?

Comunque:

a) x=1+2k (dispari) => (1+2k)^2 - n =4k^2+4k+(1-n) =4k^2+4k-(n-1)

n dispari quindi n-1 sarà pari =>divisibile per due (n-1)=2L:

=2(2k^2+2k-L) (quindi x^2-n è pari)

Allora ES 5 foglio 1: ci tento...
A proposito qualcuno sa come si risolve l'esercizio 4 del secondo foglio? Io mi ci sono persa

Ciao ciao

Scusate volevo dire il quarto esercizio del terzo foglio. Grazie

Vediamo:

x=g^i (con i=log(x))
y=x^2
log(x)=i => log(x*x)=log(x)+log(x)=i+i=2i che è pari...

Credo sia qualcosa del genere....

Ragazzi qualcuno ha fatto qualche esercizio del 5° foglio oltre al n°2?

Thanks! :wink:

Allora ES 5 foglio 1: ci tento...
A proposito qualcuno sa come si risolve l'esercizio 4 del secondo foglio? Io mi ci sono persa

Ciao ciao

Scusate volevo dire il quarto esercizio del terzo foglio. Grazie

Allora ES 5 foglio 1: ci tento...
Dividiamo il caso in cui n non sia primo e n primo

Caso 1: Se n non è primo lo possiamo scrivere come n=P*Q con P>1 e Q>1 e ovviamente P e Q minori della radice quadrata di n che è minore di (n-1). Scrivo (n-1)!=1*2*.....*P*Q*...*(n-1) . Siccome ho moltiplicato tutti i numeri per P*Q posso scrivere che (P*Q)divide((n-1)!), ma allora posso dire che n divide ((n-1)!). Quindi (n-1)!=0 (mod n) per n non primo.

Caso 2: n primo: Pongo p=n-1 e prendo tutti gli elementi invertibili di Z* di p e dico che: (p-1)!=1*2*....*p-1. Ma essendo Z*p l'insieme dei numeri invertibili (per ogni elemento x di Z* di p ci sarà un altro elemento y in Z*p tale che x*y=1) posso scrivere che (p-1)!=1. Ricordo che p=n-1 e quindi p-1=n-2 scrivo che (n-1)!=1*2*...*(n-2)*(n-1)=1(n-1).
Posso scrivere che (n-1)! mod n=(n-1) mod n=-1 mod n

Ho cercato di essere il più chiara possibile ma non è facile dopo una giornata persa dietro a sti cavoli di esercizi. A proposito qualcuno sa come si risolve l'esercizio 4 del secondo foglio? Io mi ci sono persa

Ciao ciao

Ciao,
mi dispiace di avervi invitato a condividere le esperienza di risoluzione degli esercizi e poi di non dare il mio contributo, ma mi sto rendendo conto di essere rimasto veramente MOLTO indietro col programma (per usare un eufemismo!). Vi dico solo che sto tentando, senza successo, di risolvere l'esercizio 5 del foglio 1!
(calcolare (n-1)! mod n )
Penso che verro' a vedere di cosa si tratta lunedi pomeriggio giusto per fare una passeggiata!

Buon lavoro!

Dai se ti puo' consolare anche io non sto messo benissimo, e quell'esercizio (5 del foglio 1) non viene neanche a me ne', leggendo il forum, a lupin III...
Qualcuno è riuscito a farlo? Io credo di aver capito che viene 0 se n non è primo e n-1 se invece è primo, ma la dimostrazione non so come si faccia...
PS: Per caso qualcuno mi potrebbe mandare la scansione dell'esercitazione numero 3 (la penultima che ha fatto) per favore?

Grazie a tutti e.. speriamo bene x lunedi!

Ciao,
mi dispiace di avervi invitato a condividere le esperienza di risoluzione degli esercizi e poi di non dare il mio contributo, ma mi sto rendendo conto di essere rimasto veramente MOLTO indietro col programma (per usare un eufemismo!). Vi dico solo che sto tentando, senza successo, di risolvere l'esercizio 5 del foglio 1!
(calcolare (n-1)! mod n )
Penso che verro' a vedere di cosa si tratta lunedi pomeriggio giusto per fare una passeggiata!

Buon lavoro!

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

Sì, anche questo.. sapevo che di essermi persa qualcosa per strada...!

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)

Scusa ma se hai che n = p*q*r,come fai ad avere 8 combinazioni differenti?????? :shock: :shock:

salve ragazzi, qualcuno sa darmi qualche delucidazione su questo esercizio? grazie tante

foglio 3 esercizio 4

Sia p un primo e sia g una radice primitiva modulo p. Spiegare: per ogni x in Zp* si ha che x è quadrato in Zp*se e solo se il logaritmo discreto di x `e pari.

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?

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

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?

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!

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?