TEN 2007

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

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

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:

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


Ciao!!

Rizzi ha scritto:

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:

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

pax22 ha scritto:

Rizzi ha scritto:

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:

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

Rizzi ha scritto:

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

l'ordine di grandezza si riferisce al numero da fattorizzare n e non al fattore q, vero?! :shock: :shock: