спасибо, нашёл:

mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=2002&option_lang=rus
Указан многочлен с целыми коэффициентами от 10 переменных, множество всех неотрицательных значений которого (при положительных целых значениях переменных) есть в точности множество всех простых чисел.

Какое-то шаманство, как так может быть.

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

Вот тут написано: nsu.ru/phorum/read.php?f=29&t=2644&a=1
Помимо этого замечательного факта, я слышал, что тем не менее неизвестно никаких конкретных значений переменных, на которых многочлен принимает хоть какое-то неотрицательное значение (а, значит, и простое). То есть теоретически доказано, что такие значения существуют для каждого простого числа, но неизвестно ни одного конкретного примера.

То есть практически этот полином неприменим?

То есть практически этот полином неприменим?
Вы оригинальную статью читали?
"Укажем, что степень многочлена (123) равна 15905."

> государства дебилы, конечно, но подобный дебилизм вообразить невозможно

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