Индийским математикам удалось решить вековую проблему — они нашли метод, быстродоказывающий, что число является простым — а это решающий шаг в развитии криптографии.
Популярный алгоритм шифрования RSA, применяемый в интернет-коммерции, строитсяна предположении, что когда простые числа — те, чт
делятся без остатка толькона себя и на единицу — достаточно велики, их почти невозможно подобрать. Длясоздания ключей шифрования RSA использует два длинных простых числа и с их помощьюполучает еще большеее простое число. Затем производится проверка, доказывающая,что оно действительно простое. Современные алгоритмы, применяемые в таких тестахпростых чисел, работают достаточно быстро, но допускают небольшую вероятностьошибки.
Новый алгоритм, разработанный в Индийском технологическом институте в КанпуреМаниндрой Агравалом (Manindra Agrawal) и его студентами (Neeraj Kayal и NitinSaxena), как утверждается, генерирует абсолютно точные результаты. “Самый большойнедостаток современного криптографического ПО — невозможность на 100% гарантировать,что число является простым, — комментирует профессор вычислительной техники Университеташтата Нью-Джерси Эрик Аллендер (Eric Allender). — Этот новый алгоритм решаетфундаментальную проблему, стоящую уже несколько веков, над которой ученые интенсивноработали последние десятилетия”. Работа Агравала, посвященная этому вопросу,еще не опубликована, но оригинальный способ, которым решена задача, сформулированнаяеще математиками древнего Китая и Греции, уже вызвала переполох среди специалистов.Ряд светил математики и вычислительной техники изучает этот труд. “Подготовительнаяработа была достаточно сложной, но в результате получился блестящий, очень красивыйи элегантный алгоритм”, — говорит Аллендер.
Правда, авторы признают, что до практического применения их открытия еще далеко.”Наш метод медленнее, чем самые быстрые из известных алгоритмов тестированияпростых чисел, — сказал Агравал. — Его преимущество в том, что он полностью детерминистический,в отличие от его предшествующих, которые могут приводить к ошибкам, хотя и редко”.
Специалисты отмечают, что во многих случаях люди предпочитают мириться с такимималовероятными ошибками. Однако растущая важность шифрования для таких сфер деятельности,как банковское обслуживание и защищенная связь, вызывает все большую потребностьв повышении надежности криптозащиты. “Самое важное в этом (алгоритме) — теоретическийрезультат, и это только первый шаг, — говорит Аллендер. — За ним последуют уточненияи усовершенствования с целью практического применения метода”.