Мы ушли от темы топика.

Тема топика звучит так:
"лучше решать обратную задачу:
найти критерии возможных псевдослучайных чисел, чтобы с помощью их выбирать нужные «случайные числа» для криптографии."

О чём идёт речь.

В процессе нахождения больших случайных чисел выполняется тест Миллера-Рабина к раз по количеству к битов в числе.
(или любого другого теста)
При этом в какой-то момент случайное число, по версии теста, не имеет признаков составных чисел, и это число "назначается" простым числом.

Вопрос один:
а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?

Dima TGennadiy UsovВопрос один:
а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?Сравнить на предмет чего?Например:
Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.

Dima TGennadiy UsovНапример:
Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.Такое возможно, это в википедии написано.
Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составнымЕсли это возможно, то сразу следующий вопрос:

а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)?

Dima TGennadiy UsovЕсли это возможно, то сразу следующий вопрос:
а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)?
На маленьких. Псевдопростое число Мало того, что наука изучает простые числа, но она ещё изучает и псевдопростые числа.

А где можно применить псевдопростые числа?

BarlonemaytonМы можем генерировать произвольные произведения известных нам простых.
И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число
простое - то мы засчитываем ошибку.
Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры.
С этим надо определится. В какой конфигурации настроек мы его будем тестить.
Тогда матрица отчота получистя многомерная.Проверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Интересная информация.

Я посмотрел на эти числа, и в них, кроме первого, 2 множителя, причем каждый из них "в районе" корня квадратного из этого числа.

Почему-то эти числа заканчиваются на 5537838510751 (13-й порядок).
А что далее?

BarloneА еще говорят есть тест на псевдопростоту , для которого пока не нашли ни одного контрпримераА Вы задумывались о том, почему много тестов на простоту ?
Мне известно около 10 тестов.

Или так много простоты, что тесты со всеми не справляются?

BarloneПроверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Посмотрел это сообщение подробно, и там оказалась ссылка на таблицу всех таких чисел до 2^64.

А их очень много...

И сразу имеет место очередной вопрос:

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

И есть другие составные числа, которые почти равны этим псевдопростым числам (один порядок).
И тоже состоят из двух множителей, которые почти равны друг другу.

Так почему эти составные числа нельзя использовать в криптографии?
Из-за ограничителя - теста простоты (очередного)?

BarloneНа примерно 4*10^17 простых приходится 16757 составных, проходящих 4 раунда теста. То есть у нас вероятность приблизительно одна двадцатипятитриллионная, что мы ошибочно примем составное число за простое.А чем составное число плохо для криптографии?

Допустим, приняли составное число за простое ...

Что произойдет с шифрованием и дешифрованием?

BarloneGennadiy UsovА чем составное число плохо для криптографии?
Допустим, приняли составное число за простое ...
Что произойдет с шифрованием и дешифрованием? 21820624 Допустим...

Но клиент не знает.
Система пропустила псевдослучайное число.
И что - облом,
и что делать клиенту, если не получилась расшифровка?

BarloneGennadiy UsovПочему-то эти числа заканчиваются на 5537838510751 (13-й порядок).
А что далее?Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt Немного поизучал эту таблицу.

1 число – 10 знаков. Произведение первых двух множителей равно почти 4-м величинам третьего множителя.

8 чисел – 12 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3)

15 чисел – 14 знаков. Первый множитель в два раза меньше второго множителя (с точностью до 1).

Далее много чисел – 15 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3).

Далее - мала ячейка