Программно факторизовать большое количество

Question

Хорошо, у меня есть огромное количество f, Это число длиной чуть более 100 цифр. Я знаю, что факторы примерно одинакового размера.

Если у меня ограниченные ресурсы и время, какой язык и алгоритм я должен использовать? Я в том числе время, чтобы код алгоритма в ограниченное время.

Мысли?

РЕДАКТИРОВАТЬ: Под ограниченным я имею в виду как можно меньше времени.

Answer 1

Современный алгоритм первичной факторизации - это квадратичное сито и его варианты. Для чисел больше 100 цифр сито становится более эффективным.

Здесь есть реализация с открытым исходным кодом. Он способен разбить100-значное число на два примерно одинаковых простых числа всего за 4 часа на 2,2 ГГц AMD Althon.

Итак, есть алгоритм и пример реализации. Этого может быть достаточно, чтобы дать вам идеи или начать.

Answer 2

Это звучит как хорошее упражнение (и, возможно, редкий хороший пример) для облачных вычислений. Это должно быть легко для запуска параллельной обработки. Разделите ваши пулы факторов по каждому из ваших процессов.

Нечто подобное может оказаться полезным: http://blog.controlgroup.com/2010/10/13/hadoop-and-amazon-elastic-mapreduce-analyzing-log-files/ Подробнее на http://en.wikipedia.org/wiki/Apache_Hadoop.

(В прошлом месяце я смотрел прекрасную видео-демонстрацию того, как можно увидеть нечто похожее на то, что я предлагаю здесь - но, конечно, сейчас я не могу найти ссылку.)

Особенно, если вам не нужно делать это программно, взгляните на http://www.alpertron.com.ar/ECM.HTM. (Ссылка на http://en.wikipedia.org/wiki/Quadratic_sieve.) Обратите особое внимание на примечания в разделе "Факторинг числа на нескольких машинах" в первой ссылке. (Поскольку исходный код доступен, вы можете запустить его также программно распределенным способом, используя Hadoop или тому подобное.)

Answer 3

while (x < Number) {
    if ((Number % x) == 0 ) { 
        cout << x << "*" << Number/x << endl;
        ++x;
    }  
    else ++x;
}