:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Теория чисел » Факторизация
  Разложение на множители




Простое деление
Метод сложности 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
Рассмотрена связь комбинаторных процессов и разложения на множители.