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

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#Hadoop_on_Amazon_EC2.2FS3_services.

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

Особенно, если вам не нужно делать это программно, взгляните на 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;
}