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

12.3.3 Алгоритм Бриллхарта -- Моррисона

Этот алгоритм впервые описан в работе [BrMor]. Современную версию с использованием параллельных вычислений см. в [WW]. Алгоритм Бриллхарта -- Моррисона работает так же, как алгоритм Диксона, только вместо случайных $ m$ используются некоторые числа, вычисляемые с помощью разложения $ \sqrt
n$ в непрерывную дробь. Кроме того, в факторную базу включаются только те простые числа $ p$, для которых $ n$ является квадратичным вычетом по модулю $ p$.

К алгоритму Бриллхарта -- Моррисона применимы методы ускорения, описанные в п. 12.3.2. В работе [Pom82] приведены оценки сложности алгоритма Бриллхарта -- Моррисона (в том числе с методами ускорения), получаемые с помощью некоторых эвристических допущений.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 12.3.4 Метод квадратичного решета Вверх: 12.3 Факторизация чисел с субэкспоненциальной сложностью Назад: 12.3.2 Методы ускорения алгоритма Диксона   Содержание   Предметный указатель


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