Форум русскоязычного сообщества Ubuntu


Следите за новостями русскоязычного сообщества Ubuntu в Twitter-ленте @ubuntu_ru_loco

Автор Тема: программа для факторизации числа  (Прочитано 2271 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн eBoris

  • Автор темы
  • Новичок
  • *
  • Сообщений: 20
    • Просмотр профиля
программа для факторизации числа
« : 28 Февраля 2011, 11:33:17 »
Добрый день!

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

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

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

Оффлайн inkblack

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #1 : 28 Февраля 2011, 11:49:09 »
В Ubuntu 10.10 такая фича есть в калькуляторе.

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

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



Да, в той статье идет речь про 100-значные числа, калькулятор в пролёте...
« Последнее редактирование: 28 Февраля 2011, 11:53:40 от inkblack »
Делюсь знаниями, но их у меня мало!

Оффлайн eBoris

  • Автор темы
  • Новичок
  • *
  • Сообщений: 20
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #2 : 28 Февраля 2011, 12:01:12 »
Да, в той статье идет речь про 100-значные числа, калькулятор в пролёте...
У меня число всего лишь 128 битное, а это примерно 40 символов, поэтому простым перебором совсем не хочется, хотя за несколько дней и получилось бы.
С другой стороны, задача встала разовая, поэтому совсем не хочется погружаться в алгоритмы и т.п.

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

Оффлайн inkblack

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #3 : 28 Февраля 2011, 12:06:40 »
Ну, попробуйте калькулятором, хотя вряд ли он справится. 40 цифр — много. Но вдруг _повезёт_??
Делюсь знаниями, но их у меня мало!

Оффлайн eBoris

  • Автор темы
  • Новичок
  • *
  • Сообщений: 20
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #4 : 28 Февраля 2011, 12:57:40 »
наставил разных библиотек с похожими названиями - приложения из статьи скомпилировались

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

Оффлайн Tarasov

  • Участник
  • *
  • Сообщений: 150
  • debian lenny
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #5 : 28 Февраля 2011, 15:46:40 »
можно самому прогу написать
NVIDIA user

Оффлайн Ankor

  • Активист
  • *
  • Сообщений: 324
  • Ubuntu 7.10
    • Просмотр профиля
    • Подкасты AnotherAnkor
Re: программа для факторизации числа
« Ответ #6 : 28 Февраля 2011, 16:59:08 »
Я не догоняю: нужно найти факториал или что? Вроде как это проще написать самому, чем искать в сети. Ищут либо от лени, либо от того, что проект действительно обладает определённой сложностью.
Много лет работаю админом и пишу код.

Оффлайн Jack Sparrow

  • Активист
  • *
  • Сообщений: 641
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #7 : 28 Февраля 2011, 17:24:19 »
man factor
factor число
Нейросети тебя не заменят. Тебя заменит человек, который умеет ими пользоваться.

Оффлайн eBoris

  • Автор темы
  • Новичок
  • *
  • Сообщений: 20
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #8 : 28 Февраля 2011, 17:53:45 »
man factor
factor число

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

Пользователь решил продолжить мысль 28 Февраля 2011, 17:55:38:
Я не догоняю: нужно найти факториал или что? Вроде как это проще написать самому, чем искать в сети. Ищут либо от лени, либо от того, что проект действительно обладает определённой сложностью.
надо разложить большое число на простые множители; простой перебор работает медленно, поэтому придуманы различные хитрые алгоритмы, которые позволяют этот перебор ускорить
« Последнее редактирование: 28 Февраля 2011, 17:55:38 от eBoris »

Оффлайн inkblack

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #9 : 28 Февраля 2011, 20:53:55 »
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

  • Старожил
  • *
  • Сообщений: 1216
    • Просмотр профиля
Re: программа для факторизации числа
« Ответ #10 : 13 Марта 2011, 17:30:18 »
Короче, даже тот factor, что идёт в стандартной Убунте — тоже полный отстой в сравнении с этим. Со 100-значными числами справляется даже на слабых машинках, 20-значные разлагает мгновенно. 40-значные — за пару секунд.

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

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

Нашел я это, почитав сатью «Факторизация». Там в конце три ссылки. Я здесь привёл самую крутую.
« Последнее редактирование: 13 Марта 2011, 19:26:48 от inkblack »
Делюсь знаниями, но их у меня мало!

 

Страница сгенерирована за 0.061 секунд. Запросов: 23.