Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
Не готов делать вывод, но готов ответить на вопрос :)) Как я... 17.12.04 23:02 Число просмотров: 3264
Автор: Lexy Статус: Незарегистрированный пользователь
|
> Или Вы в состоянии сделать вывод исходя из первой главы
> моей статьи? Так это только вступление...
Не готов делать вывод, но готов ответить на вопрос :)) Как я уже писал:
>>Более того, несложно заметить, что если 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
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
