Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще? 14.04.05 19:35 Число просмотров: 4460
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.04.05 19:46 Количество правок: 1
|
> Идея (p-1)-метода в том, что если N=p*q и все делители
> числа p-1 маленькие, то p-1 само является делителем m! для
> небольшого m. Поэтому число 2^(m!)-1 обязано делится на p.
> Откуда p можно найти как НОД(2^(m!)-1 mod N, N).
Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще?
> Сначала вычисляют число 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. И что будет, если сомножители p-1 и q-1 примерно равны?
И, собственно, не так уж и часто встречается ситуация, когда наибольший делитель p-1 будет достаточно мал (чтобы p-1 был делителем m!), чтобы за разумное время прокрутить вышеуказанный цикл :(.
А поиск перебором для небольших значений можно ли ускорить, если из перебора исключить заведомо составные числа? Понятно, что каждый раз проверять число на простоту - только огромная потеря времени, но с другой стороны циклично вычислять простые числа практически не реально - медленно. Поэтому можно ли исключить из перебора в цикле числа, заведомо кратные 2, 3, 5, 7 и т. д. до разумных значений? Ведь совсем несложно выкинуть четные, даже кратные 2 или 3. Причем "масочка", которая маскирует из натурального ряда числа, заведомо кратные небольшому количеству маленьких простых будет периодическая и ее можно применять циклично.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
