venerdì 29 luglio 2016

Un nuovo interessante algoritmo di fattorizzazione per RSA

n = x^2-y^2 (sempre per numeri composti), n= pq =(x-y)(x+y)

ma consideriamo per comodità

V = x^2+y^2

quindi sommando membro a membro

n+V = 2x^2 da cui x = sqrt[(n+v)/2], y =sqrt[(v-n)/2]

n dispari quindi V dispari


però y^2=x^2-n >0 quindi   V > n e V dispari

In certi casi può essere molto veloce

Generalizzando possiamo scrivere

x^2=y^2 mod(n)

x^2-y^2 = kn

ma x^2+y^2 = V

2x^2=V+kn

x=sqrt[(V+kn)/2], k = 1, 2, 3, 4... (sistema di calcolo parallelo)
y = sqrt[(V-kn)/2]


x^2-kn=y^2>0 allora V > kn


k pari allora V pari

k dispari allora V dispari

n = pq

codice in pari/GP (caso k dispari):

{facto(n, k) = local(v);
v = k*n;
x = sqrt((v+k*n)/2);
y = sqrt(x^2-k*n);
while(x != floor(x) || y != floor(y) , v = v+2; x = sqrt((v+k*n)/2);y = sqrt(x^2-k*n));
y = sqrt(x^2-k*n);
print(x);
print(y);
}

Casi banali ed estremi per le soluzioni di x^2y^2=n
a) x = sqrt(y^2+n), y = sqrt(x^2-n), x > sqrt(n)
b) x =y+m quindi sostituendo in x^2-y^2=n ottengo
y = (n-m^2)/2m con m < sqrt(n), m > 0
m = -y + sqrt(y^2+n), y >0

idem nel caso x^2=y^2 mod(n) perché basta sostituire kn con n per k=1, 2, 3, 4

In realtà
ponendo (v-n)/2 = q^2 allora v = 2q^2+n, q= 1, 2, 3, ....calcolo sqrt(n+v)/2, sqrt((n-v)/2) e se sono interio sono arrivato alla fine

oppure (n+v)/2 = Q^2 allora v = 2Q^2-n ovvero Q > sqrt(n/2)

tuttavia questo prova che l'algoritmo è equivalente a quello di Fermat


{facto1(n) = local(v);
q = 1;
v = 2+q^2+n;
while(sqrt((n+v)/2) !) int(sqrt((n+v)/2)), q = q+1; v = 2*q^2+n);
p = sqrt((v+n)/2)-sqrt((v-n)/2);
q = sqrt((v+n)/2)+sqrt((v-n)/2);
print(p);
print(q);

}

{facto1(n) = local(v);
q = 1;
v = abs(2*q^2-n);
while(sqrt((v-n)/2) !) int(sqrt((v-n)/2)), q = q+1; v = 2*q^2-n);
p = sqrt((v+n)/2)-sqrt((v-n)/2);
q = sqrt((v+n)/2)+sqrt((v-n)/2);
print(p);
print(q);

}






mercoledì 13 luglio 2016

Ulteriori nuovi appunti sulla congettura di Beal

x^n+y^m = z^1
basta considerare valori arbitrari di x, y, n, m interi positivi e calcolare z, ha infinite soluzioni molte delle quali facilmente coprime.

x^n+y=z^q
basta calcolare y = z^q-x^n  e considerare z, q, x, n interi positivi arbitrari tali che z^q-x^n > 0, ha infinite soluzioni molte delle quali facilmente coprime

dato che 1^7+2^3 = 3^2  deduciamo che nell'equazione di beal x^n+y^m = z^q non basta che le basi x, y, z siano maggiori di 1  ma anche gli esponenti interi n, m, q devono esserlo altrimenti è faile trovare controesempi.


z^q = (z^q)/2 +(z^q)/2

se z = 2^k allora possiamo scrivere 2^(kq-1)+2^(kq-1)=2^(kq) che è una delle tante formule che dà infinte soluzioni all'equazione di Beal non coprime.

quest'ultima tecnica si può estendere ad altre equazioni difoantine del tipo
a^x+b^y+c^u = d^v, se d =3^k allora 3^(kv-1)+3^(kv-1)+3^(kv-1)=3^(kv)

sabato 2 luglio 2016

la congettura debole di Goldbach

Sappiamo che ogni numeri pari può essere scritto come somma tra un primo e un dispari ovvero 2a = p+d con p = numero primo d = numero dispari. Questo è facilmente dimostrabile perché basta usare un noto teorema che dice che tra a e 2a esiste sempre un numero primo (a < p < 2a).

Nel 1923 un matematico russo provò che ogni numero pari può essere ottenuto come somma al più di quattro numeri dispari ovvero 2a = p+q+u+v (p, q, u, v numeri primi).

Unendo i due teoremi otteniamo che 2a=p+q+u+v=p+d ovvero d = q+u+v. ovviamente d > 7 perché 7 = 3+3+1 (più piccoli numeri primi dispari). Questo prova la congettura debole di Golbach.

Possiamo provare la congettura debole di Goldbach anche ipotizzando vera la congettura forte del Goldbach ovvero se 2a = p+q , p q primi allora 2a+3=p+q+3 anche qui 2a+3 se a = 1 , 2a+3 = 5 => 2 = p+q ovvero p=q=1, quindi 2a+3 >=7.


Versione probabilistica della congettura di Goldbach
Dato un numero pari 2n, ci sono sempre n modi diversi per scrivere n come somma di due numeri escludendo il caso banale di 2n = 2n+0 ( n-1 modi diversi escludendo anche il caso banale 2n = (2n-1)+1) .Dato che i numeri primi minori o uguali a n sono approssimativamente n/ln(n) e che lim(n^2/ln(n)^2) = +inf per n -> +inf allora dal punto di vista probabilistico è sempre meno probabile che al crescere delle dimensioni del numero pari 2n non ci sia almeno una coppia di primi la cui somma dà proprio 2n.