Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
А я в поисковике набрал "генерация больших простых чисел",... 07.10.08 11:28 Число просмотров: 5156
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> > по формуле N=SR+1, то возможно ли что генерилка > > "зациклится"? > > Что за формула?
А я в поисковике набрал "генерация больших простых чисел", там почти везде присутствуют именно такие обозначения.
Я даже ссылку к сообщению цеплял, только что-то она не прицепилась. Фраза оттуда: "Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа N=SR+1, S < R < 4S+2 не существует."
То есть метод вероятностный, можно искать очень долго, слишком долго, а то и вообще не найти. Про это что-то в статьях совсем ничего.
> Вроде простые числа во всех RSA-сотоварищи реализациях > генерятся просто случайным поиском с вероятностной > проверкой на простоту.
Точно. Только не совсем "просто случайным", а есть случайный с достаточно вероятным получением желаемого результата. Правда нигде не описана насколько вероятность выше, чем просто случайный поиск.
Суть его в том, что каждую итерацию получаем простое число примерно в двое большей разрядности, умножая его на случайное четное такого же порядка, что и очередное простое и добавляя единицу. Начинается все с простого, которое выбирается случайно из таблицы или генерится обычным способом - поиском/перебором.
Вот ссылка, где наиболее доступно написано.
|
|
|