Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Во-первых, если Вы что-то знаете о факторизации, но ничего... 03.12.04 08:03 Число просмотров: 3671
Автор: lime Статус: Незарегистрированный пользователь
|
> Во-первых, совершенно неясно как помогает представленная
> форма сведения факторизовать произвольное n.
Во-первых, если Вы что-то знаете о факторизации, но ничего не слышали о проблеме NP-полноты или слышали но, как следует из неправильного употребления Вами некоторых терминов, недостаточно для подобного ответа, то следует перечитать написанное еще как минимум раз десять.
Разве где то было упомянуто, что данное представление помогает факторизовать число?
Если рассказывать всю историю сначала, то основанием для данного материала (потому что это скорее методический материал, а не статья) послужило данной обсуждение http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=111593
Задачей было показать полиномиальное сведение задачи ФАКТОРИЗАЦИЯ к одной из NP-полных задач (надеюсь, знаете зачем это обычно делается).
Материал этот не готовился для FAQ, я просто попросил администратора разместить его где-нибудь. Он счел нужным поместить его в FAQ и только.
> Во-вторых, в статье я нигде не нашёл, откуда следует, что
> сложность будет именно O(n^2), а не как-то по-другому.
Верно. Его нигде нет, т.к. задачей было на примере показать методику сведения. Операции умножения в столбик учат в первом классе и порядок сложности легко считается (по крайней мере у людей, для которых данный материал изначально был предназначен, никаких вопросов не возникло).
> Вообще написано достаточно пространно и если я правильно
> понял статью, то автором предлагается свести конкретное
> число к логическому высказыванию, откуда найти сомножители.
К терминологии. Исходная формула задачи ВЫП - это не логическое высказывание, если говорить строго.
> Хотя это я уже сам домыслил (а по-другому вообще непонятно
> как факторизировать, опираясь на приведённый текст).
> Однако, если следуя подобным рассуждениям попытаться
> прописать термы для числа длиной по-больше, то вообще
> делается видно, что количество переменных и логических
> переменных возрастает гораздо быстрее, чем функция x^2. Т.
> к. для факторизации никаких расуждений я не нашёл, то
> откуда появилась конечная формула не совсем ясно.
Внизу приведена табличка из которой очень хорошо виден рост сложности задачи по мере роста размера входных данных и очень замечательно видно, что рост как раз таки не превышает x^2. Квадрат - это верхняя ассимптотическая граница. Хотя, возможно, в порыве порицания Вы просто не дочитали материал до конца и бросились писать гневный отзыв. :)
> Хотя, на самом деле, это ведь O-символика и я точно так же
> мог бы написать O(n^0.1), что тоже было бы правильно.
> Поэтому тут всё неоднозначно.
Без комментариев (потому что даже не понял смысла).
> Последнее. Товарищ lime ссылается на неких авторов, которые
> смогли найти алгоритм со сложностью O(n^1,5). Могу
> совершенно точно сказать, что самый вычислительно
> сложный метод "метод половинного деления" имеет
> сложность O(n^0.5)
Да вообще то любой ВНИМАТЕЛЬНО прочитавший ВСЁ, что я написал, понял, что сложность полученной задачи ВЫП зависит исключительно от того, какой метод умножения мы используем. Задачей было - показать пример сведения на основе правил умножения, с которыми знаком каждый из тех, кто посещает этот форум. Имеется ввиду умножение столбиком.
> А вот О. Н. Василенко в книге "Теоретико-числовые алгоритмы
> в криптографии" говорит, что алгоритмов факторизации,
> которые имеют более высокие показатели, чем с
> субэкспоненциальной сложностью в данный момент не
> существует. И пока я не видел ниодного алгоритма, который
> бы это опровергнул.
А я вроде и не утверждаю, что создал его.
> Одним словом - смысл статьи я не уловил. Да и вообще, имхо,
> нельзя говорить о сложности решения какой-то задачи, что
> пытается сделать автор. Можно говорить лишь о сложности
> вычисления какого-то алгоритма.
Опять же повторюсь, но до конца дочитывать надо.
Последний небольшой раздельчик с заголовком "Сложность". О сложности было упомянуто только там.
Так вот термин "сложность" там применяется притяжательно к термину "алгоритм". Так что опять у меня непонятки.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
