Факторизация QS

[mathpath]

Факторизация методом квадратичного решета (Quadratic sieve algorithm, сокр. QS) - метод факторизации больших чисел,
разработанный в начале 80-х годов.
До сих пор является самым быстрым для целых чисел до 100 десятичных цифр и устроен значительно проще,
чем общий метод решета числового поля (gnfs).
Это универсальный алгоритм факторизации, так как время его выполнения исключительно зависит от размера факторизуемого числа,
а не от его особой структуры и свойств.

Я хочу предложить этот алгоритм для обсуждения также в связи с тем, что на гитхабе есть реализация этого алгоритма, написанная на питоне.
https://github.com/Ganapati/RsaCtfTool
Там можно найти также реализацию других алгоритмов факторизации.

Статья на википедии про сам алгоритм qs:
https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 1%82%D0%B0

Данная реализация qs, которая лежит в файле _mpqs.py, к примеру факторизует седмое число ферма за 5 секунд.

[Pphantom]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
А что, собственно, предлагается обсуждать? Пока это просто информация о методе и его реализации, которую вроде бы никто не просил.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.