Rambler's Top100 Service
Поиск   
 
Обратите внимание!   Обратите внимание!
 
  Наука >> Математика >> Алгебра, математическая логика и теория чисел | Новости
 Написать комментарий  Добавить новое сообщение
 См. также

Популярные статьиОтветы на все вопросы

Nitin Saxena and Neeraj Kayal with Prof. Manindra Agarwal (left to right). Photo Indian Institute of Technology, Kanpur, Department of Computer Science and Engineering О полиномиальном тесте на простоту
19.08.2002 20:27 | Cryptography.Ru
    

Лето, пора отпусков и каникул. Традиционно август является, в научном плане, самым "тихим" месяцем в году. Но нынешний август - исключение. Математическая общественность была взбудоражена дней 10 тому назад, когда по миру стали распространяться слухи о том, что где-то в Индии получен новый сенсационный результат в алгоритмической теории чисел. Изначально говорилось даже, что якобы предложен эффективный алгоритм факторизации целых чисел.

На самом деле речь идёт о другой задаче - проверке целых чисел на простоту. Сам результат официально ещё не опубликован, так что доступная на данный момент статья (Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMES is in P.) по-видимому должна рассматриваться как предварительный вариант. (Ссылка на статью - pdf, 213 кб, 9 страниц.)

Здесь следует сразу же оговориться, что задачи, известные еще с античных времён и остающиеся нерешёнными по сей день, всегда привлекали и привлекают внимание весьма специфической публики типа ферматистов. Но мы имеем дело заведомо не с тем случаем: цитированная выше статья написана математиками.

Результат таков: предложен полиномиальный детерминированный алгоритм проверки целых чисел на простоту. Его асимптотическая сложность есть O~((log n)12), где n - проверяемое целое число, а O~(n) - сокращённое обозначение для O(t(n)poly(log(t(n))). Тем самым положительно решён остававшийся до сих пор открытым вопрос о принадлежности задачи распознавания простоты классу P. Высокий показатель степени (12) - это верхняя граница, которую удалось доказать авторам. Представляется, что реальная трудоёмкость алгоритма должна быть ниже.

Мы надеемся, что в ближайшем будущем на нашем сайте появится более обстоятельный комментарий к данной работе, написанный специалистами по теории чисел. На данный момент мы не можем утверждать или отрицать истинность этого результата.

Всюду ниже мы считаем, что результат верный. Как его можно оценить? Безусловно, это выдающееся достижение. Результат замечателен как сам по себе, так и той простой и изящной идеей, которая положена в его основу. Отметим, что газета New York Times в номере от 8 августа поместила специальную заметку, посвященную достижению индийских математиков.

И в заключение, разумеется, несколько слов о значении данного результата для криптографии.

С одной стороны, всякое продвижение в области разработки эффективных тестов простоты является хорошей новостью для криптографии. На данный момент трудно себе представить, чтобы алгоритмы проверки чисел на простоту можно было использовать в криптоанализе. В то же время, генерация ключей для криптосистем с открытым ключом, схем электронной подписи и т. п. включает в себя генерацию больших псевдослучайных простых чисел. Поэтому всякий новый эффективный тест простоты может сказаться лишь положительно на надежности и эффективности алгоритмов генерации ключей.

С другой стороны, данный алгоритм большого практического значения не имеет. Известные ранее рандомизированные алгоритмы проверки простоты весьма эффективны, а вероятность ошибки при их применении может считаться пренебрежимо малой для любых приложений.

Отметим также, что предложенный Миллером более четверти века назад алгоритм проверки простоты также является детерминированным. Более того, при расширенной гипотезе Римана этот алгоритм полиномиален. Более подробно о тестах простоты см. в статье Ю. В. Нестеренко (раздел 4 главы 4) в книге "Введение в криптографию".

Фото: Indian Institute of Technology, Kanpur, Department of Computer Science and Engineering


Написать комментарий
 Copyright © 2000-2015, РОО "Мир Науки и Культуры". ISSN 1684-9876 Rambler's Top100 Яндекс цитирования