Путь: Математика » Теория чисел » Факторизация

Разложение на множители Простое деление Метод сложности O( n1/2 ), используемый для обнаружения и удаления малых делителей. Методы Монте-Карло Сложность в худшем случае O( n1/4 ) Успех зависит от везения. P-1 метод Полларда Довольно хитрый алгоритм, успех которого зависит от свойств числа p-1, а не от величины простых делителей числа.   Дополнительные материалы: A Survey of Modern Integer Factorization Methods z i p Описание современных методов разложения на множители. Все дано очень доступно и понятно. Применение алгоритмов проиллюстрировано на конкретных примерах. Block Lanczos Algorithm for Finding Dependencies over GF(2) z i p В наиболее эффективных алгоритмах факторизации требуется найти часть решений большой разреженной матрицы с элементами 0 или 1. Именно такой алгоритм и описан в тексте. Factoring Integers with Self-Initializing Quadratic Sieve z i p Глубокое описание одного из мощнейших алгоритмов факторизации - SIQS, и того, как в нем применяется. Solving Large Sparse Linear Systems Over Finite Fields z i p Решение больших разреженных систем линейных уравнений над конечными полями путем комбинации нескольких известных методов. A FFT Extension of the Elliptic Curve Method of Factorization z i p Описано применение в ECM алгоритме разложения на множители быстрого умножения через FFT. The Number of Relations in the Quadratic Sieve Algorithm z i p Выбор параметров в алгоритме факторизации MPQS. Carl Pomerance: A Tale fo Two Sieves z i p Статья, на достаточно любительском уровне рассказывающая о методах 'решета', и истории их появления. Random Combinatorial Structures and Prime Factorizations z i p Рассмотрена связь комбинаторных процессов и разложения на множители.