Ниже приведен пример алгоритма на Java (это не C ++ с GMP, но преобразование должно быть довольно простым), который:
- генерирует случайное число
x битовой длины Nbits
- пытается выделить все основные факторы <100, сохраняя список простых факторов, которые делят x. </li>
- проверяет, является ли оставшийся фактор простым, используя Java
isProbablePrime метод
- Если оставшееся произведение на множители является простым с достаточной вероятностью, нам удалось разложить x. ( STOP )
- В противном случае оставшийся факторный продукт определенно является составным (см. Документы isProbablePrime).
- Пока у нас еще есть время, мы запускаем алгоритм Полларда , пока не найдем делитель d.
- Если у нас заканчивается время, мы терпим неудачу. ( СТОП )
- Мы нашли делитель d. Таким образом, мы вычленяем d, добавляем простые множители d в список простых факторов x и переходим к шагу 4.
Все параметры этого алгоритма находятся в начале списка программ. Я искал 1024-битные случайные числа с таймаутом 250 миллисекунд, и я продолжаю запускать программу, пока не получу число x, по крайней мере, с 4 простыми факторами (иногда программа находит число с 1, 2 или 3 простыми факторами первый). С этим установленным параметром на iMac 2,66 ГГц обычно требуется около 15-20 секунд.
Алгоритм Полларда не очень эффективен, но он прост по сравнению с квадратичным ситом (QS) или общим числовым ситом (GNFS) - я просто хотел посмотреть, как работает простой алгоритм.
Почему это работает: (несмотря на утверждение многих из вас, что это сложная проблема)
Простой факт в том, что простые числа не так уж редки . Для 1024-битных чисел теорема о простых числах говорит, что примерно 1 на каждые 1024 ln 2 (= около 710)
числа простые.
Так что, если я сгенерирую случайное число x, которое будет простым, и я приму вероятностное обнаружение простого числа, я успешно вычислю x.
Если это не простое число, но я быстро выделяю несколько небольших факторов, а оставшийся фактор является (вероятностно) простым, то я успешно разложил множитель x.
В противном случае я просто сдаюсь и сгенерирую новое случайное число. (что ОП говорит, что приемлемо)
У большинства успешно вычисленных чисел будет 1 большой простой множитель и несколько маленьких простых.
Числа, на которые трудно рассчитывать, это те, у которых нет простых простых факторов и, по крайней мере, 2 больших простых фактора (к ним относятся криптографические ключи, которые являются произведением двух больших чисел; OP ничего не сказал о криптографии), и Я могу просто пропустить их, когда у меня заканчивается время.
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;
}
}