Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Идея (p-1)-метода в том, что если N=p*q и все делители числа... 14.04.05 12:18 Число просмотров: 4586
Автор: RElf <M> Статус: Member
Отредактировано 14.04.05 12:21 Количество правок: 1
|
> Где-то видел про хитрую факторизацию, вроде как, методом
> N-1. Идея была в том, что N-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!) mod N. Это делается примерно так:
a=2;
for i=1 to m do
a = a^i mod N;
end do;
m выбирается из расчета чем больше - тем лучше, но так чтобы вычисления занимали разумное время.
Потом просто вычисляют НОД(a-1,N). Если он равен:
* 1 - значит, m взято слишком маленьким;
* p - вуаля, найдет нетривиальный делитель N;
* N - значит, m взято слишком большим (но это не так страшно - надо уменьшить m и повторить).
|
|
|
подробно о проекте
Анализ криптографических сетевых...
