информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Сетевые кракеры и правда о деле ЛевинаГде водятся OGRыSpanning Tree Protocol: недокументированное применение
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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Не совсем понятно 14.11.04 00:44  Число просмотров: 2984
Автор: Heller <Heller> Статус: Elderman
<"чистая" ссылка>
Во-первых, совершенно неясно как помогает представленная форма сведения факторизовать произвольное n.

Во-вторых, в статье я нигде не нашёл, откуда следует, что сложность будет именно O(n^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