BarloneGennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии.
А дальше, ещё интересно.
Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Вот интересно!Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.Теперь у меня ещё одна идея.

Если из-за числа, которое оказалось составным, происходит облом при расшифровании,
то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование.
Проверка будет проходить на небольшом тесте.

Это займёт немного времени.

maytonGennadiy UsovЯ не критикую Миллера-Рабина, там всё прекрасно, проверено.
Но это тест только на составные числа. А дальше, допущение, что ...
Мы же говорим о простых числах для криптографии.
А это, как известно, две разные вещи.
Тогда надо честно сказать, что могут быть составные числа для криптографии.
А дальше, ещё интересно.
Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Мне сложно перечитывать взад все-все ваши гипотезы. Вы можете подытожить и изложить ваши сомнения
в виде пунктов?На самом деле гипотеза у меня пока одна:

имеет место большое количество составных чисел, которые после «пропускания» через тесты простоты «становятся» простыми числами.

Всё остальное - это следствие данной гипотезы.

Gennadiy UsovТеперь у меня ещё одна идея.
Если из-за числа, которое оказалось составным, происходит облом при расшифровании,
то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование.
Проверка будет проходить на небольшом тесте.
Это займёт немного времени.Пропустил предыдущее сообщение, а там есть ссылка на такую проверку, которая уже имеет место.

BarloneGennadiy UsovЕсли из-за числа, которое оказалось составным, происходит облом при расшифровании,
то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование.
Проверка будет проходить на небольшом тесте.
Это займёт немного времени.Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.Тут ещё одна идея.

Если всё равно каждое число проверяется на шифровании-дешифровании, то зачем нужен тест простоты?

На что больше тратится время: на тест или на Ш-Д?

Вот такие мысли

Но если поверка на Ш-ДШ отвергает какие-то числа, то есть приходится к нему подключаться, значит, тест простоты "пропускает"?

И проверка на Ш-ДШ является свого рода зачисткой огрехов теста простоты.

Так ещё одна идея:

пусть различные шифры "выплёвывают" очередные простые числа.

Если эти шифры "поставить" на диапазон, то сразу все простые числа найдем в этом диапозоне.

Только непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".

Dima TGennadiy UsovТолько непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".Нашли два числа, перемножили, результат всем показали, а числа тут же забыли. Числа нигде не сохраняются, никому не показываются, только произведение. Понятно?Понятно.

Была идея, что возможны составные числа, раз тест простоты "пропускает".
Однако выяснили, что шифр за тестом простоты всё "подчищает".

Была идея, формировать составные числа, раз тест простоты их "пропускает".
Однако то, из чего их формировать, надо где-то хранить.

Так что беседа была интересной

С другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.

Как же так, что произвольно выбранное случайное число точно попадает на простое число?

Фантастика!

BarloneGennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.
Как же так, что произвольно выбранное случайное число точно попадает на простое число?
Фантастика!Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.Так сколько чисел в результате перебирают "до ближайшего простого"?

10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024.

Если уже в районе 1.0Е+15 диапазоны под 500 чисел.

maytonФормула плотности простых на квадратный километр у нас есть. Можем примерно прикинуть сколько простых
в диапазоне 2^4096По этой формуле 10-ти младших бит не хватит.

maytonНу... я так понимаю что мифы разрушены. Все точки над i поставлены. И топик вобщем не нужен.
P.S. Cartago delenda est Наверное есть смысл подвести некоторые итоги...

1.Шифр RSA - это "тест простоты", который является более сильным по сравнению с общеизвестными тестами простоты.
Я говорю про шифры, которые применяют два простых числа.

Говорить, что он является "формулой" для поиска простых чисел на диапазоне, пока, наверное, рано.
Но всё равно, в дальнейшем, будем считать, что шифр определяет простые числа.

2.При этом, шифр определяет одновременно не одно простое число, а два простых числа.

3.Шифр ищет простое число в некотором диапазоне от случайного числа в три этапа.

4.На первом этапе "отбрасываются" составные числа
либо с помощью деления на небольшой перечень младших простых чисел
либо с помощью деления на числа 6хК+-1

5.На втором этапе "отбрасываются" составные числа с помощью определёного теста простоты (например, Миллера-Рабина).

6.На третьем этапе "отбрасывается" уже пара чисел, выбранных на первом и втором этапах,
с помощью тестового шифрования-дешифрования.

Получается, что шифр ищет одновременно два простых числа на двух разных диапазонах.

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

Как то так. Может быть я где-то не прав?