программа для факторизации числа

[eBoris]

Добрый день!

Стоит задача факторизации числа на простые множители. Думал, что под ubuntu сразу найду готовую программу, но всё оказалось не совсем просто. Вышел на руководство для новичков http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html , но ggnfs надо скомпилировать самому, запустил make, а он требует gmp.h, который неизвестно в каком пакете есть

Подскажите, пожалуйста, есть ли готовая программа, которой можно дать число и она будет пытаться раскладывать его на простые множители? Желательно, чтобы можно было делать паузу, хотя это и не принципиально.

Заранее спасибо!

[inkblack]

В Ubuntu 10.10 такая фича есть в калькуляторе.

Но в пакетном режиме, конечно не запустишь.
Считает _Очень_ медленно, разложения числа 1111111111111111111 (19 единиц) я так и не дождался (несколько часов).

Есть еще программа gcalccmd, но как ей пользоваться — не знаю, а мана нет.


Да, в той статье идет речь про 100-значные числа, калькулятор в пролёте...

[eBoris]

Да, в той статье идет речь про 100-значные числа, калькулятор в пролёте...

У меня число всего лишь 128 битное, а это примерно 40 символов, поэтому простым перебором совсем не хочется, хотя за несколько дней и получилось бы.
С другой стороны, задача встала разовая, поэтому совсем не хочется погружаться в алгоритмы и т.п.

P.S. никак не могу привыкнуть, что всё самому собирать надо, а оно в редких случаях соберётся сразу 

[inkblack]

Ну, попробуйте калькулятором, хотя вряд ли он справится. 40 цифр — много. Но вдруг _повезёт_??

[eBoris]

наставил разных библиотек с похожими названиями - приложения из статьи скомпилировались

тему можно закрывать

[Tarasov]

можно самому прогу написать

[Ankor]

Я не догоняю: нужно найти факториал или что? Вроде как это проще написать самому, чем искать в сети. Ищут либо от лени, либо от того, что проект действительно обладает определённой сложностью.

[Jack Sparrow]

Код: [Выделить]

man factor
factor число


[eBoris]

Код: [Выделить]

man factor
factor число


действительно, удобная программа, но больше 20 десятизначных разрядов не работает, а так - то, что надо
Пользователь решил продолжить мысль 28 Февраля 2011, 17:55:38:

Я не догоняю: нужно найти факториал или что? Вроде как это проще написать самому, чем искать в сети. Ищут либо от лени, либо от того, что проект действительно обладает определённой сложностью.

надо разложить большое число на простые множители; простой перебор работает медленно, поэтому придуманы различные хитрые алгоритмы, которые позволяют этот перебор ускорить

[inkblack]

Код: [Выделить]

man factor
factor число


действительно, удобная программа, но больше 20 десятизначных разрядов не работает, а так - то, что надо

Если точнее, то

Код: [Выделить]

p@e4:~$ factor 18446744073709551616
factor: «18446744073709551616» слишком велик
p@e4:~$ factor 18446744073709551615
18446744073709551615: 3 5 17 257 641 65537 6700417
p@e4:~$
Число должно быть < 2^64.
Но в info factor сказано:

   Factoring the product of the eighth and ninth Mersenne primes takes
about 30 milliseconds of CPU time on a 2.2 GHz Athlon.

     M8=`echo 2^31-1|bc` ; M9=`echo 2^61-1|bc`
     /usr/bin/time -f '%U' factor $(echo "$M8 * $M9" | bc)
     4951760154835678088235319297: 2147483647 2305843009213693951
     0.03

   Similarly, factoring the eighth Fermat number 2^256+1 takes about 20
seconds on the same machine.

 ...

   If `factor' is built without using GNU MP, only single-precision
arithmetic is available, and so large numbers (typically 2^64 and
above) will not be supported.  The single-precision code uses an
algorithm which is designed for factoring smaller numbers.

То есть, имеется в виду, что программа вообще-то может работать и с бОльшими числами, и даже ничего не сказано про максимальную разрядность входных данных. Только как её собрать с использованием «GNU MP»? Вот вопрос.

Кстати,

Код: [Выделить]

p@e4:~$ factor 1111111111111111111
1111111111111111111: 1111111111111111111
p@e4:~$
За 16 секунд на IBM PC XT Asus EEE PC 900.
gcalctool позорно не справился с задачей...

[inkblack]

Короче, даже тот factor, что идёт в стандартной Убунте — тоже полный отстой в сравнении с этим. Со 100-значными числами справляется даже на слабых машинках, 20-значные разлагает мгновенно. 40-значные — за пару секунд.

Вот тут, правда с числом 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 (101 единица) долго возится. Результата пока нет.

А, вот уже есть: число разложено на 3 множителя за 2 часа 41 минуту 26 секунд.

Нашел я это, почитав сатью «Факторизация». Там в конце три ссылки. Я здесь привёл самую крутую.