Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Не совсем понятно 14.11.04 00:44 Число просмотров: 3521
Автор: Heller <Heller> Статус: Elderman
|
Во-первых, совершенно неясно как помогает представленная форма сведения факторизовать произвольное n.
Во-вторых, в статье я нигде не нашёл, откуда следует, что сложность будет именно O(n^2), а не как-то по-другому.
Вообще написано достаточно пространно и если я правильно понял статью, то автором предлагается свести конкретное число к логическому высказыванию, откуда найти сомножители. Хотя это я уже сам домыслил (а по-другому вообще непонятно как факторизировать, опираясь на приведённый текст). Однако, если следуя подобным рассуждениям попытаться прописать термы для числа длиной по-больше, то вообще делается видно, что количество переменных и логических переменных возрастает гораздо быстрее, чем функция x^2. Т. к. для факторизации никаких расуждений я не нашёл, то откуда появилась конечная формула не совсем ясно.
Хотя, на самом деле, это ведь O-символика и я точно так же мог бы написать O(n^0.1), что тоже было бы правильно. Поэтому тут всё неоднозначно.
Последнее. Товарищ lime ссылается на неких авторов, которые смогли найти алгоритм со сложностью O(n^1,5). Могу совершенно точно сказать, что самый вычислительно сложный метод "метод половинного деления" имеет сложность O(n^0.5)
А вот О. Н. Василенко в книге "Теоретико-числовые алгоритмы в криптографии" говорит, что алгоритмов факторизации, которые имеют более высокие показатели, чем с субэкспоненциальной сложностью в данный момент не существует. И пока я не видел ниодного алгоритма, который бы это опровергнул.
Одним словом - смысл статьи я не уловил. Да и вообще, имхо, нельзя говорить о сложности решения какой-то задачи, что пытается сделать автор. Можно говорить лишь о сложности вычисления какого-то алгоритма.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
