Математика: Теория чисел: Разложение на множители.

Очевидно, эта задача всегда разрешима. Основная проблема - сделать это как можно быстрей.

Простое деление

Метод сложности O( n^1/2 ), используемый для обнаружения и удаления малых делителей.

Методы Монте-Карло

Сложность в худшем случае O( n^1/4 ). Успех зависит от везения.

P-1 метод Полларда

Довольно хитрый алгоритм, успех которого зависит от свойств числа p-1, а не от величины простых делителей числа.

Архив статей.

A Survey of Modern Integer Factorization Methods

Описание современных методов разложения на множители. Все дано очень доступно и понятно. Применение алгоритмов проиллюстрировано на конкретных примерах.

Block Lanczos Algorithm for Finding Dependencies over GF(2)

В наиболее эффективных алгоритмах факторизации требуется найти часть решений большой разреженной матрицы с элементами 0 или 1. Именно такой алгоритм и описан в тексте.

Factoring Integers with Self-Initializing Quadratic Sieve

Глубокое описание одного из мощнейших алгоритмов факторизации - SIQS, и того, как в нем применяется.

Solving Large Sparse Linear Systems Over Finite Fields

Решение больших разреженных систем линейных уравнений над конечными полями путем комбинации нескольких известных методов.

A FFT Extension of the Elliptic Curve Method of Factorization

Описано применение в ECM алгоритме разложения на множители быстрого умножения через FFT.

The Number of Relations in the Quadratic Sieve Algorithm

Выбор параметров в алгоритме факторизации MPQS.

Carl Pomerance: A Tale fo Two Sieves

Статья, на достаточно любительском уровне рассказывающая о методах 'решета', и истории их появления.

Random Combinatorial Structures and Prime Factorizations

Рассмотрена связь комбинаторных процессов и разложения на множители.

Вверх по странице, к оглавлению и навигации