Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem.
Здравствуйте, Alexander Shargin, Вы писали:
AS>Вот, попалось на глаза такое сообщение.
AS>Turns out, Primes are in P
AS>Manindra Agrawal et. al. of the Indian Institute of Technology Kanpur CS department have released a most interesting paper today. It presents an algorithm that determines whether a number is prime or not in polynomial time. While I haven't gone through the presentation in detail, it looks like a promising, albeit non-optimized, solution for the famous PRIMES in P problem.
AS>http://www.cse.iitk.ac.in/primality.pdf
Прикольно, но с теоретической точки зрения, поскольку сложность у него O(log^12-16(не помню точно)(N)). Вероятностные алгоритмы для практики лучше.
P.S. У него еще очень громоздское доказательство корректности и оценка сложности, а мне это на экзамене сдавать придется
Здравствуйте, IO, Вы писали:
IO>Здравствуйте, Alexander Shargin, Вы писали:
IO>А что такое полиномиальное время?
Это означает, что требуемое время оценивается полиномом от входных данных.
Если интересно, то попробуй поискать инфу по ключевым словам
"алгоритмическая сложность", "сложность алгоритмов"
Тема очень интересная, но очень непростая...
Re[3]: Простые числа за полиномиальное время
От:
Аноним
Дата:
24.11.02 12:36
Оценка:
Здравствуйте, bkat, Вы писали:
IO>>А что такое полиномиальное время?
B>Это означает, что требуемое время оценивается полиномом от входных данных.
Маленькое добавление:
длина входных данных в данной задаче по определению = число цифр в (десятичной) записи числа.
DOO>P.S. У него еще очень громоздское доказательство корректности и оценка сложности, а мне это на экзамене сдавать придется
Бог с Вами! Возможно, конечно, теория эллиптических кривых Вам ближе...
но все же. Во-первых это первый детеминироваынный полиномиальный алгоритм,
а во-вторых доказательство его корректности не выходит за пределы
2 курса мехмата. Да и вообще основная идея -- использование эндоморфизма
Фробениуса -- достаточно прозрачна. Т.е. n -- простое iff отображение
p \mapsto p^n -- энфоморфизм. Дальше остается проблема
проверки того, что полином большой степени тождественно нулевой.
Этот вопрос мы сведем к полиномам маленькой степени, беря факторы
по полиномам вида x^r — 1. Одна проблема -- фактор кольца по такому полиному
не является полем, поэтому работать с ним не очень удобно. Ну есть некоторые трудности, конечно
Если же посмотреть на то, что предлагалось раньше
(работы Ленстры, Померанца, Киллиана, Голдвассер и прочих заслуженных
товарищей), то это просто развлечение.
E>Сейчас куча народа над алгоритмом работает, реально время порядка 6й, а не 12й степени.. Однако Миллер-Рабин все же круче.
Т.е. доказана гипотеза о распределении чисел Софи Жермен?
Или найдено другое простое объяснение лучшей оценки времени?
Хотя в любом случае лучшая оценка по модулю недоказанной теоремы
это лучше, чем корректность по модулю ERH (как в детерминированном
варианте Миллера-Рабина)
Помнится, когда-то меня сильно удивило, что Primes \in NP \cap co-NP
(в одну сторону -- очевидно, в другую -- теорема Пратта, кажется)
А теперь, оказывается, Primes \in P и вообще все тривиально.
