Генерация простого числа заданного размера?

Конечно, AKS вообще полиномиальный по сложности в отличие от других детерминированных алгоритмов проверки на простоту. Но это теория. Насколько мне известно с практической точки зрения он никуда не годится, т. к. там константы гигантские. То есть он будет выигрывать ну на ооочень больших числах, которые пока не используются на практике.