1 Fattorizzazione RSA e congettura di Goldbach Vincenzo Cerreto, Rosario Turco Introduzione La congettura di Goldbach un classico della Teoria dei Numeri cherientraneiproblemiadditivi;altrettantoclassicala procedura per fattorizzare un numero composto. Essi, come problemi classici, hanno un vasto pubblico che li comprendeechesidedicaadunpossibilesviluppodi dimostrazione. Nel caso della fattorizzazione, poi, il legame con la crittografia e lalgoritmo RSA, rende il problema anche di pratica utilit. Larticolo mette in evidenza come i due problemi siano legati, ed individua sia un metodo di fattorizzazione di un numero semiprimo o RSA (N = p * q), sia un metodo grafico di fattorizzazione. Goldbach e la simmetria Nella formulazione pi semplice, la congettura di Goldbach afferma che: Tutti i numeri pari maggiori di 2 possono essere espressi come somma di due numeri primi p e q, (p + q) = s > 2, dove p pu anche essere uguale a q. "Ilproblemacheinumeriprimisonodefinitimediante moltiplicazione,mentreilproblemariguardal'addizione.In generale difficile stabilire connessioni tra le propriet de1la moltiplicazione e dell'addizione dei numeri interi." [1] La domanda da porsi diventa: "Quando che (p * q) = (p + q), dove p e q sono numeri primi?" Per far s che l'uguaglianza sia verificata, in qualche modo, bisogna trovare il "ponte", ovvero la relazione di trasformazione che unisce il prodotto di due numeri primi con la loro somma. Lidea nasce usando il concetto di simmetria tra i due numeri primi p ed q: 2 (1)2(2) 2(3)2 2(4) 2 2(5)2 2(6)2(7)(8)( ),22* * 2* *222* *44 2 2*42* 22( ) p+qq pd p qp q d p qq pp q p qq p pqp q p qpq q p pqp qpq q p p qp q p qp q= p : S = p + q 2 d= q - p Quindi : p = S/2 d q = S - p

3 In conclusione sapendo N=p*q e ricavandoci d, troviamo poi p e q. Il vero problema algoritmico di individuare rapidamente d. In APPENDICE un semplice algoritmo in PARI/GP, che si basa sulla (2). Metodo grafico di fattorizzazione Il metodo grafico una curiosit che riportiamo, anche perch per numeri elevati scomodo da usare. Per la fattorizzazione si utilizza una semplice variazione della (2), cio: 2(9)2(10)**p q d dp q d d+ ++

In tal caso si pone: y = sqrt(pq+x^2) + x y = sqrt(pq+x^2) - x Se si eseguono i grafici delle (9)(10) le curve si devono incrociare obbligatoriamente, per la natura del problema, a delle coordinate intere, che si possono individuare a colpo docchio sulle singole curve (vedi il cerchio rosso degli esempi grafici successivi). Ad esempio per N=33 le curve si incrociano a coordinate(4, 11) e (4, 3), dove d=4 ed q=11 e p=3 sono i fattori di N=33=3*11. In questo caso d determinato graficamente. La non praticit del metodo che i programmi che tracciano i graficidifunzioni,pernumeriabbastanzagrandiacausa dellapprossimazione,dannolecoordinateinnotazione scientifica(es:1,1E-234)ediventadidifficile interpretazione. Un analogo problema risiede nel calcolo numerico e mostreremo un algoritmo in APPENDICE che cerca di superare tale difficolt. Nel seguito le immagini della fattorizzazione grafica con Derive del numero composto N=33. 4 Grafico di y = sqrt(pq+x^2) + x Grafico di y = sqrt(pq+x^2) - x Calcolo numerico Per risolvere il problema in PARI/GP che, per grandi numeri, alcune funzionalitdilibreriaoperanoinnotazionescientifica provocando la perdita di precisione, lalgoritmo implementa la funzionalit di radice quadrata col metodo di Newton-Raphson, ma con una precisione decidibile in automatico. Un esempio duso della procedura : getFactRSA(33)getFactRSA(219) getFactRSA(3064021)

5 La velocit dellalgoritmo dipende, da vari fattori:-dalla precisione del numero di punti di rilevazione sulla curva dellalgoritmo di Newton-Raphson (npoint=50);-dalla precisione per evitare il troncamento delle cifre nella valutazione della radice quadrata (realprecision);-dalla velocit con cui si individua il valore di d (cercato iterativamente). Se N = N * 1 N numero primo d=0d=1d>1 Quadrato di un numero primo Primi gemelliPrimi di Polignac In tabella si riassume che se d=0 vuol dire che si tratta di un quadrato di un numero primo. Se d=1 abbiamo a che fare con numeri primigemelli,perd>1abbiamoicosiddettinumeriprimidi Polignac; difatti sempre: q = p + 2*d Per la definizione del problema che q > p, non possibile d 1,

for(i=2,c, a = f(x,N)/f1(x); x = x - a; ); ); return(x); } 8 /* ** Su un multi-processore possibile mandare pi sessioni** in parallelo per diversi valori di d, impostando start ed end ** diversi sulle sessioni **** es: getPFRSA(13*11,1,10^6) ** */ {getPFRSA(n,start=-1, end=start+10^1000, npoint=50) = local (S=1.1, d=-1, q=1, p=1); if( n