Olimpia

L'algoritmo di Shanks-Tonelli risolve problemi del tipo x^2 = n mod p, dove n è un residuo quadratico di p.

In pratica ti trova la x.

Siccome l'algoritmo ci sembrava parecchio complicato da implementare e non avevamo più molto tempo abbiamo cercato un'implementazione e qualcosa abbiamo trovato.

Non mi pare sia quello utilizzato da noi, ma una possibile implementazione l'ho trovata qui:

http://www.codecodex.com/wiki/index.php ... _algorithm


Ciao!!

Grazie Rizzi!
Comunque stavo girando per il web,e ho trovato,proprio sul sito di schoof,lo pseudocodice di Tonelli...se può servirti...

Ma p è il numero primo e n il numero da fattorizzare giusto????

L'algoritmo di Shanks-Tonelli risolve problemi del tipo x^2 = n mod p, dove n è un residuo quadratico di p.

In pratica ti trova la x.

Siccome l'algoritmo ci sembrava parecchio complicato da implementare e non avevamo più molto tempo abbiamo cercato un'implementazione e qualcosa abbiamo trovato.

Non mi pare sia quello utilizzato da noi, ma una possibile implementazione l'ho trovata qui:

http://www.codecodex.com/wiki/index.php ... _algorithm


Ciao!!

Grazie Rizzi!
Comunque stavo girando per il web,e ho trovato,proprio sul sito di schoof,lo pseudocodice di Tonelli...se può servirti...

L'algoritmo di Shanks-Tonelli risolve problemi del tipo x^2 = n mod p, dove n è un residuo quadratico di p.

In pratica ti trova la x.

Siccome l'algoritmo ci sembrava parecchio complicato da implementare e non avevamo più molto tempo abbiamo cercato un'implementazione e qualcosa abbiamo trovato.

Non mi pare sia quello utilizzato da noi, ma una possibile implementazione l'ho trovata qui:

http://www.codecodex.com/wiki/index.php ... _algorithm


Ciao!!

Rizzi,una domanda...tu hai fatto il qs??
Sapresti dirmi in parole povere cosa fa l'algoritmo di Shanks Tonelli?
O comunque indicarmi un sito dove posso trovare qualcosa a riguardo?
Grazie...

35-40 cifre in tempi umani, un bel portatile ti aiuta in ciò

Qualcuno che ha fatto quest'anno il progetto può dirmi cortesemente quante cifre col QS servono per prendere un buon voto???

Oggi mi sento in vena di domande...
Il prof ha messo queste date : 27-28-29 giugno...
Ma uno se la può scegliere la data nella prenotazione per mail,oppure te l'assegna lui????????

Figo google mi dice che faccio ricerche molto di più il mercoledi...

Ma io mi riferivo alla prova scritta con gli esercizi ... il " lasciapassare " per il progetto :lol:

hai ragione scusa! l'altra volta mi pare che avesse fatto coincidere la prima data della discussione progetti con lo scritto.. oppure il giorno prima non ricordo..
ti conviene mandargli una mail.

@lionel: grazie 1000!

Ma io mi riferivo alla prova scritta con gli esercizi ... il " lasciapassare " per il progetto :lol:

ciao!
non ho parlato col prof ma le date sono online da almeno un mese:

[code type="markup"]Discussione progetti: 27, 28, 29 giugno 2007. Ufficio 1204, Dipartimento di Matematica, Edificio Sogene. Prenotazione per email.[/code]

il mio problema è che non so se ce la faro' in 10 giorni a prepararlo...

Non è che per caso qualcuno che ha fatto MPQS o QS semplice potrebbe per favore mandarmi qualche link o titolo di libro che ha usato per implementarlo?

vi ringrazio tutti in anticipo!
ciao

Noi ci siamo basati su questo documento:
http://www.crypto-world.com/documents/siqs.ps.gz

ciao!
non ho parlato col prof ma le date sono online da almeno un mese:

[code type="markup"]Discussione progetti: 27, 28, 29 giugno 2007. Ufficio 1204, Dipartimento di Matematica, Edificio Sogene. Prenotazione per email.[/code]

il mio problema è che non so se ce la faro' in 10 giorni a prepararlo...

Non è che per caso qualcuno che ha fatto MPQS o QS semplice potrebbe per favore mandarmi qualche link o titolo di libro che ha usato per implementarlo?

vi ringrazio tutti in anticipo!
ciao

Qualcuno percaso ha parlato ultimamente con Schoof e conosce in anteprima ( :? ) le date per la prova scritta di Giugno ??

Thanks.

non mi pare che vada comunicato nulla. basta mandare una mail per prenotarsi entro pochi giorni dall'esame.. confermate?
Ha pubblicato le nuove date
Discussione progetti: 27, 28, 29 giugno 2007. Ufficio 1204, Dipartimento di Matematica, Edificio Sogene. Prenotazione per email.

Qualcuno mi sa dire se la scelta del progetto va comunicata anticipatamente al professore?? :?:

Qualcuno che ha implementato le curve ellittiche e ha già fatto l'esame? Che numeri dava? Com'è andata?

grazie 18927382410326547632185743659837465743687534875638295643786583429873427856943827543873453847965489 a shogun

scusate se mi faccio gli affari vostri... ma la molta felicità del prof... a che voto corrisponderebbe, non vorrei fare la figura di quello terra terra, però, mi farebbe piacere prendere un bel voto.

30 e lode

Un'altra domanda: 47 cifre va bene, ma sarebbe interessante anche sapere che tipi di fattori aveva, che è più importante, solo due fattori grandi o un paio più grandi e tutti gli altri più piccolini?

Erano solo due fattoroni (leggi: fattori grandi)

Noi siamo riusciti a farne 47 cifre in 20 minuti. Ed era molto felice. Il nostro però era l'algoritmo del MPQS (MultiPolynomial), quindi forse il QS normale non è così veloce...

scusate se mi faccio gli affari vostri... ma la molta felicità del prof... a che voto corrisponderebbe, non vorrei fare la figura di quello terra terra, però, mi farebbe piacere prendere un bel voto.
Un'altra domanda: 47 cifre va bene, ma sarebbe interessante anche sapere che tipi di fattori aveva, che è più importante, solo due fattori grandi o un paio più grandi e tutti gli altri più piccolini?

grazie ragazzi!
Per curiosita', che algoritmo avete fatto? io sto lavorando al QS e non ho idea di quante cifre max debba essere il numero da fattorizzare..
grazie ancora ciao!

Noi siamo riusciti a farne 47 cifre in 20 minuti. Ed era molto felice. Il nostro però era l'algoritmo del MPQS (MultiPolynomial), quindi forse il QS normale non è così veloce...