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


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

В этом разделе мы описываем методы факторизации $ n$ за $ O(L^{\alpha+o(1)})$ арифметических операций, где $ \alpha $ -- некоторая константа, а $ L=L(n)=e^{\sqrt{\ln n\,\ln\ln
n}}$. Далее мы будем писать $ L^\alpha$, подразумевая $ L^{\alpha+o(1)}$.

Перейдем к описанию алгоритмов. Далее мы будем предполагать, что:     1) $ n$ составное; это легко обнаружить с помощью тестов на псевдопростоту типа теста Соловея -- Штрассена (об этих тестах см. обзор [Вас]);

    2) $ n$ не делится на простые числа $ p$, не превосходящие $ L$; это легко проверить пробными делениями за $ O(L)$ шагов.




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


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

TopList Rambler's Top100