MMOnline – Информационный портал о мехмате МГУ

Математики Индийского института технологии в городе Канпуре утверждают, что им удалось решить задачу, которой 2200 лет.

Маниндра Аграваль, Нирадж Кайяль и Нитин Саксена в понедельник представляют на рассмотрение свой метод определения того, является ли данное число простым, то есть, делится ли оно только на единицу и на самое себя.

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

Однако до сих пор не существует точного метода определения простоты любого числа за конечное число шагов.

В 200 году до новой эры греческий математик Эратосфен, первый определивший простые числа, предложил и метод их определения, который и по сей день изучается в средней школе. Этот метод, известный как "Решето Эратосфена", прост, понятен, дает точный ответ на вопрос, но крайне долог.

Для определения простоты числа, мы выписываем все числа от 0 до самого числа и затем вычеркиваем каждое второе число после 2 (то есть, все числа, делящиеся на два), потом - каждое третье после 3 (то есть, делящиеся на три) и так далее, пока не дойдем до середины ряда. Оставшиеся невычеркнутыми числа - простые.

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

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

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

Индийские математики говорят, что их метод - конечный и дает не вероятностный, а детерминистический ответ, является ли число простым.

Впрочем, сами они признаются, что нынешние алгоритмы гораздо быстрее, и вряд ли новый метод сразу найдет себе применение.

Однако, по словам руководителя группы, теперь, когда метод получен, математики могут начать искать способы сокращения числа шагов.

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

BBC