NP-полные задачи и криптография

[Esp_]

nikvic в сообщении #718179 писал(а):

Если не ошибаюсь, для проверки числа на простоту есть полиномиальный алгоритм

Где он?

[Sonic86]

Esp_ в сообщении #718397 писал(а):

nikvic писал(а):

Если не ошибаюсь, для проверки числа на простоту есть полиномиальный алгоритм

Где он?

(Оффтоп)

ну Вы даете!

Agrawal-Kaial-Saxena primarility test.
http://en.wikipedia.org/wiki/AKS_primality_test
http://mathworld.wolfram.com/AKSPrimalityTest.html
Василенко Теоретико-числовые алгоритмы в криптографии (хотя там только ссылки)
http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D1%8B (статья длиннее, чем в английской версии, хе)