BugTraq.Ru: форум / theory / Очень бы хотелось увидеть это доказательство. Т.е.,...

информационная безопасность
без паники и всерьез

подробно о проекте

Spanning Tree Protocol: недокументированное применение

Анализ криптографических сетевых...

Модель надежности двухузлового...

Специальные марковские модели надежности...

С наступающим

Microsoft обещает радикально усилить...

Ядро Linux избавляется от российских...

bugtraq.ru / форум / theory

Имя

Пароль


ФОРУМ


	все доски
	FAQ
	IRC
	новые сообщения

	site updates
	guestbook
	beginners
	sysadmin
	programming
	operating systems
	theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap

регистрация

Легенда:

новое сообщение

закрытая нитка

новое сообщение

в закрытой нитке

старое сообщение

Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
Новичкам также крайне полезно ознакомиться с данным документом.

Очень бы хотелось увидеть это доказательство. Т.е.,... 17.12.04 22:40 Число просмотров: 4346
Автор: Lexy Статус: Незарегистрированный пользователь

<"чистая" ссылка>

> В заключении хотелось бы сказать, что на мой личный взгляд
> задача факторизации - чистейшая NP полная задача, безо
> всяких скидок. Даже доказать смогу. :)

Очень бы хотелось увидеть это доказательство. Т.е., совершенно очевидно, что "факторизация" не более сложна чем "выполнимость" (с точностью до полинома). Однако это - не есть NP-полнота. Для NP-полноты нужно доказать еще и обратное. Что вовсе не так очевидно.

Так что ждем с нетерпением :))

===
Lexy

Поиск

Математики стоят на пороге уничтожения криптографии - TARASA 08.09.04 08:11 [9782]
- Каюсь. Я от криптографии и от высшей математики да... - TARASA 13.09.04 16:56 [5732]
- Задача журналиста - найти горячий материал. В принципе... - lime 13.09.04 16:11 [5512]
  - Существуют. Криптосистемы ЭльГамаля, Рабина, Нидер... - Heller 13.09.04 20:16 [6551]
    - Значит проблема будет только в быстром отказе от ставших... - lime 15.09.04 07:55 [5036]
- Интересно, с чего такой вывод? - cybervlad 10.09.04 08:36 [5322]
  - объясните пожалуйста еще раз - kata 22.09.04 08:31 [4921]
    - Попробую обобщить в двух словах все ранее сказанное - Heller 22.09.04 22:47 [5085]
      - скорость факторизации - kata 23.09.04 10:01 [5052]
        Pari/GP раскладывает за доли секунды [url] - RElf 23.09.04 14:46 [5056]
        Maple тоже - amirul 27.09.04 11:20 [5193]
        Согласно его хелпу: - RElf 27.09.04 12:20 [4786]
        Круто! Действительно, очень быстро. Если задача фа... - kata 24.09.04 06:57 [4721]
        В RSA сейчас используются модули порядка 2^1024, а то и... - RElf 24.09.04 10:19 [4905]
        Ахренеть! - kata 24.09.04 07:43 [4642]
        Ну что такое 100 битное число - малышка. А сколько... - DPP 24.09.04 10:18 [5112]
        скорость факторизации и лома - kata 23.09.04 11:53 [4971]
        Если речь о RSA, то 56 битными ключами никто не по... - DPP 23.09.04 19:13 [4675]
        немного путаницы - leo 23.09.04 13:07 [4869]
        При использовании алгоритма Ленстры сложность будет... - Heller 23.09.04 10:32 [5063]
        Эти формулы выдраны из O-нотации, поэтому верхняя оценка... - RElf 23.09.04 15:09 [4524]
        Сама функция задаётся непосредственно как L(n), а не как... - Heller 23.09.04 18:19 [4097]
        Выражение L(n)=(2+o(1))*f(n) - чуть более точное чем... - RElf 23.09.04 22:24 [4374]
        Странно, апплетовая факторизовалка на... - DPP 23.09.04 10:20 [4178]
        Попоробовал дать ей несколько разных коротких чисел вида... - Heller 23.09.04 10:52 [4074]
        А что значит короткое число? (-) - kata 23.09.04 11:27 [4103]
        Всмысле маленькое. Термин "короткое" несколько нек... (-) - Heller 23.09.04 17:51 [4083]
  - объясните пожалуйста - kata 21.09.04 16:28 [4142]
    - Ну, во-первых, не p, q и e, а на основе n и e - Heller 21.09.04 17:54 [4393]
      - попытка № 2 - kata 22.09.04 07:18 [4131]
        Спасибо, уже не надо. - kata 22.09.04 07:55 [4322]
        Про n=p1p2p3.. - Heller 22.09.04 09:46 [4299]
        чем дальше в лес... - kata 22.09.04 10:59 [4087]
        Вероятность этого при правильной реализации ничтожно мала. - RElf 22.09.04 15:56 [4240]
  - Ниже следующий автор по имени amirul упомянул еще... - lime 13.09.04 15:23 [4430]
  - Ну и мои 5 копеек - amirul 10.09.04 10:40 [4544]
    - Первое. Я не понимаю фразы "NP-полнота неизвестна"... - lime 13.09.04 15:36 [4857]
      - Не спора ради, но пониманья для - amirul 22.09.04 11:02 [4348]
        Эта задача уже несколько лет классифицируется как... - lime 30.09.04 14:37 [4474]
        Очень бы хотелось увидеть это доказательство. Т.е.,... - Lexy 17.12.04 22:40 [4346]
        http://bugtraq.ru/forum/faq/theory/fact2sat.html (-) - lime 28.12.04 09:01 [4073]
        отлично, но не то :( - Lexy 11.01.05 14:09 [4473]
        Я лучше расскажу, т.к. не встречал ни одной достаточно... - lime 30.09.04 14:04 [4153]
        Сведение - lime 08.10.04 09:29 [4290]
        Обо всём сразу - Heller 22.09.04 21:01 [5675]
        Что-то мне подсказывает, что Вы ошиблись в определении... - Lexy 17.12.04 22:43 [3947]
        Занимай очередь. :) (-) - lime 28.12.04 09:05 [3940]
        Ошибся-ошибся. Сам перечитал и не понял, что напис... (-) - Heller 28.12.04 18:10 [4047]
        И вновь каша в голове. - lime 01.10.04 12:40 [4253]
        IMHO про гипотезу Римана - leo 22.09.04 21:21 [4204]
- гонево - _йцукенг_ 08.09.04 14:46 [4715]
- Некоторые непонятки - nkiller 08.09.04 14:44 [4463]
  - я дилетант в криптографии, но пару линков дам. - _йцукенг_ 08.09.04 14:57 [4963]
    - Насчет источника, на который линк дан. Написано жу... - lime 13.09.04 15:56 [4702]
- Глупость, имхо - Heller 08.09.04 13:45 [4621]
  - просто сообщение Средств Массовой ДезИнформации (-) - kavkav@ukr.net 03.10.04 20:29 [4275]

Page build time: 0 s

Design: Vadim Derkach