c++ - Factoriza un gran número de manera eficiente con GMP

math primes

Question

Necesito obtener todos los factores primos de números grandes que pueden llegar fácilmente a 1k bits. Los números son prácticamente aleatorios, así que no debería ser difícil. ¿Cómo lo hago de manera eficiente? Yo uso C ++ con la biblioteca GMP.

EDIT: supongo que todos me han malentendido.
Lo que quiero decir con un número primo es obtener todos los factores primos del número.
Lo siento por mi inglés, en mi idioma prime y factor son lo mismo :)

aclaración (de la otra publicación de OP):

Lo que necesito es una forma de factorizar de manera eficiente (encontrar factores primos de un número) números grandes (puede llegar a 2048 bits) utilizando C ++ y GMP (lib de precesión múltiple Gnu) o menos preferiblemente de otra manera. Los números son prácticamente aleatorios, por lo que hay pocas posibilidades de que sea difícil factorizar, e incluso si el número es difícil de factorizar, puedo repetir el número (aunque no puedo elegir).

Answer 1

Un buen comienzo sería un prefiltrado con primos pequeños, por ejemplo, sobre todos los números primos inferiores a 100.000 o más. Simplemente intente dividir por cada uno de ellos (cree una tabla que luego cargue en tiempo de ejecución o tenga como datos estáticos en su código). Puede parecer lento y estúpido, pero si el número es totalmente aleatorio, esto le dará algunos factores muy rápido con una gran probabilidad. Luego mira el número restante y decide qué hacer a continuación. Si es bastante pequeño (lo que "pequeño" significa que depende de usted) podría intentar una prueba de primalidad (creo que hay algo en GMP) y si le da una prima, en la mayoría de los casos puede confiar en ella. De lo contrario, debes factorizarlo más.

Si tus números son realmente enormes y te preocupa el rendimiento, definitivamente necesitas implementar algo más sofisticado que una división estúpida. Mira el Tamiz Cuadrático (prueba wikipedia). Es bastante simple pero muy poderoso. Si está hasta el límite, pruebe con MPQS, una variante del algoritmo de tamiz cuadrático. Este foro es una buena fuente de información. Incluso hay implementaciones existentes de una herramienta que necesita; vea, por ejemplo, esto .

Sin embargo, tenga en cuenta que los números con 1k bits son enormes por todos los medios. Factorizar ese número (incluso con MPQS u otros) puede tomar años si tienes suerte y para siempre si no. Creo que MPQS funciona bien con números de alrededor de 100-400 bits (si están compuestos por dos números primos casi iguales, que es el caso más difícil, por supuesto).

Answer 2

A continuación se muestra un algoritmo de muestra en Java (no es C ++ con GMP, pero la conversión debe ser bastante sencilla) que:

1. genera un número aleatorio x de bitbits Nbits
2. intenta factorizar todos los factores primos <100, manteniendo una lista de factores primos que dividen x.
3. prueba para ver si el factor restante es primordial usando el método isProbablePrime de Java
4. Si el producto de factor restante es primo con probabilidad suficiente, hemos tenido éxito en factorizar x. ( STOP )
5. De lo contrario, el producto de factor restante es definitivamente compuesto (consulte los documentos de isProbablePrime).
6. Mientras todavía tenemos tiempo, ejecutamos el algoritmo Pollard rho hasta que encontremos un divisor d.
7. Si nos quedamos sin tiempo, hemos fallado. ( STOP )
8. Hemos encontrado un divisor d. Entonces, 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, en comparación con el tamiz cuadrático (QS) o el tamiz general de campo numérico (GNFS); solo quería ver cómo funcionaba el algoritmo simple.

Por qué esto funciona: (a pesar del reclamo de muchos de ustedes de que este es un problema difícil)

La simple realidad es que los números primos no son tan raros . Para números de 1024 bits, el Teorema del Número Principal dice que aproximadamente 1 de cada 1024 ln 2 (= aproximadamente 710) números es primo.

Entonces, si genero un número aleatorio x que sea primo, y acepto detección de probabilidad probabilística, he factorizado con éxito x.

Si no es primo, pero rápidamente factorizo ​​algunos pequeños factores, y el factor restante es (probabilísticamente) primo, entonces he factorizado con éxito x.

De lo contrario, simplemente me rindo y generaré un nuevo número aleatorio. (que el OP dice que es aceptable)

La mayoría de los números factorizados con éxito tendrán 1 factor primo grande y algunos factores primos pequeños.

Los números que son difíciles de factorizar son aquellos que no tienen factores primarios pequeños y al menos 2 factores primarios 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 simplemente omítalos 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;
}
}

Answer 3

Por el momento no puedes factorizar un bigint con GMP. Puede convertir su bigint a otras bibliotecas y usar sus algoritmos de factorización. Tenga en cuenta que el factoring de enteros con >> 20 dígitos necesita algoritmos especializados y es casi exponencialmente lento.

Revisa:

• http://flintlib.org/
• http://pari.math.u-bordeaux.fr/
• http://ecm.gforge.inria.fr/

Answer 4

Puede usar el algoritmo de factorización Pollard p-1 si el número que desea factorizar tiene factores primarios pequeños. Se ha factorizado un factor primo de 30 dígitos del número 2 ^ 740 + 1. ECM es un algoritmo similar pero sub-exponencial, pero la implementación es más difícil. La cantidad de tiempo que el algoritmo se basa en cómo se establece el límite b. Factorizará cualquier número que tenga un factor p donde p - 1 sea b-suave.

//Pollard p - 1 factorization algorithm
void factor(mpz_t g, mpz_t n, long b)
{
//sieve for primes
std::vector<bool> r;
for(int i = 0; i < b; i++)
r.push_back(true);
for(int i = 2; i < ceil(sqrt(b - 1)); i++)
if(r.at(i) == true)
for(int j = i * i; j < b; j += i)
r.at(j) = false;
std::vector<long> p;
std::vector<long> a;
for(int i = 2; i < b; i++)
if(r[i] == true)
{
p.push_back(i);//Append the prime on to the vector
int temp = floor(log(b) / log(i)); //temp = logb(i)
// put primes in to sieve
// a = the maximum power for p ^ a < bound b
if(temp == 0)
a.push_back(1);
else
a.push_back(temp);
}
int m = p.size();//m = number of primes under bound b
mpz_t c;// c is the number Which will be exponated
mpz_init(c);
long two = 2;
mpz_set_ui(c, two);// set c to 2
int z = 0;
long x = 2;
// loop c until a factor is found
for(;;)
{
mpz_set_si( c, x);
//powering ladder
for(long i = 0; i < m; i++)
for(long j = 0; j < a[i]; j++)
mpz_powm_ui(c , c, (p[i]), n);
//check if a factor has been found;
mpz_sub_ui(c ,c,1);
mpz_gcd(g ,c, n);
mpz_add_ui(c , c, 1);
//if g is a factor return else increment c
if((mpz_cmp_si(g,1)) > 0 && (mpz_cmp(g,n)) < 0)
return;
else if (x > b)
break;
else
x++;
}
}
int main()
{
mpz_t x;
mpz_t g;
//intialize g and x
mpz_init(g);
mpz_init_set_str(x,"167698757698757868925234234253423534235342655234234235342353423546435347",10);
//p-1 will factor x as long as it has a factor p where p - 1 is b-smooth(has all prime factors less than bound b)
factor(g , x, 1000);
//output the factor, it will output 1 if algorithm fails
mpz_out_str(NULL, 10, g);
return 0;
}

Salidas - 7465647 Tiempo de ejecución - 0.003 segundos

Otro algoritmo de Factoring creado por J.Pollard fue el algoritmo Pollards Rho, que no es tan rápido, pero requiere muy poco espacio. También hay formas de parrelizarlo. Su complejidad es O (n ^ 1/4)

//Pollard rho factoring algorithm
void rho(mpz_t g, mpz_t n)
{
mpz_t x;
mpz_t y;
mpz_init_set_ui(x ,2);
mpz_init_set_ui(y ,2);//initialize x and y as 2
mpz_set_ui(g , 1);
mpz_t temp;
mpz_init(temp);
if(mpz_probab_prime_p(n,25) != 0)
return;//test if n is prime with miller rabin test
int count;
int t1 = 0;
int t2 = 1;
int nextTerm = t1 + t2;
while(mpz_cmp_ui(g,1) < 1)
{
f(x,n);//x is changed
f(y,n);//y is going through the sequence twice as fast
f(y,n);
if(count == nextTerm)//calculate gcd every fibonacci number
{
mpz_sub(temp,x,y);
mpz_gcd(g , temp, n);
t1 = t2;
t2 = nextTerm;
nextTerm = t1 + t2;//calculate next fibonacci number
}
count ++;
}
return;
}
int main()
{
mpz_t x;
mpz_t g;
//intialize g and x
mpz_init(g);
mpz_init_set_str(x,"167698757698757868925234234253423",10);
rho(g , x);
//output the factor, it will output 1 if algorithm fails
mpz_out_str(NULL, 10, g);
return 0;
}

Salidas - 353 Tiempo de ejecución - 0.003s