lunedì 20 ottobre 2014

Un algoritmo di fattorizzazione poco efficiente

n = pq
d = p-q
s = p+q

p^2-q^2 = ds

M = ds > 4sqrt(n)

p^2-q^2 = M
n = pq
 M= ds

questo ci porta ad una equazione di quarto grado biquadratica in p o in q, dove porre il discriminante maggiore di zero. Si fa variare M finché non si ottengono valori interi

lunedì 6 ottobre 2014

Riflessioni su RSA

n = pq se p, q sono molto vicini allora p = q+a quindi q^2+aq-n=0 con a pari, parametro a che varia finché non ottengo valori interi per q.

 se p, q non sono molto vicini p^2=q^2+a dove 4 divide a e  a > 0, a < n sostituendo ottengo
 q^4+aq^2-n^2=0,parametro a

In generale possiamo anche considerare p^m=q^m+a, n = pq