Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Нет, видимо я путано объяснил. Идея какая: при обычном... 26.08.04 10:52 Число просмотров: 3197
Автор: Heller <Heller> Статус: Elderman
|
Нет, видимо я путано объяснил. Идея какая: при обычном логарифмировании мы вычисляем m=(c(mod n))^(1/e). Ну якобы обратную функцию. Перебор c (mod n) не занимает очень уж много ресурсов - основная работа приходится на вычисление ^(1/e) - корня степени e.
Ещё раз приведу гомоморфное сво-во, что бы перед глазами было, (m1m2)^e=(m1^e)*(m2^e)=с1с2 (mod n)
Если я возьму свою пару m2 и c2, то, "ломая" их произведение, я буду точно знать, из каких значений с1с2 (mod n) мне точно не надо вычислять корень. Это проистекает из свойств моего сомножителя m1. Так как он в моём примере 30 (хотя можно взять любое число, удовлетворяющее данным ключам), то я должен рассматривать только те числа, которые делятся на 90 (т. к. 30 возводится в степень e). Это проверяется элементарно. К тому же я могу сразу вычеркнуть начальную стадию перебора, ориентируясь на разрядность моего искусственно введённого m2.
Таким образом область перебора на самом деле увеличивается, однако уменьшается количество вычислений "корней степени e" - что гораздо более трудоёмко, чем ... (mod n). Вот только не совсем ясны пропорции, в каких это происходит и, соответственно, неясно насколько мой способ эффективнее.
|
|
|