IMPLEMENTACION DEL ALGORITMO RHO POLLARD EN JAVA

El algoritmo rho de Pollard es un algoritmo especializado de factorización de números enteros. Fue inventado por John Pollard en 1975. Es especialmente efectivo a la hora de factorizar números compuestos que tengan factores pequeños.

El algoritmo rho emplea pues una función módulo n a modo de generador de una secuencia pseudoaleatoria. Hace funcionar una de las secuencias el doble de rápido que la otra, es decir, por cada iteración de una de las copias de la secuencia, la otra hace dos iteraciones. Sea x el estado actual de una secuencia e y el estado actual de la otra. En cada paso se toma el máximo común divisor (MCD) de |x − y| y n. Si este MCD llega a ser n, entonces finaliza el algoritmo con el resultado de fracaso, ya que esto significa que x = y y, por el algoritmo de la liebre y la tortuga, la secuencia ya ha completado su ciclo y seguir más allá sólo conseguiría repetir trabajo ya realizado.

Algoritmo:

Entrada:  Un número entero  “n” que no sea una potencia prima. 
Salida : Factor no trivial de «n»
a ← 2;
b ← 2;
PARA (i = 1, 2, . . .);
a ← a2 + 1 mod n;
b ← b2 + 1 mod n;
b ← b2 + 1 mod n;
d ← mcd(abs(a – b), n);
SI (1 < d < n)
Retornar d; 
SI (d >= n)
Retornar Sin exito; 
FIN PARA;
//Observación: Una potencia prima es una potencia entera y positiva de un
// número primo. Por ejemplo 5=5¹, 9=3² son potencias primas, 
//mientras que 6=2×3, 15=3×5 y 36=6²=2²×3² no lo son.

Implementación: 

Nota:La función rho usa como función auxiliar una llamada mcd, puedes usar cualquiera que ya hallas implementado en mi caso yo use el algoritmo de euclides extendido (ver publicación acerca de euclides extendido).

Función rho:

public boolean rho()
    {
        int a=2, b=2,d=1;
        boolean bandera;
        while(d==1)
        {
            a=((a*a)+1)%numero;
            b=((b*b)+1)%numero;
            b=((b*b)+1)%numero;
            d=(int) EuclidesIterativo(abs(a-b),numero);
            ca.add(a);
            cb.add(b);
            cd.add(d);
        }
        if(d>1 && d < numero)
        {
            bandera=true;
            return  bandera;
        }
        else
        {
            //NO EXISTE FACTOR TRIVIAL
            bandera=false;
            return bandera;
        }
    }
//Estoy almacenando cada valor que toma a,b y d para mostrarlo posteriormente
//en una interfaz, pero si deseas obtener el primer factor directamente , basta
//con imprimir el ultimo valor de "d".

Ejemplo:
Sea n = 8051 un número entero, el algoritmo reporta el factor no trivial 97. El otro factor es 83(Este factor se obtiene dividiendo n entre el factor no trivial obtenido por el algoritmo de Rho Pollard).

• Tweet
• Share
• Share
• Share
• Share