Olimpia

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?

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.

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:

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

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!

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!

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

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

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)

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

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

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:

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

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!

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

Non preoccuparti!!Va bene lo stesso!

OT (per sdrammatizzare): sapete se si trovano ancora biglietti per il derby di stasera?

Good work!

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

ho capito grazie!
Riguardando gli appunti lo aveva fatto alla prima pseudo-esercitazione, l'unica NON facoltativa di un ciclo di 4 pseudo-esercitazioni che avrebbero dovuto preparare ad un compito NON facoltativo!

Qualche anima pia per caso mi potrebbe mandare in privato la 3a pseudo esercitazione per favore?

Esercizio numero 6, Foglio 1

(Numeri di Mersenne) Per ogni numero naturale n, si definisce l'ennesimo numero di Mersenne come M(n)=2^n-1
(a) Fattorizzare M(n) per 1<=n<=12;
(b) Dimostrare: se M(n) è primo, allora n è primo;
(c) Far vedere che il viceversa di (b) non vale.

(a)
M(1) =2^1-1 =1
M(2) =2^2-1 =3
M(3) =2^3-1 =7
M(4) =2^4-1 =15=3*5
M(5) =2^5-1 =31
M(6) =2^6-1 =63=3*21=3^2*7
M(7) =2^7-1 =127
M(8) =2^8-1 =255=5*55=5^2*11
M(9) =2^9-1 =511=7*73
M(10) =2^10-1 =1023=3*341=3*11*31
M(11) =2^11-1 =2047=23*89
M(12) =2^12-1 =4095=3^2*5*7*13

(la fattorizzazione di M(11) e M(12) li ho calcolati sul computer, ma come si vede anche a mano M(12) ha una fattorizzazione facile, giusto M(11) poteva far perdere un pò di tempo)

(b) M(n) primo implica n primo
Ipotizziamo per assurdo che n non sia primo (ovviamente assumendo la premessa)
Esistono p,q, numeri interi primi tali che n=p*q AND MCD(p,q)=1
M(n)=2^n-1=2^(p*q)-1
Noi sappiamo che dato un numero primo z:
x^(z-1) (mod z) è congruo a 1
e ovviamente
x^z (mod z) è congruo a x
Quindi
M(n)=2^n-1=2^(p*q)-1=(2^q)^p (mod p) è congruo a 2-1=1 (mod p)
equivalentemente
M(n)=2^n-1=2^(p*q)-1=(2^p)^q (mod q) è congruo a 2-1=1 (mod q)
Per il Teorema Cinese del Resto possiamo scrivere che
M(n) è congruo a 1 (mod p*q)
o equivalentemente
M(n)-1=2^n-1-1=2^n-1=2(2^(n-1)-1) è congruo a 0 (mod p*q=n)
Questo significa che n deve dividere 2(2^(n-1)-1)
ora
2(2^(n-1)-1) congruo a 0 (mod n)
se e solo se 2^(n-1) (mod n) è congruo a 1
è vera se e solo se n è primo, incongruo con quanto detto prima
quindi l'assunzione era sbagliata
e quindi abbiamo dimostrato che
M(n) primo implica n primo

(c) dimostrare che n primo implica M(n) primo
basta trovare un controesempio
11 è un numero primo
M(11)=2047 che non è primo e può essere fattorizzato come 2047=23*89

Scusate, è una cavolata ma non ricordo bene e non riesco a trovarla sugli appunti... se ho un punto P=(x, y), come è il punto -P? E' (x, -y)?