Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Я знаю. Мой вопрос-то, вообщем, и заключался в том, как... 31.03.04 16:41 Число просмотров: 2752
Автор: E-Lenin Статус: Незарегистрированный пользователь
|
> > представить число в виде n^k -(+) 1, и применить > алгоритм > > Special Number Field Sieve. > > Увы, этот алгоритм применим далеко не ко всем числам. Но
Я знаю. Мой вопрос-то, вообщем, и заключался в том, как проверить некое данное число на применимость к нему SNFS.
> можно использовать General Number Field Sieve, примениемое > к любым числам. Есть даже готовые сорцы: > http://www.math.ttu.edu/~cmonico/software/ggnfs/
Был я тут. По некоторым отзывам, эта реализация GNFSвесьма далёка от совершенства, о чём пишет и автор:
The polynomial selection code is awful. I don't mean bad - I mean awful. It's just something I wrote to generate slightly better than average polynomials.
The classical siever has not been optimized at all, and is not terribly smart.
The lattice siever should not even be used, except for educational purposes. It is terribly slow.
In short, you probably won't be factoring any 512-bit numbers with this code, but I think it's a good start.
В любом случае, хотелось бы узнать, можно ли факторизовать число SNFS, прежде чем использовать какой-либо другой метод.
> Как бы там ни было, факторизация 512 бит - это очень > трудоемко, поэтому рекомендую найти как можно больше > компьютеров для организации распределенных вычислений...
Ну, это как бы само собой понятно... :)
> > в виде n^k -(+) 1, кроме как прямым перебором значений > n и k? > > Если число сразу не было представлено в таком виде, то > крайне маловероятно, что такое представление вообще > существует.
Я бы не спешил делать подобные выводы. Мне думается, что программисту, реализующему RSA, нет никакого резона записывать число N в форме, удобной для его последующей факторизации.
Предвидя возражения вида "равно как и нет резона выбирать такие p и q, чтобы полученное N можно было представить в специальной форме", скажу, что в рассматриваемой мной реализации RSA каких-либо проверок N не обнаружено. Так что насчёт "крайне маловероятно", что N может быть представлено в специальной форме.... Тут я более оптимистичен.
Вообщем, хотелось бы какой-нибудь алгоритм, позволяющий представить заданное число в специальной форме, или хотя бы проверить число на возможность такого представления.
|
|
|