Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
  Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Вверх: 13. Методы построения больших простых чисел Назад: 13.5 Построение больших простых чисел n с использованием частичного разложения n-1 на множители   Содержание   Предметный указатель


13.6 Полиномиальные алгоритмы доказательства простоты с помощью известного полного разложения на простые множители

В работе Конягина и Померанса [KonP] был предложен ряд алгоритмов, позволяющих детерминированно доказывать, что $ n$ -- простое или составное число, с полиномиальной сложностью, если известно полное или частичное разложение $ n-1$ на простые множители.

Справедлива, например, следующая теорема.

Теорема 7.  Если известно полное разложение $ n-1$ на простые множители, то имеется алгоритм, который доказывает, что $ n$ -- простое или составное число, за $ O\left((\log
n)^{17/7}/\log\log n\right)$ арифметических операций.

Подобные алгоритмы были известны и ранее, но константа в показателе в оценке сложности была хуже.

Практическое применение этих алгоритмов при построении больших простых чисел может быть таким. Допустим, что мы выбрали $ n$ с известным разложением $ n-1$ на простые множители; кроме того, оказалось, что $ n$ вероятно простое (по методу Миллера -- Рабина из раздела 13.2), но нам не удается доказать простоту $ n$ методом Миллера. Тогда можно применить один из алгоритмов Конягина -- Померанса для доказательства простоты $ n$.


Вперед Вверх Назад Содержание Предметный указатель
Вперед: 13.7 Анализ алгоритма построения больших простых чисел, изложенного в Стандарте (ГОСТ Р 34.10-94) "Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма" Вверх: 13. Методы построения больших простых чисел Назад: 13.5 Построение больших простых чисел n с использованием частичного разложения n-1 на множители   Содержание   Предметный указатель


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

TopList Rambler's Top100