Es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después de Number field Sieve). Es todavía el más rápido para enteros que tienen 100 o menos dígitos decimales, y es considerado mucho más sencillo que la NFS. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución únicamente depende el tamaño del entero a ser factorizado, y no sobre una estructura especial o propiedades.
Algoritmo:
Ejemplo Aplicativo:
Nota: El valor de X, es un numero aleatorio, en este caso elegimos el 12
Observación: si al momento de hallar el mcd(x-y,n) este nos da un valor de 1 o n , debemos volver a buscar otra combinación de filas a sumar.
Implementación:
La siguiente implementación fue realizada en conjunto con uno de los autores de este Blog (Rafael Larco Buchelli).
Clase QuadraticSieve
import java.util.ArrayList;
public class QuadraticSieve {
public static int base=40;
EsPrimo esPrimo = new EsPrimo();
Jacobi jacobi = new Jacobi();
public ArrayList< Long > QS(int n){
//***************CALCULO DE LA BASE DE FACTORES************//
int jac=0,raiz=0;
ArrayList< Long > solucion = new ArrayList< >();
ArrayList< Integer > factoresBase = new ArrayList< >();
ArrayList< Integer > valoresX = new ArrayList< >();
ArrayList< Integer > valoresY = new ArrayList< >();
ArrayList< Boolean > ySuaves = new ArrayList< >();
ArrayList< Integer > valoresSuaves = new ArrayList< >();
factoresBase.add(-1);
for (int i = 2; i < base; i++) {
if(esPrimo.esPrimo(i)){
jac=jacobi.Jacobi(n, i);
if(jac==1){
factoresBase.add(i);
}
}
}
System.out.println("Mostrando Base De Factores");
for (int i = 0; i < factoresBase.size(); i++) {
System.out.println(factoresBase.get(i));
}
//*********************RAIZ CUADRADA DE N*************//
raiz=(int) Math.sqrt(n);
System.out.println("\nRaiz Cuadrada De "+n+" : "+raiz);
//*******************BUSQUEDA DE VALORES*************//
for (int i = -base; i < = base; i++) {
valoresX.add(raiz+i);
}
for (int i = -base ; i < = base; i++) {
valoresY.add((int)Math.pow((raiz+i), 2)-n);
}
//**********HALLANDO LOS Y'S SUAVES*************//
int i,j,valor,p;
int []a= new int[50];
for (int k = 0; k < valoresY.size(); k++) {
valor=Math.abs(valoresY.get(k));
i=2;
j=0;
while(valor >1){
if(valor%i==0){
valor=valor/i;
a[j]=i;
j++;
i=2;
}
else
i++;
}
p=0;
for (int l = 0; l < j; l++) {
boolean band=true;
for (int m = 0; m < factoresBase.size() && band==true; m++) {
if(a[l]==factoresBase.get(m)){
band=false;
p++;
}
}
}
if(p==j){
System.out.println(valoresY.get(k)+" | Suave"+" X: "+Math.sqrt(valoresY.get(k)+n));
ySuaves.add(true);
valoresSuaves.add(valoresY.get(k));
}
else{
// System.out.println(valoresY.get(k)+" | No Suave");
ySuaves.add(false);
}
}
//**************CALCULANDO LA MATRIZ*************//
int [][]matrizInicial = new int [valoresSuaves.size()][factoresBase.size()];
int conRep,filaMI=0,columnaMI=0;
ArrayList< Integer > factorizacionN = new ArrayList< >();
Factorizar factorizar=new Factorizar();
for (int k = 0; k < valoresSuaves.size(); k++) {
conRep=0;
columnaMI=0;
factorizacionN=factorizar.factorizarN(Math.abs(valoresSuaves.get(k)));
if(valoresSuaves.get(k)< 0){
factorizacionN.add(-1);
}
for (int l = 0; l < factoresBase.size(); l++) {
conRep=0;
for (int m = 0; m < factorizacionN.size(); m++) {
if(factoresBase.get(l)==factorizacionN.get(m)){
conRep++;
}
}
matrizInicial[filaMI][columnaMI]=conRep%2;
columnaMI++;
}
filaMI++;
}
//*******************ELIMINACION GAUSSIANA*************//
System.out.println("Gaussiana");
/**********************************************************/
/***Eliminacion de gauss: escoger las filas de la matriz***/
/*identidad cuya fila en la matriz inicial son todos ceros*/
/**********************************************************/
int filas, columnas;
filas=valoresSuaves.size();
columnas=factoresBase.size();
Identidad identidad = new Identidad();
int [][]MI=new int[filas][filas];
identidad.crearMatrizIdentidad(MI, filas);
Gaussiana gaussiana = new Gaussiana();
gaussiana.Gaussiana(matrizInicial, MI, filas, columnas);
//**************OBTENIENDO LAS FILAS A USAR (CEROS)***********//
boolean banderaCeros=true;
ArrayList< Integer > FilasUsar = new ArrayList< >();
for(int q=0;q< filas;q++){
banderaCeros=true;
for(int w=0;w< columnas && banderaCeros==true;w++){
if(matrizInicial[q][w]==1){
banderaCeros=false;
}
}
if(banderaCeros==true){
System.out.println("Usar Filas: "+q);
}
if(banderaCeros==true){
FilasUsar.add(q);
}
}
/***************CALCULANDO RESULTADO***********/
int filaUsar;
long resultadoX,resultadoY,valorXSuave,respuestaVerdad_Uno,respuestaVerdad_Dos;
boolean bandSolucion=true;
for (int k = 0; k < FilasUsar.size() && bandSolucion==true; k++) {
resultadoX=1;
resultadoY=1;
respuestaVerdad_Uno=0;
respuestaVerdad_Dos=0;
filaUsar=FilasUsar.get(k);
for (int l = 0; l < MI.length; l++) {
if(MI[filaUsar][l]==1){
valorXSuave=(long) Math.sqrt(valoresSuaves.get(l)+n);
resultadoX=resultadoX*valorXSuave;
resultadoY=resultadoY*valoresSuaves.get(l);
}
}
System.out.println("Resultado Y Sin Modulo: "+resultadoY);
resultadoX=resultadoX%n;
System.out.println("Resultado X: "+resultadoX);
resultadoY=(long) ((Math.sqrt(resultadoY)))%n;
System.out.println("Resultado Y: "+resultadoY);
MCD gcd = new MCD();
respuestaVerdad_Uno=gcd.mcd((resultadoX-resultadoY), n);
respuestaVerdad_Dos=gcd.mcd((resultadoX+resultadoY), n);
if(respuestaVerdad_Uno*respuestaVerdad_Dos==n && respuestaVerdad_Uno!=1 && respuestaVerdad_Dos!=1){
System.out.println("\nValor No Trivial: "+respuestaVerdad_Uno);
System.out.println("\nEl Otro Valor: "+respuestaVerdad_Dos);
solucion.add(0,respuestaVerdad_Uno);
solucion.add(1,respuestaVerdad_Dos);
bandSolucion=false;
}
}
return solucion;
}
}
Clase CalcularExponente
public class EsPrimo {
public boolean esPrimo(int numero){
int contador = 2;
boolean primo=true;
while ((primo) && (contador!=numero)){
if (numero % contador == 0)
primo = false;
contador++;
}
return primo;
}
}
Clase Factorizarimport java.util.ArrayList;
public class Factorizar {
public ArrayList< Integer > factorizarN(int n){
int i,j;
ArrayList< Integer > factores = new ArrayList< > ();
i=2;
j=0;
while(n > 1){
if(n%i==0){
n=n/i;
factores.add(i);
j++;
i=2;
}
else
i++;
}
return factores;
}
}
Clase Gaussiana
public class Gaussiana {
public void Gaussiana(int M[][], int Identidad[][], int filas, int columnas){
int i=0;
int k=0;
boolean band=true;
while(i< filas-1){
for(int j=0;j< columnas && band==true;j++){
if(M[i][j]==1){
k=j;
band=false;
}
}
if(band==false){
for(int u=i+1;u< filas;u++){
if(M[u][k]==1){
for(int w=0;w< columnas;w++){
M[u][w]^=M[i][w];
if(w< u){
Identidad[u][w]^=Identidad[i][w];
}
}
}
}
}
band=true;
i++;
}
}
}
Clase Identidad
public class Identidad {
public void crearMatrizIdentidad(int I[][],int filas){
for(int i=0;i< filas;i++){
for(int j=0;j< filas;j++){
if(i==j){
I[i][j]=1;
}
else{
I[i][j]=0;
}
}
}
}
}
Clase Jacobipublic class Jacobi {
CalcularExponente calcularExponente = new CalcularExponente();
SonCongruentes sonCongruentes = new SonCongruentes();
public int Jacobi(int a, int n){
int e=0,a1=1,n1=0,s=-2;
if(a==0 || a==1)
return a;
e=calcularExponente.hallarExponente(a);
a1=(int)(a/Math.pow(2,e));
if(e%2==0) // si 'e' es par
s=1;
else{
if((sonCongruentes.son_congruentes(n,1,8))||(sonCongruentes.son_congruentes(n,7,8)))
s=1;
else
if((sonCongruentes.son_congruentes(n,3,8))||(sonCongruentes.son_congruentes(n,5,8)))
s=-1;
}
if((sonCongruentes.son_congruentes(n,3,4))&&(sonCongruentes.son_congruentes(a1,3,4)))
s=-1*s;
n1=n%a1;
if(a1==1)
return s;
else
return (s*Jacobi(n1,a1));
}
}
Clase MCD
public class MCD {
public long mcd(long a, long b){
return (b == 0)? a : mcd(b, a % b);
}
}
Clase Potencia Prima
import java.util.ArrayList;
public class PotenciaPrima {
public boolean potenciaPrima(int n){
int i;
ArrayList< Integer > A = new ArrayList< >();
i=2;
while(n >1){
if(n%i==0){
n=n/i;
A.add(i);
i=2;
}
else
i++;
}
boolean band=true;
for(i=0;i < A.size()&&band==true;i++){
for(int o=0;o < A.size();o++){
if(A.get(i)!=A.get(o)){
band=false;
}
}
}
return band;
}
}
Clase Congruencia
public class SonCongruentes {
public boolean son_congruentes(long a, long b, long n){
if((a-b)%n==0)
return true;
else
return false;
}
}
0 comentarios: