Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Алгоритм 08.02.03 02:55 Число просмотров: 4086
Автор: RElf <M> Статус: Member Отредактировано 08.02.03 08:46 Количество правок: 1
|
> Уж простите меня, > но чегото у меня не получается такая элементарная весч. > Квадратное уравнение я решать умею, > но добраться до него никак не могу =)))
Как я понял, тебе известны ключи (n,e) и (n,d), и нужно найти разложение n=p*q.
Квадратное уравнение возникает только в случае, когда известна величина phi(n)=(p-1)(q-1).
Известные ключи RSA дают только кратное phi(n) число m=e*d-1. Поэтому приходится использовать нечто более изощренное. Например, следующий вероятностный алгоритм:
сначала из m "извлекается" максмальная степень 2-ки, т.е. оно представляется в виде m = 2^k * t, где t - нечетное число. Далее делаем такой цикл:
{
начало цикла:
берем случайное число a из интервала [1,n]
вычисляем b = a^t mod n
если b==1 mod n, то goto начало цикла
вложенный цикл: { пока b^2 mod n не равно 1, полагаем b = b^2 mod n }
находим r = НОД(b-1,n)
если r не равно 1, то это нетривиальный делитель n. конец.
goto начало цикла
}
|
|
|