Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
re: 18.12.04 03:56 Число просмотров: 3289
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
> > Или Вы в состоянии сделать вывод исходя из первой
> главы
> > моей статьи? Так это только вступление...
>
> Не готов делать вывод, но готов ответить на вопрос :)) Как
> я уже писал:
>
> >>Более того, несложно заметить, что если n простое,
> то независимо от наличия известного >>разложения для
> всех предыдущих чисел, потребуется выполнить пробные
> деления на все простые >>числа, меньшие n. Таких
> чисел довольно много ( O( n/ln n ), по теореме Чебышева ),
> так что даже этот >>шаг алгоритма крайне далек от
> оптимального.
>
> Иными словами, независимо от предварительной обработки
> чисел от m до n-1, обработка числа n может потребовать
> значительного числа операций. Причем какие это операции -
> пробное деление, вычеркивание, или что-то еще - значения не
> имеет. Их надо сделать, каждая займет какое-то время. Стало
> быть она учитывается при оценке сложности алгоритма. В
> случае простого n - эта сложность порядка O( n/ln n ).
> Теорему Чебышева здесь доказывать не буду, предлагаю либо
> поверить мне на слово, либо (что лучше) обратиться к
> литературе по теории чисел.
>
> Если, к примеру, n = pq, где p, q - простые , сложность
> будет порядка O( k/ln k ), где k = min( p, q ). При этом,
> если p ~ q ~ n^{1/2}, то имеем O( 2 n ^{1/2} / ln n ). Что
> не сильно лучше. Этот случай на самом деле - наиболее
> сложный, и совершенно не зря над ним специалисты вот уже
> много лет (а точнее, веков) головы ломают.
>
> Так что, к сожалению, при неудачном выборе чисел Ваш
> алгоритм будет работать плохо. Причем такой неудачный выбор
> не является редкостью - в RSA, например, именно такие n и
> используются.
>
> А с литературой все же очень советую ознакомиться :))
>
> ===
> Lexy
Что (из литературы) посоветуете?
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
