Dado un entero positivo n , y que es compuesto, encuentre un divisor de él.
Ejemplo:
Input: n = 12; Output: 2 [OR 3 OR 4] Input: n = 187; Output: 11 [OR 17]
Método bruto: pruebe todos los números enteros menores que n hasta encontrar un divisor.
Improvisación: pruebe todos los números enteros menores que √n
Un número lo suficientemente grande aún significará una gran cantidad de trabajo. Pollard’s Rho es un algoritmo de descomposición en factores primos, particularmente rápido para un número compuesto grande con factores primos pequeños. El éxito más notable del algoritmo Rho fue la factorización del octavo número de Fermat: 1238926361552897 * 93461639715357977769163558199606896584051237541638188580280321.
El algoritmo Rho fue una buena elección porque el primer factor primo es mucho más pequeño que el otro.
Conceptos utilizados en el Algoritmo Rho de Pollard:
- Se dice que dos números x e y son congruentes módulo n (x = y módulo n) si
- su diferencia absoluta es un múltiplo entero de n, OR,
- cada uno de ellos deja el mismo resto cuando se divide por n.
- El Máximo Común Divisor es el número más grande que divide por igual a cada uno de los números originales.
- Paradoja del cumpleaños: la probabilidad de que dos personas tengan el mismo cumpleaños es inesperadamente alta incluso para un grupo pequeño de personas.
- Algoritmo de búsqueda de ciclos de Floyd: si la Turtle y la liebre comienzan en el mismo punto y se mueven en un ciclo tal que la velocidad de la liebre es el doble de la velocidad de la Turtle, entonces deben encontrarse en algún punto.
Algoritmo :
- Comience con x y c aleatorios. Toma y igual a x y f(x) = x 2 + c.
- Mientras no se obtenga un divisor
- Actualizar x a f(x) (módulo n) [Movimiento Turtle]
- Actualizar y a f(f(y)) (módulo n) [Hare Move]
- Calcular MCD de |xy| y N
- Si GCD no es la unidad
- Si GCD es n, repita desde el paso 2 con otro conjunto de x, y y c
- De lo contrario, GCD es nuestra respuesta
Ilustración:
Supongamos n = 187 y consideremos diferentes casos para diferentes valores aleatorios.
- Un ejemplo de valores aleatorios tales que el algoritmo encuentra el resultado :
y = x = 2 y c = 1, por lo tanto, nuestra f(x) = x 2 + 1.
- Un ejemplo de valores aleatorios en los que el algoritmo encuentra el resultado más rápido :
y = x = 110 y ‘c’ = 183. Por lo tanto, nuestra f(x) = x 2 + 183.
- Un ejemplo de valores aleatorios tales que el algoritmo no encuentra el resultado :
x = y = 147 y c = 67. Por lo tanto, nuestra f(x) = x 2 + 67.
A continuación se muestra la implementación C/C++ del algoritmo anterior:
C++
/* C++ program to find a prime factor of composite using
Pollard's Rho algorithm */
#include<bits/stdc++.h>
using namespace std;
/* Function to calculate (base^exponent)%modulus */
long long int modular_pow(long long int base, int exponent,
long long int modulus)
{
/* initialize result */
long long int result = 1;
while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent & 1)
result = (result * base) % modulus;
/* exponent = exponent/2 */
exponent = exponent >> 1;
/* base = base * base */
base = (base * base) % modulus;
}
return result;
}
/* method to return prime divisor for n */
long long int PollardRho(long long int n)
{
/* initialize random seed */
srand (time(NULL));
/* no prime divisor for 1 */
if (n==1) return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;
/* we will pick from the range [2, N) */
long long int x = (rand()%(n-2))+2;
long long int y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long long int c = (rand()%(n-1))+1;
/* Initialize candidate divisor (or result) */
long long int d = 1;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d==1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n)%n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n)%n;
y = (modular_pow(y, 2, n) + c + n)%n;
/* check gcd of |x-y| and n */
d = __gcd(abs(x-y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d==n) return PollardRho(n);
}
return d;
}
/* driver function */
int main()
{
long long int n = 10967535067;
printf("One of the divisors for %lld is %lld.",
n, PollardRho(n));
return 0;
}
Java
/* Java program to find a prime factor of composite using
Pollard's Rho algorithm */
import java.util.*;
class GFG{
/* Function to calculate (base^exponent)%modulus */
static long modular_pow(long base, int exponent,
long modulus)
{
/* initialize result */
long result = 1;
while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent % 2 == 1)
result = (result * base) % modulus;
/* exponent = exponent/2 */
exponent = exponent >> 1;
/* base = base * base */
base = (base * base) % modulus;
}
return result;
}
/* method to return prime divisor for n */
static long PollardRho(long n)
{
/* initialize random seed */
Random rand = new Random();
/* no prime divisor for 1 */
if (n == 1) return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;
/* we will pick from the range [2, N) */
long x = (long)(rand.nextLong() % (n - 2)) + 2;
long y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long c = (long)(rand.nextLong()) % (n - 1) + 1;
/* Initialize candidate divisor (or result) */
long d = 1L;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d == 1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n) % n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n) % n;
y = (modular_pow(y, 2, n) + c + n) % n;
/* check gcd of |x-y| and n */
d = __gcd(Math.abs(x - y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d == n) return PollardRho(n);
}
return d;
}
// Recursive function to return gcd of a and b
static long __gcd(long a, long b)
{
return b == 0? a:__gcd(b, a % b);
}
/* driver function */
public static void main(String[] args)
{
long n = 10967535067L;
System.out.printf("One of the divisors for " + n + " is " +
PollardRho(n));
}
}
// This code contributed by aashish1995
Python3
# Python 3 program to find a prime factor of composite using
# Pollard's Rho algorithm
import random
import math
# Function to calculate (base^exponent)%modulus
def modular_pow(base, exponent,modulus):
# initialize result
result = 1
while (exponent > 0):
# if y is odd, multiply base with result
if (exponent & 1):
result = (result * base) % modulus
# exponent = exponent/2
exponent = exponent >> 1
# base = base * base
base = (base * base) % modulus
return result
# method to return prime divisor for n
def PollardRho( n):
# no prime divisor for 1
if (n == 1):
return n
# even number means one of the divisors is 2
if (n % 2 == 0):
return 2
# we will pick from the range [2, N)
x = (random.randint(0, 2) % (n - 2))
y = x
# the constant in f(x).
# Algorithm can be re-run with a different c
# if it throws failure for a composite.
c = (random.randint(0, 1) % (n - 1))
# Initialize candidate divisor (or result)
d = 1
# until the prime factor isn't obtained.
# If n is prime, return n
while (d == 1):
# Tortoise Move: x(i+1) = f(x(i))
x = (modular_pow(x, 2, n) + c + n)%n
# Hare Move: y(i+1) = f(f(y(i)))
y = (modular_pow(y, 2, n) + c + n)%n
y = (modular_pow(y, 2, n) + c + n)%n
# check gcd of |x-y| and n
d = math.gcd(abs(x - y), n)
# retry if the algorithm fails to find prime factor
# with chosen x and c
if (d == n):
return PollardRho(n)
return d
# Driver function
if __name__ == "__main__":
n = 10967535067
print("One of the divisors for", n , "is ",PollardRho(n))
# This code is contributed by chitranayal
C#
/* C# program to find a prime factor of composite using
Pollard's Rho algorithm */
using System;
class GFG
{
/* Function to calculate (base^exponent)%modulus */
static long modular_pow(long _base, int exponent,
long modulus)
{
/* initialize result */
long result = 1;
while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent % 2 == 1)
result = (result * _base) % modulus;
/* exponent = exponent/2 */
exponent = exponent >> 1;
/* base = base * base */
_base = (_base * _base) % modulus;
}
return result;
}
/* method to return prime divisor for n */
static long PollardRho(long n)
{
/* initialize random seed */
Random rand = new Random();
/* no prime divisor for 1 */
if (n == 1) return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;
/* we will pick from the range [2, N) */
long x = (long)(rand.Next(0, -(int)n + 1));
long y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long c = (long)(rand.Next(1, -(int)n));
/* Initialize candidate divisor (or result) */
long d = 1L;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d == 1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n) % n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n) % n;
y = (modular_pow(y, 2, n) + c + n) % n;
/* check gcd of |x-y| and n */
d = __gcd(Math.Abs(x - y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d == n) return PollardRho(n);
}
return d;
}
// Recursive function to return gcd of a and b
static long __gcd(long a, long b)
{
return b == 0 ? a:__gcd(b, a % b);
}
/* Driver code */
public static void Main(String[] args)
{
long n = 10967535067L;
Console.Write("One of the divisors for " + n + " is " +
PollardRho(n));
}
}
// This code is contributed by aashish1995
Javascript
<script>
/* Javascript program to find a prime factor of composite using
Pollard's Rho algorithm */
/* Function to calculate (base^exponent)%modulus */
function modular_pow(base,exponent,modulus)
{
/* initialize result */
let result = 1;
while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent % 2 == 1)
result = (result * base) % modulus;
/* exponent = exponent/2 */
exponent = exponent >> 1;
/* base = base * base */
base = (base * base) % modulus;
}
return result;
}
/* method to return prime divisor for n */
function PollardRho(n)
{
/* no prime divisor for 1 */
if (n == 1)
return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0)
return 2;
/* we will pick from the range [2, N) */
let x=(Math.floor(Math.random() * (-n + 1) ));
let y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
let c= (Math.floor(Math.random() * (-n + 1)));
/* Initialize candidate divisor (or result) */
let d=1;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d == 1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n) % n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n) % n;
y = (modular_pow(y, 2, n) + c + n) % n;
/* check gcd of |x-y| and n */
d = __gcd(Math.abs(x - y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d == n) return PollardRho(n);
}
return d;
}
// Recursive function to return gcd of a and b
function __gcd(a,b)
{
return b == 0? a:__gcd(b, a % b);
}
/* driver function */
let n = 10967535067;
document.write("One of the divisors for " + n + " is " +
PollardRho(n));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
One of the divisors for 10967535067 is 104729
Complejidad del tiempo: O(sqrt(n)*logn)
Espacio auxiliar: O(1)
¿Cómo funciona esto?
Sea n un compuesto (no primo) . Dado que n es compuesto, tiene un factor no trivial f < n. De hecho, hay al menos una f <= √n .
Ahora supongamos que tenemos que elegir dos números x e y del rango [0, n-1]. La única vez que obtenemos x = y módulo n es cuando xey son idénticos. Sin embargo, dado que f < √n, existe una buena probabilidad de que x = y módulo f incluso cuando xey no son idénticos ( paradoja del cumpleaños ).
Comenzamos seleccionando aleatoriamente x con reemplazo del conjunto {0, 1, …, n-1} para formar una secuencia s 1 , s 2 , s 3 … Definiendo ś yo = si mod f , nuestra secuencia ahora tiene cada ś i perteneciente a {0, 1, …, f-1}. Debido a que ambos conjuntos son finitos, eventualmente habrá un número entero repetido en ambos. Esperamos lograr la repetición anterior en ś i , ya que f < n.
Ahora, di ś i = ś j para i ≠ j, entonces, s i = s j módulo d. Y por tanto, |s i – s j | será múltiplo de f. Como se supuso anteriormente, n también es un múltiplo de f. Juntos, esto significa que MCD de |s i – s j | y n será múltiplo entero positivo de f, ¡y también nuestro candidato a divisor d!El problema aquí es que sabíamos que tenía que haber algún divisor de n, y ni siquiera nos importaba su valor. Una vez que llegamos a s i y s j (nuestros x e y finales), entonces cada elemento en la secuencia que comienza con s i será congruente módulo f con el elemento correspondiente en la secuencia que comienza con s j , y por lo tanto, un ciclo. Si graficamos la sucesión s i , observaremos la forma de la letra griega Rho (ρ).
El corazón del algoritmo Rho es recoger valores aleatorios y evaluar GCD. Para disminuir los costosos cálculos de GCD, podemos implementar la Rho de Pollard con la detección del ciclo de Floyd (que se puede entender con la analogía de la liebre-Turtle donde la Turtle se mueve a través de cada elemento uno a la vez en orden, y la liebre comienza en el mismo punto pero se mueve el doble de rápido que la Turtle). Tendremos algún polinomio f(x) para lo mismo, comenzamos con x 0 aleatorio , y 0 = x 0 , y calculamos x i+1 = f(x i ) y y i+1 = f(f(y i ) ). Como no sabemos mucho acerca de d, una opción típica para el polinomio es f(x) = x 2 + c (módulo n) (Sí, ‘c’también se elegirá al azar ).
Nota:
- El algoritmo se ejecutará indefinidamente para números primos.
- Es posible que el algoritmo no encuentre los factores y devuelva un error para el compuesto n. En ese caso, usamos un conjunto diferente de x, y y c y lo intentamos de nuevo.
- El algoritmo anterior solo encuentra un divisor. Para encontrar un factor primo, podemos factorizar recursivamente el divisor d, ejecutar el algoritmo para d y n/d. La duración del ciclo es típicamente del orden de √d.
Análisis de Complejidad de Tiempo:
El algoritmo ofrece una compensación entre su tiempo de ejecución y la probabilidad de que encuentre un factor. Se puede lograr un divisor primo con una probabilidad de alrededor de 0,5, en O(√d) <= O(n 1/4 ) iteraciones. Esta es una afirmación heurística, y el análisis riguroso del algoritmo permanece abierto.
Este artículo es una contribución de Yash Varyani . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA