domenica 30 marzo 2014

Fattorizzazione degli RSA con Bezout

import math;
def mcd(a, b):
 if  b == 0:
  return a;
 else:
  return mcd(b, a%b);
def facto(n):
 k = -1;
 v = math.sqrt(1-4*k*n);
 while (v != math.floor(v)):
  k = k-1;
  v = math.sqrt(1-4*k*n);
 y = (1-math.sqrt(1-4*k*n))/2;
 x = (1+math.sqrt(1-4*k*n))/2;
 p = mcd(x, n);
 q = mcd(y, n);
 print(p);
 print(q);

martedì 25 marzo 2014

Fattorizzazione RSA: schema classico e calcolo parallelo (caso particolare)

schema classico
può anche capitare (casi rari) che avvenga solo  n = (a-b)(a+b)  in questo caso basterà usare i classici metodi alla Fermat. La situazione descritta non è la più generale ma è comunque abbastanza frequente (statisticamente)

questo induce un algoritmo di calcolo parallelo assegnando un diverso valore di k ad ogni PC

in generale k =1, 2, 3, 4, ....


lunedì 24 marzo 2014

Trovare i numeri pseudoprimi in base a con PARI/GP

Problema: trovare i numeri x non primi tali che a^x = a mod x (pseudoprimi in base a)




domenica 23 marzo 2014

Il logaritmo discreto risolve la fattorizzazione dei numeri RSA



inoltre risolvere l'equazione diofantina s^2-4n=d^2 nelle incognite s, d
s=p+q, d=p-q, quindi x^2-y^2 = 4n allora implica risolvere la fattorizzazione dei numeri RSA

mercoledì 12 marzo 2014

Logaritmo discreto: programmi in Python e PARI/GP

a^x = b mod p, trovare x dati a, b, p

PROGRAMMI IN PYTHON
import math;
def logdisc(a, b, p):
 x=1;
 while(math.fmod(a**x,p) != b ):
  x = x+1;
 print(x);
----
import math;
def logdisc(a, b, p):
 x=1;
 while((a**x - b)% p != 0 ):
  x = x+1;
 print(x);
----
import math;
def logdisc(a, b, p):
 k = 1;
 x = math.log(b+k*p)/math.log(a);
 while ( x != math.floor(x) ):
  k = k+1;
  x = math.log(b+k*p)/math.log(a);
 print(x);
----
PROGRAMMA IN PARI/GP
{logdisc(a, b, p) = local(x);
x = 1;
while ((a^x -b)%p !=0 , x=x+1);
print(x);
}



venerdì 7 marzo 2014

Numeri primi con la libreria GMP e il PARI/GP

NUMERI PRIMI CON GMP
LISTA DI PRIMI
#include 
#include 
void main (void){
unsigned long int i, j;
i = 1;
j = 1;
mpz_t primo;
mpz_t base;
mpz_init(primo);
mpz_init(base);
base = 2165671351635126533125751;
while (i<= 10000){
mpz_nextprime(primo, base);
gmp_printf("%Zd\n", primo);
mpz_add_ui(primo, primo, j);
mpz_set(base, primo);
i = i+1;
}
}
-----------------------------------
TEST DI PRIMALITA'
#include 
#include 
void main(void){
int reps = 100;
int risultato;
mpz_t n;
mpz_init(n);
mpz_init_set(n, 1263516735162516757157);
risultato = mpz_probab_prime_p(n, reps);
if (risultato == 0){
gmp_printf("il numero %Zd e'composto", n);
else
gmp_printf("il numero %Zd e' primo", n);
}
mpz_clear(n);
}
----------------------------------------
LISTA DI PRIMI CON PARI/GP
{ listaprimi;
i = 0;
j = 3;
a = 0;
while (a <= 1000,  a= nextprime(j); print(a); i=i+1; j = a+1); 
}