![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaКажется, горячие индийские парни придумали полиномиальный алгоритм проверки числа на простоту. (ссылка на дискуссию в Слешдоте).
До сих пор был известен только полиномиально-вероятностный алгоритм проверки числа на простоту -- если он говорил, что число простое, то ошибался с некоторой вероятностью. Но его можно было повторять неограниченное кол-во раз, снижая эту вероятность ошибки до сколь угодно малого значения. Таким образом, с практической точки зрения уже существовал полиноминальный алгоритм проверки, и им сплошь и рядом пользуются. Но с теоретической точки зрения, это довольно интересное достижение. Многие думали, что это просто неверно, что существует такой алгоритм.
Забавно то, что, кажется, этот новый алгоритм использует очень простую арифметику, ничего продвинутого.![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
french_man, если тебе это интересно, посмотри и расскажи свои впечатления. У меня сейчас совсем нет возможности заниматься внимательным вчитыванием и проверкой, увы.
Примечание: "полиномиальный" алгоритм здесь означает "полиномиальный от размера данных". Т.е. полиномиальная проверка того, является ли простым число N, должна занимать время, ограниченное полиномиалом от log(N) -- размера двоичного представления N. Предлагаемый в этой статье алгоритм работает за время O(log(N)12).
Не стоит путать этот алгоритм с алгоритмом разложения числа на множители - такого полиномиального алгоритма пока ещё никто не придумал, и скорее всего его не существует, хотя и этого не могут доказать. Открытие такого алгоритма было бы катастрофическим для немалой части современной криптографии.
До сих пор был известен только полиномиально-вероятностный алгоритм проверки числа на простоту -- если он говорил, что число простое, то ошибался с некоторой вероятностью. Но его можно было повторять неограниченное кол-во раз, снижая эту вероятность ошибки до сколь угодно малого значения. Таким образом, с практической точки зрения уже существовал полиноминальный алгоритм проверки, и им сплошь и рядом пользуются. Но с теоретической точки зрения, это довольно интересное достижение. Многие думали, что это просто неверно, что существует такой алгоритм.
Забавно то, что, кажется, этот новый алгоритм использует очень простую арифметику, ничего продвинутого.
french_man, если тебе это интересно, посмотри и расскажи свои впечатления. У меня сейчас совсем нет возможности заниматься внимательным вчитыванием и проверкой, увы.Примечание: "полиномиальный" алгоритм здесь означает "полиномиальный от размера данных". Т.е. полиномиальная проверка того, является ли простым число N, должна занимать время, ограниченное полиномиалом от log(N) -- размера двоичного представления N. Предлагаемый в этой статье алгоритм работает за время O(log(N)12).
Не стоит путать этот алгоритм с алгоритмом разложения числа на множители - такого полиномиального алгоритма пока ещё никто не придумал, и скорее всего его не существует, хотя и этого не могут доказать. Открытие такого алгоритма было бы катастрофическим для немалой части современной криптографии.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re: математика
Date: 2002-08-15 03:33 pm (UTC)Если алгоритм индусов говорит, что число простое - оно действительно простое. В этом состоит отличие этого алгоритма от популярного алгоритма Рабина-Миллера, который утверждал это лишь с определенной вероятностью. Вероятность можно было довести как угодно близно до единицы, но время работы алгоритма при этом увеличивалось. В алгоритме индусов нет никаких вероятностей.
На пальцах объяснять я не берусь. Может, кто-то еще попробует.
Re: математика
Date: 2002-08-15 03:38 pm (UTC)Re: математика
Date: 2002-08-15 03:39 pm (UTC)Re: математика
Date: 2002-08-15 03:46 pm (UTC)И еще...вот эти индусы..они что - просто написали всем письма с решением и параллельно выложили свое решение на сайте и тем самым защитили себя?А вдруг кто0-то скажет что раньше сделал?НЕужели так просто они пошли на риск?Вот какой поток вопросов.