Используйте алгоритм Ленстры EC, если он не полупростой. В противном случае используйте NFS Pomerance. Хорошие представления существуют для обеих этих "коробок". Моя ставка - просматривать домашние страницы Lenstra и Pomerance, они оба действительно хороши в экспозиции. Или посмотрите " Теория чисел: Руководство для программистов ", автор Mark Herkommer . Это именно то, что вам нужно, ничего более и очень ясно.
РЕДАКТИРОВАТЬ: хотя 1000-битный модуль может быть немного растянутым, если у вас есть обычное оборудование.
РЕДАКТИРОВАТЬ: Конечно, некоторые дополнительные ссылки: http://tinyurl.com/herkAmzon для книги Herkommer.
Статья 1987 года о факторизации ЕС с домашней страницы Хендрика Ленстры: Факторизация целых чисел с эллиптическими кривыми, Ann. математики 126, 649-673. .
Из обширной сети: Очень простой исходный код Python для вышеуказанного алгоритма (который я не корректировал)
Домашняя страница Карла Померанса и соответствующий документ на сите Числового поля: здесь
Однако, вы также можете найти этот рассказ о развитии сита , или этот рассказ о квадратичной версии также со страницы Pomerance.
Посетите этот сайт, посвященный реализации GNFS , но я настоятельно рекомендую найти копию книги Herkommer, которая содержит простой и понятный исходный код на нескольких страницах.
РЕДАКТИРОВАТЬ: Также рассмотрите возможность использования факторинга в облаке Elastic Compute. Я слышал, что парень делает это за одну ночь за 75 долларов, согласно этой статье WiRED