Método de factorización de Dixon con implementación

El método de factorización de Dixon es un algoritmo de factorización de enteros. En este artículo se explica este método para encontrar los factores de un número compuesto .

La factorización de Dixon se basa en el conocido hecho de la teoría de números de que:

• Si es probable que mcd (x – y, n) sea factor de n .

Por ejemplo:

si N = 84923,
comenzando en 292, el primer número mayor que √N y contando hasta
5052 mod 84923 = 256 = 16 ²

Entonces (505 – 16)(505 + 16) = 0 mod 84923. Calcular
el máximo común divisor de 505 – 16 y N usando el algoritmo de Euclides da 163, que es un factor de N.

Algoritmo de factorización de Dixon:

• Paso 1: elige un límite B e identifica la base factorial (P) de todos los números primos menores o iguales que B.
• Paso 2: busque el entero positivo z , tal que sea B-Smooth.

  

  B-Smooth : Un entero positivo se llama B-Smooth si ninguno de sus factores primos es mayor que B.
  Por ejemplo:

  720 tiene factorización prima como 2 ⁴ * 3 ² * 5 ¹
  Por lo tanto, 720 es 5 suave porque ninguno de sus factores primos es mayor que 5.

• Paso 3: Después de generar suficientes de estas relaciones (generalmente algunas más que el tamaño de P), usamos el método de álgebra lineal (por ejemplo, Eliminación de Gauss ) para multiplicar estas relaciones. Repetir este paso hasta formar un número suficiente de cuadrados lisos.
• Paso 4: Después de multiplicar todas estas relaciones, obtenemos la ecuación final, digamos:

  a2 = b2 mod(N)
  

• Paso 5: Por lo tanto, los factores de la ecuación anterior se pueden determinar como:

  GCD(a - b, N), GCD(a + b, N)
  

Ejecución paso a paso del algoritmo de factorización de Dixon:

• Digamos que queremos factorizar N = 23449 usando el límite B = 7. Por lo tanto, la base factorial P = {2, 3, 5, 7}.
• Aquí, x = ceil(sqrt(n)) = 154. Por lo tanto, buscamos aleatoriamente enteros entre 154 y N cuyos cuadrados sean B-Smooth.
• Como se mencionó anteriormente, un entero positivo se llama B-Smooth si ninguno de sus factores primos es mayor que B. Entonces, digamos, encontramos dos números que son 970 y 8621 tales que ninguno de sus cuadrados tiene factores primos mayores que 7 .
• A partir de aquí los primeros cuadrados relacionados que obtenemos son:
  • 970 ² % 23499 = 2940 = 2 ² * 3 * 5 * 7 ²
  • 8621 ² % 23499 = 11760 = 2 ⁴ * 3 * 5 * 7 ²
• Entonces, (970 * 8621) ² = (2 ³ * 3 * 5 * 7 ² ) ² % 23499. Es decir:
  14256 ² = 5880 ² % 23499.
• Ahora, encontramos:

  gcd(14256 - 5880, 23449) = 131
  gcd(14256 + 5880, 23449) = 179

• Por lo tanto, los factores son:
  N = 131 * 179

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of Dixon factorization algo
#include<bits/stdc++.h>
using namespace std;
#include<vector>
  
// Function to find the factors of a number
// using the Dixon Factorization Algorithm
void factor(int n)
{
   
    // Factor base for the given number
    int base[4] = {2, 3, 5, 7};
   
    // Starting from the ceil of the root
    // of the given number N
    int start = int(sqrt(n));
   
    // Storing the related squares
    vector<vector<int> >pairs;
      
    // For every number from the square root 
    // Till N
    int len=sizeof(base)/sizeof(base[0]);
    for(int i = start; i < n; i++)
    {
        vector<int> v;
          
        // Finding the related squares 
        for(int j = 0; j < len; j++)
        {
            int lhs = ((int)pow(i,2))% n;
            int rhs = ((int)pow(base[j],2)) % n;
               
            // If the two numbers are the 
            // related squares, then append
            // them to the array 
            if(lhs == rhs)
            {
                v.push_back(i);
                v.push_back(base[j]);
                pairs.push_back(v);
            }
                  
        }
    }
   
    vector<int>newvec;
   
    // For every pair in the array, compute the 
    // GCD such that 
    len = pairs.size();
    for (int i = 0; i < len;i++){
        int factor = __gcd(pairs[i][0] - pairs[i][1], n);
           
        // If we find a factor other than 1, then 
        // appending it to the final factor array
        if(factor != 1)
            newvec.push_back(factor);
   
    }
    set<int>s;
    for (int i = 0; i < newvec.size(); i++)
        s.insert(newvec[i]);
    for(auto i = s.begin(); i != s.end(); i++)
        cout<<(*i)<<" ";
}
   
// Driver Code
int main()
{
    factor(23449);
}
  
// This code is contributed by chitranayal

# Python 3 implementation of Dixon factorization algo
  
from math import sqrt, gcd
import numpy as np
  
# Function to find the factors of a number
# using the Dixon Factorization Algorithm
def factor(n):
  
    # Factor base for the given number
    base = [2, 3, 5, 7]
  
    # Starting from the ceil of the root
    # of the given number N
    start = int(sqrt(n))
  
    # Storing the related squares
    pairs = []
  
    # For every number from the square root 
    # Till N
    for i in range(start, n):
  
        # Finding the related squares 
        for j in range(len(base)):
            lhs = i**2 % n
            rhs = base[j]**2 % n
              
            # If the two numbers are the 
            # related squares, then append
            # them to the array 
            if(lhs == rhs):
                pairs.append([i, base[j]])
  
    new = []
  
    # For every pair in the array, compute the 
    # GCD such that 
    for i in range(len(pairs)):
        factor = gcd(pairs[i][0] - pairs[i][1], n)
          
        # If we find a factor other than 1, then 
        # appending it to the final factor array
        if(factor != 1):
            new.append(factor)
  
    x = np.array(new)
  
    # Returning the unique factors in the array
    return(np.unique(x))
  
# Driver Code
if __name__ == "__main__":
    print(factor(23449))

[131 179]