Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Маловероятность следует из требуемого вида, а не из... 31.03.04 22:54 Число просмотров: 2854
Автор: RElf <M> Статус: Member Отредактировано 31.03.04 22:56 Количество правок: 1
|
> В любом случае, хотелось бы узнать, можно ли факторизовать > число SNFS, прежде чем использовать какой-либо другой > метод.
> > > в виде n^k -(+) 1, кроме как прямым перебором значений > > n и k? > > > > Если число сразу не было представлено в таком виде, то > > крайне маловероятно, что такое представление вообще > > существует. > > Я бы не спешил делать подобные выводы. Мне думается, что > программисту, реализующему RSA, нет никакого резона > записывать число N в форме, удобной для его последующей > факторизации. > Предвидя возражения вида "равно как и нет резона выбирать > такие p и q, чтобы полученное N можно было представить в > специальной форме", скажу, что в рассматриваемой мной > реализации RSA каких-либо проверок N не обнаружено. Так что > насчёт "крайне маловероятно", что N может быть представлено > в специальной форме.... Тут я более оптимистичен.
Маловероятность следует из требуемого вида, а не из процедуры получения N.
> Вообщем, хотелось бы какой-нибудь алгоритм, позволяющий > представить заданное число в специальной форме, или хотя бы > проверить число на возможность такого представления.
Достаточно извлечь все корни (N+(-)1)^(1/k) для k=2..[log(N)] и проверить их на целочисленность. Корни можно извлекать целочисленным методом Ньютона и для каждого целочисленного корня r=[(N+(-)1)^(1/k)] проверить справедливость равенства r^k=?=(N+(-)1).
Как видите, для N имеется примерно 2*log(N) возможностей быть представленым в этом специальном виде. Поэтому вероятность наличия такого представления можно оценить величиной 2*log(N)/N, которая крайне мала.
Кстати, SNFS применимо не только к числам вида n^k -(+) 1, но, вообще говоря, к многочленам с малыми коэффициентами от n. Если уж так хочется применить SNFS, то нужно смотреть в этом направлении, хотя и здесь шансы невелики.
|
|
|