информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Сетевые кракеры и правда о деле ЛевинаАтака на Internet
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
 С наступающим 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Я знаю. Мой вопрос-то, вообщем, и заключался в том, как... 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 может быть представлено в специальной форме.... Тут я более оптимистичен.

Вообщем, хотелось бы какой-нибудь алгоритм, позволяющий представить заданное число в специальной форме, или хотя бы проверить число на возможность такого представления.
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach