Факторизация: ро-метод или метод квадратичного решета

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Хыиуду
Сообщения: 2388
Зарегистрирован: Вс мар 06, 2005 9:03 pm
Откуда: Москва
Контактная информация:

Факторизация: ро-метод или метод квадратичного решета

Сообщение Хыиуду » Вс апр 09, 2006 11:16 am

Суть задачи: есть большое число N, которое суть произведение простых чисел P и Q. Зная число N, надо найти P и Q, т.е., проще говоря, разложить N на простые множители. Если кто-нибудь может написать здесь или дать ссылку на такие методы решения этой задачи, как ро-метод и квадратичное решето - буду признателен. В поисковиках чаще всего выдаются оглавления книг с этими методами, а покупать книгу не хотца...
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.

Alex_soldier
Сообщения: 1
Зарегистрирован: Ср ноя 08, 2006 4:29 pm
Откуда: Москва
Контактная информация:

Сообщение Alex_soldier » Ср ноя 08, 2006 4:34 pm

Попробуйте посмотреть здесь:
http://ru.wikipedia.org/wiki/Факторизация
Идеи двигают Мир!

Andrey1302
Сообщения: 3
Зарегистрирован: Пн мар 26, 2018 1:17 am

Re: Факторизация: ро-метод или метод квадратичного решета

Сообщение Andrey1302 » Пн мар 26, 2018 1:20 am

В пакете GMP в папке demos есть прога factorize.c, которая использует длинную арифметику. Можешь ее сам улучшить или сразу использовать.

Ответить