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





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Во-первых, если Вы что-то знаете о факторизации, но ничего... 03.12.04 08:03  Число просмотров: 3016
Автор: 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)
Да вообще то любой ВНИМАТЕЛЬНО прочитавший ВСЁ, что я написал, понял, что сложность полученной задачи ВЫП зависит исключительно от того, какой метод умножения мы используем. Задачей было - показать пример сведения на основе правил умножения, с которыми знаком каждый из тех, кто посещает этот форум. Имеется ввиду умножение столбиком.

> А вот О. Н. Василенко в книге "Теоретико-числовые алгоритмы
> в криптографии" говорит, что алгоритмов факторизации,
> которые имеют более высокие показатели, чем с
> субэкспоненциальной сложностью в данный момент не
> существует. И пока я не видел ниодного алгоритма, который
> бы это опровергнул.
А я вроде и не утверждаю, что создал его.

> Одним словом - смысл статьи я не уловил. Да и вообще, имхо,
> нельзя говорить о сложности решения какой-то задачи, что
> пытается сделать автор. Можно говорить лишь о сложности
> вычисления какого-то алгоритма.
Опять же повторюсь, но до конца дочитывать надо.
Последний небольшой раздельчик с заголовком "Сложность". О сложности было упомянуто только там.
Так вот термин "сложность" там применяется притяжательно к термину "алгоритм". Так что опять у меня непонятки.
<site updates> Поиск 








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


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