Комментарии 19
else: pass
выглядит незавершенным
Я так написал, чтобы подчеркнуть комментарий и следование словесному алгоритму - там действий никаких не нужно в else блоке. Можно заменить на # else: pass n isn't prime, choose another n
После выполнения инструкции break мы выйдем с цикла по выбору a и перейдём к циклу по выбору n, поэтому произойдёт ровно то, что описано комментарием.
Одно из решений это
Что такое x? Не вижу этой переменной больше нигде
при действительно простом
мы найдём(можно оценить вероятность от s) такое
Самое интересное - эти вероятности и, в целом, требуемые значения s - как раз и не приведено в статье... Без этого вообще непонятно, сколько этот алгоритм будет работать, и насколько он конкурентоспособен по сравнению с другими алгоритмами.
А о каких других алгоритмах вы говорите? Пример можно?
Вы же сами даёте ссылки на статьи с другими алгоритмами. Но, для определённости, пример - запуск серии тестов Миллера-Рабина (что, например, используется OpenSSL на практике).
Тест Миллера-Рабина вероятностный, который даёт сильное псевдопростое число, а здесь генерируется однозначно простое число.
Вопрос в том, какова стоимость этой гарантии.
Я понял, о чём вы говорите. В принципе, я могу дополнить статью сравнением эффективности по времени работы других алгоритмов по генерации простых/псевдопростых чисел с этим - спасибо за предложение по улучшению.
Но изначальной целью было продемонстрировать сам алгоритм как подход к генерации больших однозначно простых чисел, так как не видел, чтобы он где-то был описан.
Думаю, сравнение с другими алгоритмами по эффективности было бы очень наглядным!
Но всё-таки по-прежнему интересен вопрос с асимптотикой в "плохом" случае (я предполагаю, что говорить о "худшем" случае тут неинтересно, поскольку, видимо, алгоритм сильно завязан на рандоме). Сколько разных a нам может понадобиться для проверки одного (положим, "неудачно" выбранного) r? Или сколько, в среднем, r нам понадобится просмотреть?
Я посмотрел, на существующие криптолибы - по поводу практических оценок эффективности, то сделать это проблематично из-за разных API по генерации простых чисел. Какой-то алгоритм будет генерировать n-e простое, другой - простое c n битами, этот - простое больше n, где-то идут ограничения на кратность 128, 512 бит в размере, где-то и вовсе псевдопростые и т.д.
Поэтому больший смысл имеют асимптотические оценки, но для того, чтобы их сделать, то нужно углубляться в те статьи о корректности алгоритма, которые я упомянул ))
Ссылки с оценками асимптотики у меня нету, но я читал когда-то об этом алгоритме, но уже не помню, где.
Могу добавить статистику времени работы этого алгоритма для генерации простых чисел разного порядка, если это поможет.
В данном случае 
можно считать 
- когда мы рассматриваем конгруэнцию, то 
фиксированные параметры, а 
это переменная вместо 
. Примитивное решение
нас не интересует, так как мы выбирали 
, поэтому я так и записал.
на 
.Если говорить про вероятность того, что для простого 
мы найдём нужное 
, то это 
. 
и 
фиксированные, количество 
, которые нас не удовлетворяют, не больше 
, всего различных 
это 
.
Добавил оценку вероятности в статью.
После перечитывания FIPS 186-4 (секция C.6) и поиска доп. информации по алгоритму Shawe-Taylor получилось выйти на упоминания алгоритма Maurer, который уже очень похож на то, что описано в статье ("Fast Generation of Secure RSA-Moduli with Almost Maximal Diversity", Maurer, 1989):
Lemma 1 suggests a method for constructing large primes. One can form the product F = product q_j^beta_j of some known primes q_j, raised to some powers beta_j, and repeatedly choose an integer R < F at random until n = 2RF + 1 can be proved to be prime by an appropriate choice of the base a. Lemma 3 shows that if n is indeed prime and if all q_j's are large, then virtually every base a can be used for certifying the primality of n. On the other hand, if n is composite but does not contain a small prime factor that allows to detect this by trial division, then virtually every base a will satisfy a^{n-1} \ne 1 (mod n) and hence reveal the compositeness of n, unless n is of a very special form.
Кроме того, там дальше в статье, по-видимому, делаются дополнительные ухищрения, чтобы добиться более равномерной генерации случайных простых.
Поглядев ещё в статьях, нашёл ещё один близкий аналог - "Generating Provable Primes Efficiently on Embedded Devices" (Clavier, 2012). "Ядро" алгоритма там выглядит ещё ближе к вашему алгоритму:
We generate a provable prime by doubling at each iteration the size of the current prime p to derive the new prime n = 2rp + 1.
и псевдокод алгоритма очень похож. Но есть и отличия - например, они стартуют не с решета Эратосфена, а с генерации числа до 2^32 с помощью тестов Миллера-Рабина. У них там много и других интересных соображений - про энтропию, про ускорение подбора случайных параметров путём поиска их в специальной форме, и т. п.
Криптография и генерация больших однозначно простых чисел — критерий Поклингтона