Я посмотрел, на существующие криптолибы - по поводу практических оценок эффективности, то сделать это проблематично из-за разных API по генерации простых чисел. Какой-то алгоритм будет генерировать n-e простое, другой - простое c n битами, этот - простое больше n, где-то идут ограничения на кратность 128, 512 бит в размере, где-то и вовсе псевдопростые и т.д.
Поэтому больший смысл имеют асимптотические оценки, но для того, чтобы их сделать, то нужно углубляться в те статьи о корректности алгоритма, которые я упомянул )) Ссылки с оценками асимптотики у меня нету, но я читал когда-то об этом алгоритме, но уже не помню, где.
Могу добавить статистику времени работы этого алгоритма для генерации простых чисел разного порядка, если это поможет.
Если говорить про вероятность того, что для простого мы найдём нужное , то это . и фиксированные, количество , которые нас не удовлетворяют, не больше , всего различных это .
Я понял, о чём вы говорите. В принципе, я могу дополнить статью сравнением эффективности по времени работы других алгоритмов по генерации простых/псевдопростых чисел с этим - спасибо за предложение по улучшению.
Но изначальной целью было продемонстрировать сам алгоритм как подход к генерации больших однозначно простых чисел, так как не видел, чтобы он где-то был описан.
В данном случае можно считать - когда мы рассматриваем конгруэнцию, то фиксированные параметры, а это переменная вместо . Примитивное решениенас не интересует, так как мы выбирали , поэтому я так и записал.
Я так написал, чтобы подчеркнуть комментарий и следование словесному алгоритму - там действий никаких не нужно в else блоке. Можно заменить на # else: pass n isn't prime, choose another n
После выполнения инструкции break мы выйдем с цикла по выбору a и перейдём к циклу по выбору n, поэтому произойдёт ровно то, что описано комментарием.
Спасибо за ответ - действительно дополняет статью.
Почему они будут не совсем случайными? Как вы это оценили?
Я посмотрел, на существующие криптолибы - по поводу практических оценок эффективности, то сделать это проблематично из-за разных API по генерации простых чисел. Какой-то алгоритм будет генерировать n-e простое, другой - простое c n битами, этот - простое больше n, где-то идут ограничения на кратность 128, 512 бит в размере, где-то и вовсе псевдопростые и т.д.
Поэтому больший смысл имеют асимптотические оценки, но для того, чтобы их сделать, то нужно углубляться в те статьи о корректности алгоритма, которые я упомянул ))
Ссылки с оценками асимптотики у меня нету, но я читал когда-то об этом алгоритме, но уже не помню, где.
Могу добавить статистику времени работы этого алгоритма для генерации простых чисел разного порядка, если это поможет.
Если говорить про вероятность того, что для простого
мы найдём нужное 
, то это 
. 
и 
фиксированные, количество 
, которые нас не удовлетворяют, не больше 
, всего различных 
это 
.
Добавил оценку вероятности в статью.
Я понял, о чём вы говорите. В принципе, я могу дополнить статью сравнением эффективности по времени работы других алгоритмов по генерации простых/псевдопростых чисел с этим - спасибо за предложение по улучшению.
Но изначальной целью было продемонстрировать сам алгоритм как подход к генерации больших однозначно простых чисел, так как не видел, чтобы он где-то был описан.
Спасибо, исправил - заменил
на 
.
Тест Миллера-Рабина вероятностный, который даёт сильное псевдопростое число, а здесь генерируется однозначно простое число.
В данном случае
можно считать 
- когда мы рассматриваем конгруэнцию, то 
фиксированные параметры, а 
это переменная вместо 
. Примитивное решение
нас не интересует, так как мы выбирали 
, поэтому я так и записал.
А о каких других алгоритмах вы говорите? Пример можно?
Я так написал, чтобы подчеркнуть комментарий и следование словесному алгоритму - там действий никаких не нужно в else блоке. Можно заменить на # else: pass n isn't prime, choose another n
После выполнения инструкции break мы выйдем с цикла по выбору
aи перейдём к циклу по выборуn, поэтому произойдёт ровно то, что описано комментарием.