Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | |
Маловероятность следует из требуемого вида, а не из... 31.03.04 22:54 Число просмотров: 2950
Автор: 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, то нужно смотреть в этом направлении, хотя и здесь шансы невелики.
|
|
<theory>
|
Факторизация больших чисел. 31.03.04 14:44
Автор: E-Lenin Статус: Незарегистрированный пользователь
|
Понадобилось факторизовать 512-бит число, сами знаете для чего... :)
Перерыв кучу ссылок, я понял, что единственная надежда сделать это в более-менее приемлемое время - это попытаться представить число в виде n^k -(+) 1, и применить алгоритм Special Number Field Sieve.
Отсюда вопрос - каким образом (с помощью какого алгоритма) можно проверить, можно ли представить данное большое число в виде n^k -(+) 1, кроме как прямым перебором значений n и k?
Всем заранне спасибо за помощь.
|
|
Увы, этот алгоритм применим далеко не ко всем числам. Но... 31.03.04 15:27
Автор: RElf <M> Статус: Member
Отредактировано 31.03.04 15:28 Количество правок: 1
|
> Понадобилось факторизовать 512-бит число, сами знаете для
> чего... :)
> Перерыв кучу ссылок, я понял, что единственная надежда
> сделать это в более-менее приемлемое время - это попытаться
> представить число в виде n^k -(+) 1, и применить алгоритм
> Special Number Field Sieve.
Увы, этот алгоритм применим далеко не ко всем числам. Но можно использовать General Number Field Sieve, примениемое к любым числам. Есть даже готовые сорцы: http://www.math.ttu.edu/~cmonico/software/ggnfs/
Как бы там ни было, факторизация 512 бит - это очень трудоемко, поэтому рекомендую найти как можно больше компьютеров для организации распределенных вычислений...
> Отсюда вопрос - каким образом (с помощью какого алгоритма)
> можно проверить, можно ли представить данное большое число
> в виде n^k -(+) 1, кроме как прямым перебором значений n и k?
Если число сразу не было представлено в таком виде, то крайне маловероятно, что такое представление вообще существует.
|
| |
Я знаю. Мой вопрос-то, вообщем, и заключался в том, как... 31.03.04 16:41
Автор: 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 может быть представлено в специальной форме.... Тут я более оптимистичен.
Вообщем, хотелось бы какой-нибудь алгоритм, позволяющий представить заданное число в специальной форме, или хотя бы проверить число на возможность такого представления.
|
| | |
Маловероятность следует из требуемого вида, а не из... 31.03.04 22:54
Автор: 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, то нужно смотреть в этом направлении, хотя и здесь шансы невелики.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
