La scomposizione dei numeri RSADi Cristiano Armellini, cristiano.armellini@alice.it e Morfeo Chiesa

Supponiamo di dover scomporre in fattori primi un numero intero n=pq ove p, q sono numeri primi molto grandi. Da Fermat sappiamo che ogni numero intero può essere espresso come la differenza di due quadrati , ovvero n=A2−B2=( A−B ) (A+B )=pq. Consideriamo due casi

Caso a)

Scriviamo B2=A2−n, ovvero B=√ A2−n. Quindi dobbiamo trovare gli interi A tali che A≥√n. D’altra

parte sapevamo che s=p+q≥2√n il che porta proprio a A≥√n.

Nei problemi RSA i due fattori (p, q) pur essendo molto grandi in genere hanno la stessa dimensione nel senso che sono dello stesso numero di cifre oppure differiscono al massimo di una o due cifre. Quindi detto

k= pq= A+√A2−nA−√A2−n

e svolgendo o calcoli si arriva a A=1+k2 √ nk . Ora non è detto che k sia intero tuttavia

per ogni k = 1,…100 possiamo considerare A¿=floor (1+k2 √ nk ) e quindi provare tutti gli interi A tali che

A>A ¿ fino a che anche B non è intero. E’ facile immaginare un sistema di calcolo parallelo che svolga tale compito. Ovviamente p =A+B, q = A-B

Vediamo una semplice applicazione in Visual Basic .net

Module Module1

Sub Main() Dim n As Double Dim a, b As Double Dim c As Integer Console.Write("inserisci un intero ") n = Console.ReadLine() a = Math.Floor(Math.Sqrt(n)) b = Math.Sqrt(Math.Abs(Math.Pow(a, 2) - n)) While (b <> Math.Floor(b)) a = a + 1 b = Math.Sqrt(Math.Abs(Math.Pow(a, 2) - n)) End While Console.WriteLine(a - b) Console.WriteLine(a + b) Console.Write("inserisci un carattere per finire ") c = Console.Read End Sub

End Module

Caso b)

Scriviamo n+B2=A2 quindi A=√B2+n con B = 0, 1, 2, 3,….. Anche qui come nell’esempio precedente

consideriamo k=pq= √B2+n+B

√B2+n−B (ove p>q, k = 1, …100) Svolgendo i calcoli si arriva a B= k−1

2 √ nk e

quindi se B¿=floor ( k−12 √ nk ) basterà prendere in esame per ogni valore di k =1, 100 gli B interi B>B¿ e

provarli fino a che anche A non è intero quindi p = A+B q = A-B

Vediamo una semplice applicazione in Visual Basic .Net

Module Module1

Sub Main() Dim n As Double Dim a, b As Double Dim c As Integer Console.Write("inserisci un intero ") n = Console.ReadLine() b = 0 a = Math.Sqrt(Math.Pow(b, 2) + n) While (a <> Math.Floor(a)) b = b + 1 a = Math.Sqrt(Math.Pow(b, 2) + n) End While Console.WriteLine(a - b) Console.WriteLine(a + b) Console.Write("inserisci un carattere per finire ") c = Console.Read End Sub

End Module

Per velocizzare entrambi gli algoritmi in tutti i casi ricordiamo che i quadrati perfetti devono terminare con una delle seguenti cifre 0, 1, 4, 5, 6, 9.