Решена задача, которой более 2000 лет

[AL]

Индийский математик Маниндра Аграваль (Manindra Agrawal) и его студенты Нирадж
Кайяль и Нитин Саксена (Neeraj Kayal и Nitin Saxena) решили проблему, которая
"не давалась" исследователям более чем 2200 лет. Трое математиков индийского
института технологии, расположенного в городе Канпур, разработали метод,
позволяющий безошибочно и быстро определять, является ли то или иное число
простым (то есть, делится ли оно только на единицу и на само себя,
www.cse.iitk.ac.in/primality.pdf ).

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

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

А вот создатели нового метода настроены очень оптимистично: "Наш алгоритм
исключает вероятность любой ошибки". "Мы получили несколько отзывов. Никто не
высказывает сомнений в новом алгоритме, и все выражают удовлетворение
достигнутым результатом", - говорит Маниндра Агравал. Впрочем, сами создатели
признаются, что уже существующие алгоритмы гораздо быстрее, и вряд ли их новый
метод сразу найдет себе применение.

Теперь, когда метод получен, есть два возможных пути. Согласно первому из них,
после того, как результаты расчетов стали доступны математикам всего мира, в
предложенном методе может быть найдена ошибка. Второй же путь - признание
работоспособности метода и начало работы над сокращением числа шагов с
последующим его широким применением.