Hola, esta publicación requiere de un conocimiento o amenos algo de estudio acerca de este algoritmo, te recomiendo que investigues un poco mas sobre este algoritmo antes de tratar de entender el código.
Un poco de Teoría:
Carl Prométanse, un matemático estadounidense especializado en teoría de números, propuso en 1981 un algoritmo llamado criba cuadrática (Quadratic Sieve) que se encargaba de la factorización de números enteros, extendía las ideas de Dixon y de Kraitchik. La criba cuadrática era el algoritmo de factorización mas rápido hasta que se descubrió la criba general del cuerpo de números (Number Field Sieve) en torno a 1993. No obstante, la criba cuadrática sigue siendo incluso más rápida que la criba general del cuerpo de números cuando se trata de números menores de 110 dígitos aproximadamente. Se ubica en los algoritmos de factorización de propósito General.
Algoritmo:
Explicación del Algoritmo:
Lograr entender el algoritmo es un poco complicado si lo tratamos de leer como se muestra el algoritmo con operaciones matemáticas de manera que aquí te voy a dar algunos pasos en los que consiste el algoritmo.Antes de empezar hago suposición de que sabes operaciones modulares las que se aplican en Zn .
En el algoritmo definirás el tamaño máximo de la base y de los números aleatorios (-c,c).
Paso 1: Debemos seleccionar una base de números que son residuo cuadrático de n, para hacer esto solo debemos aplicar el algoritmo de Jacobi, este algoritmo devolverá 1 si es residuo cuadrático y -1 si no lo es. Se seleccionara los números hasta el rango indicado por ejemplo si el rango es 30 se escogerán los números que cumplen ser residuo cuadrático hasta ese numero.
Paso 2: Debemos sacarle la raíz cuadrada al numero n.
Paso 3: Obtenemos un vector de números x tales que será la suma de la raíz cuadrada mas el rango de aleatorios.
Paso 4: Encontraremos un vector de números tales que sera la función de x , donde elevaremos a x al cuadrado y restaremos el numero.
Paso 5: A este vector de f(x) seleccionaremos solo los que son lisos(suaves), en otras palabras los que su factorización en números de la base cumplen con el rango de números, le asignaremos a cada factor que cumple el numero de su exponente y al que no cero.
Paso 6: A la matriz anterior obtenida le sacaremos modulo 2 para obtener solo una matriz binaria.
Paso 7: Escogeremos las filas de la matriz que cumple que su suma en modulo 2 da cero.
Paso 8: en los vectores de x multiplicaremos a todos los números que cumplieron el paso anterior y sacaremos modulo 2 obteniendo una variable X.
Paso 9: en los vectores de f(x) multiplicaremos a todos los números que cumplieron el paso 7 y obtendremos una variable Y^2 y le sacaremos la raiz para obtener Y.
Paso 10: obtenidos X y Y sacaremos el máximo común divisor de X+Y con n y obtendremos un factor no trivial de n, y sacamos también el máximo común divisor de X-Y con n y se obtendrá el otro factor no trivial estos dos factores será los factores de n.
Ejemplo:
Factorizar n=87453
Sea B=30 el máximo rango de números de la base
Sea (–C,C)= (-35,35) el rango de números aleatorios
Paso 1: Encontramos los números que son residuo cuadrático de n.
Paso 2: m=√n, m= 295
Paso 3 ,4 ,5,6. Donde obtendremos esta matriz de números lisos
Paso 8: X=296*316 = 6073
Paso 9: Y^2 = 153*12393, Y= 1377
Paso 10: mcd(X-Y,n)= 587 y mcd(X+Y,n)= 149
Para verificación 587*149= 87463
Implementacion en C++:
Prueba:
Esto es todo lo que te puedo compartir, recuerda que si te sirvió me ayudarías mucho dando Like a mi pagina de Facebook, tambien este codigo lo puedes compartir, pero recuerda que es mi esfuerzo hacerlo asi que me gustaría que dejes mis créditos, gracias.
SOCIALIZA ESTO →