Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.2.1 Алгоритм Шермана - Лемана Вверх: 12. Задача факторизации больших целых чисел Назад: 12.1 Введение   Содержание   Предметный указатель


12.2 Факторизация чисел с экспоненциальной сложностью

Пусть дано натуральное число $ n$, $ n>1$. Простейший алгоритм разложения $ n$ на простые множители имеет следующий вид. Будем последовательно проверять делимость $ n$ на $ i=2,3,\ldots,\left[\sqrt{n\vphantom{n_1}}\right]$. Если делители не найдены, то $ n$ -- простое число. Если же $ k$ -- первый найденный делитель числа $ n$, то $ k$ есть наименьший простой делитель числа $ n$. В этом случае полагаем $ n_1=n/k$ и повторяем вышеописанный процесс для $ n_1$, начиная не с $ 2$, а с найденного $ k$, т. е. последовательно проверяем делимость $ n_1$ на $ i=k,k+1,\ldots,\left[\sqrt{n_1}\right]$. Полное разложение $ n$ на простые множители будет найдено за $ O\left(\sqrt n\log n\right)$ арифметических операций.

В книге [Кнут] описано несколько подобных алгоритмов со сложностью $ O\left(n^{1/2+\varepsilon}\right)$. Например, метод Олвея для нечетного $ n$ и нечетного $ d\geqslant 2n^{1/3}+1$ находит наименьший нечетный делитель $ f$ числа $ n$ такой, что $ d<f\leqslant n^{1/2}$, либо доказывает, что такого $ f$ не существует. Преимущество метода в том, что поиск делителей происходит без использования операции деления; на каждом шаге алгоритма делается лишь несколько сложений и вычитаний. Там же описан метод Ферма, который по заданному $ n$ (также без деления) находит наибольший множитель $ n$, не превосходящий $ \sqrt n$.

Теперь рассмотрим алгоритмы факторизации со сложностью $ O(n^\alpha)$, $ \alpha<1/2$. Многие из них подробно описаны в [Kob], [Voor]. Мы приводим только процедуры нахождения нетривиального делителя числа $ n$ (о нахождении разложения на простые множители см. введение).


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.2.1 Алгоритм Шермана - Лемана Вверх: 12. Задача факторизации больших целых чисел Назад: 12.1 Введение   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100