A continuación se muestra un algoritmo muestra en Java (que no es C++ con GMP, pero la conversión debe ser bastante sencillo) que:
- genera un número aleatorio
x de bitlength Nbits
- intentos para factorizar todos primos factores < 100, manteniendo una lista de factores principales que se dividen en x.
- prueba para ver si el factor restante es primordial utilizando el método
isProbablePrime de Java
- Si el producto de factor restante es primo con suficiente probabilidad, hemos tenido éxito en factorizar x. (STOP)
- De lo contrario, el producto de factor restante es definitivamente compuesto (consulte los documentos de isProbablePrime).
- Mientras todavía tenemos tiempo, ejecutamos el Pollard rho algorithm hasta que encontremos un divisor d.
- Si nos quedamos sin tiempo, hemos fallado. (STOP)
- Hemos encontrado un divisor d. Así que factorizamos d, sumamos los factores primos de d a la lista de factores primos de x, y avanzamos al paso 4.
Todos los parámetros de este algoritmo están cerca del comienzo de la lista de programas. Busqué números aleatorios de 1024 bits, con un tiempo de espera de 250 milisegundos, y sigo ejecutando el programa hasta que obtengo un número x con al menos 4 factores primos (a veces el programa encuentra un número con 1, 2 o 3 factores primos) primero). Con este parámetro establecido, generalmente toma alrededor de 15-20 segundos en mi iMac de 2.66Ghz.
El algoritmo rho de Pollard no es tan eficiente, pero es simple, comparado con el quadratic sieve (QS) o el general number field sieve (GNFS) - Solo quería ver cómo funcionaba el algoritmo simple.
Por qué esto funciona: (a pesar de la afirmación de que muchos de ustedes que este es un problema difícil)
El simple hecho de que es, que prime numbers aren't that rare. Para números de 1024 bits, el teorema del número principal dice que aproximadamente 1 de cada 1024 ln 2 (= alrededor de 710) números es primo.
Así que si genero un número aleatorio x que es primo, y acepto detección de probabilidad probabilística, he factorizado con éxito x.
Si no es primo, pero rápidamente factorizo algunos factores pequeños, y el factor restante es (probabilísticamente) primo, entonces he factorizado con éxito x.
De lo contrario, me rindo y genero un nuevo número aleatorio. (que el OP dice que es aceptable)
La mayoría de los números cuentan correctamente con 1 factor primo de Gran tamaño y algunos factores primos pequeños.
Los números que son difíciles de factorizar son aquellos que no tienen factores primos pequeños y al menos 2 factores primos grandes (estos incluyen claves criptográficas que son el producto de dos números grandes, el OP no ha dicho nada acerca de la criptografía). y puedo omitirlos cuando me quede sin tiempo.
package com.example;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class FindLargeRandomComposite {
final static private int[] smallPrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97};
final static private int maxTime = 250;
final static private int Nbits = 1024;
final static private int minFactors = 4;
final static private int NCERTAINTY = 4096;
private interface Predicate { public boolean isTrue(); }
static public void main(String[] args)
{
Random r = new Random();
boolean found = false;
BigInteger x=null;
List<BigInteger> factors=null;
long startTime = System.currentTimeMillis();
while (!found)
{
x = new BigInteger(Nbits, r);
factors = new ArrayList<BigInteger>();
Predicate keepRunning = new Predicate() {
final private long stopTime = System.currentTimeMillis() + maxTime;
public boolean isTrue() {
return System.currentTimeMillis() < stopTime;
}
};
found = factor(x, factors, keepRunning);
System.out.println((found?(factors.size()+" factors "):"not factored ")+x+"= product: "+factors);
if (factors.size() < minFactors)
found = false;
}
long stopTime = System.currentTimeMillis();
System.out.println("Product verification: "+(x.equals(product(factors))?"passed":"failed"));
System.out.println("elapsed time: "+(stopTime-startTime)+" msec");
}
private static BigInteger product(List<BigInteger> factors) {
BigInteger result = BigInteger.ONE;
for (BigInteger f : factors)
result = result.multiply(f);
return result;
}
private static BigInteger findFactor(BigInteger x, List<BigInteger> factors,
BigInteger divisor)
{
BigInteger[] qr = x.divideAndRemainder(divisor);
if (qr[1].equals(BigInteger.ZERO))
{
factors.add(divisor);
return qr[0];
}
else
return x;
}
private static BigInteger findRepeatedFactor(BigInteger x,
List<BigInteger> factors, BigInteger p) {
BigInteger xprev = null;
while (xprev != x)
{
xprev = x;
x = findFactor(x, factors, p);
}
return x;
}
private static BigInteger f(BigInteger x, BigInteger n)
{
return x.multiply(x).add(BigInteger.ONE).mod(n);
}
private static BigInteger gcd(BigInteger a, BigInteger b) {
while (!b.equals(BigInteger.ZERO))
{
BigInteger nextb = a.mod(b);
a = b;
b = nextb;
}
return a;
}
private static BigInteger tryPollardRho(BigInteger n,
List<BigInteger> factors, Predicate keepRunning) {
BigInteger x = new BigInteger("2");
BigInteger y = x;
BigInteger d = BigInteger.ONE;
while (d.equals(BigInteger.ONE) && keepRunning.isTrue())
{
x = f(x,n);
y = f(f(y,n),n);
d = gcd(x.subtract(y).abs(), n);
}
if (d.equals(n))
return x;
BigInteger[] qr = n.divideAndRemainder(d);
if (!qr[1].equals(BigInteger.ZERO))
throw new IllegalStateException("Huh?");
// d is a factor of x. But it may not be prime, so run it through the factoring algorithm.
factor(d, factors, keepRunning);
return qr[0];
}
private static boolean factor(BigInteger x0, List<BigInteger> factors,
Predicate keepRunning) {
BigInteger x = x0;
for (int p0 : smallPrimes)
{
BigInteger p = new BigInteger(Integer.toString(p0));
x = findRepeatedFactor(x, factors, p);
}
boolean done = false;
while (!done && keepRunning.isTrue())
{
done = x.equals(BigInteger.ONE) || x.isProbablePrime(NCERTAINTY);
if (!done)
{
x = tryPollardRho(x, factors, keepRunning);
}
}
if (!x.equals(BigInteger.ONE))
factors.add(x);
return done;
}
}
¿Cómo que por primera en este contexto? ¿Estás tratando de generar números primos grandes? ¿O quieres decir preparar los números antes de tiempo para algún uso particular? – DGH
Empuja el pequeño botón blando en el costado del número para subirlo unas cuantas muescas, por lo que es perfecto y el motor comienza a funcionar sin problemas. – Potatoswatter
Estoy de acuerdo, el inglés sobre esto es tan malo que puedo adivinar lo que significaba el OP, pero ciertamente no está claro. – Omnifarious