Scomporre in fattori un numero composto sembra banale, un esercizio da scuole medie inferiori eppure è uno dei problemi maggiori dell'era moderna per ambiti come la crittografia. La sfida tra cifratori e crittoanalisti è basata essenzialmente sul tempo necessario a decrittare un messaggio. Maggiore è il tempo necessario più diventa obsoleto o inutile il messaggio stesso.
In passato alcuni algoritmi come quello di Shor non venivano tanto presi in considerazione, ma oggi con l'avvento e le prime sperimentazioni dei computer quantistici l'algoritmo ritorna di interesse perchè i "moderni computer" sono capaci di velocità e parallelizzazioni molto spinte.
Questo vuol dire che sarà possibile istanziare N processi paralleli, partendo magari da valori diversi, e il primo che troverà il risultato farà terminare l'eleaborazione degli altri processi.
Un esempio didattico ci viene fornito dal sito www.geocities.com/SiliconValley/Port/3264
L'esempio è utilizzabile con PARI/GP ma dovendo girare su computer convenzionali non aspettatevi miracoli in fatto di tempi. L'algoritmo è una variante di Shor e semplificato per far comprendere l'idea su cui è basato.
/*********************************************************
* Shor Factoring
*
* n
* f(x) = a^x mod n
*
* Variant of "Shor's algorithm"
*
* Rosario Turco
*
* RSA
* 0 0 5
* 39460021111111111107165109=2207*55234 r=
* 1178888888888888888771=1439*39095 r=
* 11788888811= r=
* 2467757=2417*1021 r=
* 691217=1021*677 r=57460
* 99097=41*2417 r=12080
* 4171=43*97 r=336
*********************************************************/
{shorRSA(n, flag) = local (a, vecOut, i, r, j, initseq, val1, val2, repeat);
if( n<2>1"));
if( bigomega(n) == 1, print1("shorRSA: It's a prime number: ", n); return(););
if( bigomega(n) > 2, print1("shorRSA: You must insert a RSA number!"); return(););
vecOut=vector(2);
/* trivial case */
if( Mod(n,2)==0, vecOut[1]=2; vecOut[2]=floor(n/2); return(vecOut););
if( Mod(n,3)==0, vecOut[1]=3; vecOut[2]=floor(n/3); return(vecOut););
if( ispower(n,2)==1, vecOut[1]=floor(sqrt(n)); vecOut[2]=vecOut[1];return(vecOut); );
/* Strategy to choose the value a */
repeat = 1;
a=2;
while( repeat == 1 & a
/* if r odd then repeat = 1 */
while( repeat == 1,
repeat = 0;
r = 0;
/* We find a
while((gcd(a,n)!=1), a++;);
/* The first of the sequence */
initseq = a%n; /* a^1 mod n */
i=2;
/* We search the lenght of sequence jstep from the second element i=2 */
while( initseq != (a^i)%n, r++; if(flag==1, print1("."); i++; ));
r++;
if(r%2 != 0, repeat=1; print1("d", r););
);
j=r/2;
val1=(a^j)-1;
val2=(a^j)+1;
if(flag == 1, print1("\n\nr: ", r); print1("\nj: ", j););
vecOut[1]=gcd(val1,n);
vecOut[2]=gcd(val2,n);
if( vecOut[1]==1 | vecOut[2] == 1, repeat=1;);
a++;
);
return(vecOut);
}
Post
