BarloneКод недоделанный.
После x = pow(y1, t1, p) надо еще
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.

BarloneGennadiy UsovЭто второе условие теста Миллера-Рабина?
В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.Как в том анекдоте:
хрень, не хрень, а работает.

Я просто спросил, а тут такие выводы...

Я предупреждал, что в сообщении 21958523 рассматриваю только первое условие теста Миллера-Рабина,
причем было оговорено: "какой перечень остатков выдаёт этот тест".

Поскольку случайное число получается от 2 до (n - 2 ),
то, естественно, было интересно:
а что получится, если все случайные числа 2 до (n - 2 ) будут "применены".

Таким образом, я посчитал все остатки по модулю при подстановке всех возможных случайных чисел для чисел от 5 до 115.

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.

Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...

maytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...

BarloneGennadiy Usov Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.
Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.И что увидели на всей матрице? Жду ответа.

А можно посмотреть на отдельные столбцы матрицы. Найти логику и выработать эвристическое решение
(с проверкой на деление на сколько хватит мощности компьютера).

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.

Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA.
Для этого алгоритма требуются случайные простые числа.
Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел :
k – количество битов в двоичной записи проверяемого числа n.
С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n).

Так какое количество раундов выбрать?

Решил проверить с помощью простенькой программы на Питоне:

Получилось
709.782712893

И 1024 и 709 - числа большие.

А если уменьшить количество раундов в 2, 3, 4 раза?

maytonУсов. У меня идея появилась.
Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная.
От нее легко перейти к любому интервалу.
Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etcМонте-Карло - это случайность, вероятность.
Конечно, можно оценить с помощью перебора случайных чисел любой процесс, но это будет вероятностное определение.

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).

Dimitry SibiryakovGennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.К слову "достаточный" требуется уточнение "для чего".Рассмотрим небольшую задачу.

Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.

Пусть имеется подмножество простых чисел, которые определяются с помощью 100 раундов теста Миллера–Рабина (а может быть и меньше). Причем, числа этого подмножества имеют достаточное условие для простых чисел. Количество элементов в подмножестве в 2 раза меньше, чем количество простых чисел (для определённого N рассматриваемых чисел).

Элементы подмножества встречаются реже, чем элементы множества, но зато за определённый промежуток времени можно проверить в несколько раз больше чисел.

Главное, мы получаем не псевдопростые числа, а простые числа.

maytonGennadiy UsovНадо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.
Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.Почему 2000 ?В вики записано про случайные простые числа для RSA:

"В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k...
...
Выполнить тест Миллера — Рабина с количеством раундов не меньше k.".

У нас либо 1024, либо 2048