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


Этот материал доступен в сети по адресу:
http://www.mmonline.ru/message/1921/


28.11.02 14:26  Очередное Заседание Московского Математического Общества - 3 декабря

Заседание Московского Математического Общества 3 декабря 2002 г.
(начало в 18 час. 10 мин., ауд.16-24 Главного здания МГУ)

Ю.В.Нестеренко.
Как отличить простое число от составного.

Двести лет назад К.Ф.Гаусс писал: "задача о том, как отличать составные числа от простых и разлагать первые на их простые сомножители принадлежит к важнейшим задачам всей арифметики". В последние два десятилетия, благодаря в первую очередь запросам криптографии и широкому распространению ЭВМ, исследования этих задач переживают весьма бурный и плодотворный период. Наиболее быстрые в настоящее время алгоритмы проверки чисел на простоту используют вычисления в круговых полях или на эллиптических кривых и эффективны на практике. Тем не менее в течение длительного времени стояла открытой теоретическая проблема: доказать, что задача проверки на простоту имеет полиномиальную сложность. Эту проблему решили летом текущего 2002 года индийские математики M.Agrawal, N.Kayal, N.Saxena. Они нашли новый алгоритм, который требует $O(ln^{12} N)$ арифметических операций для ответа на вопрос, является заданное число $N$ простым или составным. Сам по сабе алгоритм элементарен, но доказательство его работоспособности, а также оценка сложности основаны на очень глубоких результатах аналитической теории чисел (E.Fouvry, 1985г.)

В докладе, который не потребует никаких специальных знаний, будет рассказано об этом замечательном достижении.


Московское Математическое Общество


Copyright © 2000−2021 MMOnline.Ru | http://www.mmonline.ru/