Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Можно и 3, можно и любое другое число. Но это ничем особо от... 15.04.05 06:36 Число просмотров: 4082
Автор: RElf <M> Статус: Member
Отредактировано 15.04.05 06:37 Количество правок: 1
|
> Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще?
Можно и 3, можно и любое другое число. Но это ничем особо от 2 отличатся не будет.
> > Сначала вычисляют число 2^(m!) mod N. Это делается
> примерно
> > так:
> > a=2;
> > for i=1 to m do
> > a = a^i mod N;
> > end do;
> > m выбирается из расчета чем больше - тем лучше, но так
> > чтобы вычисления занимали разумное время.
>
> А на каждом шаге цикла почему бы НОД не вычислить и
> остановиться, как только НОД не будет равен 1?
Вычисление НОД - дорогая операция. Лучше ее вычислять только один раз в конце, во избежание нежелательных тормозов.
> > Потом просто вычисляют НОД(a-1,N). Если он равен:
> > * 1 - значит, m взято слишком маленьким;
> > * p - вуаля, найдет нетривиальный делитель N;
> > * N - значит, m взято слишком большим (но это не так
> > страшно - надо уменьшить m и повторить).
>
> Нужели можно взять такое m, что НОД будет равен N.
Ну, например, m=N гарантированно даст в качестве результата N. Другое дело, что для больших N, прогон такого цикла будет практически неосуществим.
> И что будет, если сомножители p-1 и q-1 примерно равны?
Нужно выбрать такое m, чтобы p-1 (но не q-1, или же наоборот) было делителем m!.
> И, собственно, не так уж и часто встречается ситуация,
> когда наибольший делитель p-1 будет достаточно мал (чтобы
> p-1 был делителем m!), чтобы за разумное время прокрутить
> вышеуказанный цикл :(.
Теперь еще не чаще. ;)
Имея в виду этот метод, при генерации от p-1 и q-1 часто требуют наличия больших простых делителей.
> А поиск перебором для небольших значений можно ли ускорить,
> если из перебора исключить заведомо составные числа?
Можно ускорить (но не особо), есть соответствующие модификации. Но основная идея та же.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
Можно и 3, можно и любое другое число. Но это ниче... - RElf