Доказательство равенства P и NP

[AV_77]

Угрозы нет, только использовать криптографию с открытыми ключами станет, мягко говоря, очень неудобно. Уже сейчас ключи для RSA длиной меньше 500 бит можно считать не стойкими. А если оценка числа операций станет полиномиальной, то нужно будет использовать ключи на порядки длиннее!

А вот на криптографию с секретными ключами это никак не повлияет.

[Руст]

Не факт, что полиномиальный алгоритм факторизации даст более быстрый алгоритм разложения для чисел порядка 500 бит. Например, быстрое умножение с помощью дискретного преобразования Фурье начинает давать выигрыш по сравнению с обычным умножением когда числа имеют более 2000-3000 бит. Там, где даст более быстрый результат, возможно никогда не будет использоваться в RSA.
К тому же, зачем зацикливаться на RSA. Как я говорил, даже если взлом требует $n^2$ то можно испотльзовать этот лгоритм. При $n=10^{10}$ для компьютера шифровка займет порядка секунды, взлом $10^{10}$ сек, примерно 35 лет.

[AV_77]

Руст в сообщении #266806 писал(а):

Как я говорил, даже если взлом требует $n^2$ то можно испотльзовать этот лгоритм. При $n=10^{10}$ для компьютера шифровка займет порядка секунды, взлом $10^{10}$ сек, примерно 35 лет.

Согласен, стойкость будет обеспечиваться. А вот как насчет удобства использования? Хранить ключи длиной $10^{10}$ бит весьма сложно. Не находите? Да и используются алгоритмы с открытыми ключами (в настоящее время) не для шифрования непосредственно, а для передачи ключей симметричных алгоритмов по открытым каналам связи. А передавать сообщение длиной 10Гбит только для передачи 256-битного ключа как-то накладно. Да и по времени не очень быстро будет.

Но вообще, сейчас смысла нет рассуждать о том, что будет. Когда появится полиномиальный алгоритм, тогда и можно будет о чем-то говорить, исходя из оценки сложности этого алгоритма.

[Somewhere far beyond]

Руст в сообщении #266806 писал(а):

Не факт, что полиномиальный алгоритм факторизации даст более быстрый алгоритм разложения для чисел порядка 500 бит. Например, быстрое умножение с помощью дискретного преобразования Фурье начинает давать выигрыш по сравнению с обычным умножением когда числа имеют более 2000-3000 бит. Там, где даст более быстрый результат, возможно никогда не будет использоваться в RSA.
К тому же, зачем зацикливаться на RSA. Как я говорил, даже если взлом требует $n^2$ то можно испотльзовать этот лгоритм. При $n=10^{10}$ для компьютера шифровка займет порядка секунды, взлом $10^{10}$ сек, примерно 35 лет.

Несогласен.
Здесь "палка о двух концах".
Говорите о числе $n=10^{10}$, как его хранить или пересылать это лишь мелкий технический вопрос, но как его получить что бы на нем можно было построить шифр RSA? Для это нужны два прайма размера $n=5*10^{9}$, для генерации которых уже нужен куб алгоритмической сложности и что бы сгенерировать шифр который не взломают полиномиальным алгоритмом факторизации квадратичной сложностью за 35 лет нужно $2*25*10^{18}$ сек - это полтора трилиона лет, по грубой оценке.
Если все таки удастся сгенерировать прайм размера $n=5*10^{9}$, что реально только в классе простых Мерсена (по современному стоянию т.ч.), которые не применимы в криптографии, то это число поймете куда отправить, предварительно ознакомившись с числом после символа "$" под пунктом D - http://w2.eff.org/awards/coop-prime-rules.php

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

Насчет темы, то считаю что $P\neq NP$, по крайней мере до поры изобретения принципиально новых вычислительных машин (не квантовых компьютеров).

[AV_77]

Somewhere far beyond в сообщении #267783 писал(а):

Говорите о числе $n=10^{10}$, как его хранить или пересылать это лишь мелкий технический вопрос, но как его получить что бы на нем можно было построить шифр RSA? Для это нужны два прайма размера $n=5*10^{9}$

Не $5 \cdot 10^9$, а $\sqrt{10^{10}} = 10^5$.

[venco]

AV_77 в сообщении #267807 писал(а):

Somewhere far beyond в сообщении #267783 писал(а):

Говорите о числе $n=10^{10}$, как его хранить или пересылать это лишь мелкий технический вопрос, но как его получить что бы на нем можно было построить шифр RSA? Для это нужны два прайма размера $n=5*10^{9}$

Не $5 \cdot 10^9$, а $\sqrt{10^{10}} = 10^5$.

Насколько я понял, здесь $n$ - длина числа используемого в RSA, или логарифм величины. Тогда для числа длины $10^{10}$ длина корня будет $5\cdot 10^9$.
Сейчас используются числа длины до нескольких тысяч. Если будет известен полиномиальный алгоритм разложения на множители, то длину чисел в RSA придётся сильно увеличить. На самом деле это совершенно убъёт RSA, т.к. оно основано на несопоставимо большей сложности разложения по сравнению с умножением.

[AV_77]

venco в сообщении #267842 писал(а):

Насколько я понял, здесь $n$ - длина числа используемого в RSA, или логарифм величины. Тогда для числа длины $10^{10}$ длина корня будет $5\cdot 10^9$.

Действительно, ошибся немного

[Руст]

Когда я привел аргументы, что можно работать с открытым ключом, даже если на взлом потребуется только $n^2$ операций, то не имелось в виду RSA. Даже, если $P=NP$, будут существовать алгоритмы с открытом ключом, для взлома которых потребуется делать как минимум $n^4$ степени операций. В этом случае уже точно не будут проблем для таких доказанных относительно сложности алгоритмов с открытым ключом. Да и квантовый компьютер, решающий за полиномиальное время факторизацию чисел не станет помехой.

[Somewhere far beyond]

Вы все же настаиваете, что возможна надежная асимметричная криптосистема, даже при наличии полиномиального алгоритма ее взлома. Позвольте привести несколько контраргументов:

Во первых, непонятно что за криптосистему вы имели ввиду, преобразований таких что $F^{-1}$ алгоритмически осуществить сложнее чем $F$ - множество ограничиваемое лишь фантазией, но не на каждом преобразовании возможно построить асимметричную криптосистему, пусть даже из корня ненадежную.

Для построения асимметричной криптосистемы необходимо следующее:
1. Алгоритм генерации открытого ключа.
2. Алгоритм генерации секретного ключа.
3. Алгоритм шифрования.
4. Алгоритм дешифровки.

И уже после этого рассматривать вопросы:
1. Насколько она криптостойка.
2. Варианты улучшения ее криптостойкости.
3. Варианты улучшения алгоритмов взлома.

И действительно обсудим конкретные вопросы на конкретном примере, а рассуждения о том, "если бы до-ка-бы, то были бы грибы" - это на форум философии.

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

В третьих, допустим все же решили использовать алгоритм нахождения секретного ключа из открытого, то почему следует использовать обычный компьютер т.е. машину Тьюринга?
Существуют множество инженерных методов реализации алгоритмов на аппаратный уровень. К примеру, тот же алгоритм умножения, аппаратная реализация которого на $2^{32}$ элементов, что вполне реально при современном уровне нанотехнологий и даже более чем $32$, позволит на созданной машине производить умножение гигабитных чисел в $2^{30}$ раз быстрее чем на обычном компьютере. Если на обычном компьютере сложность алгоритма умножения примерно-равных гигабитных чисел порядка $O (ln^2N)$, то плюс производительности этого инженерного творения снизит сложность алгоритма умножения до $O (lnN)$. Машина может просто напросто "съесть" степень полинома полиномиального алгоритма. Нельзя пренебрегать возможностями инженерного решения, увлекаясь математическими выкладками для конкретного устройства.
Что касается NP-задач, то конечно же возможна аппаратная реализация, к примеру, той же факторизации чисел, но конструкция устройства на $2^{32}$ элемента алгоритма решета числового поля даст незначительный плюс, если на этой машине разлагать на множители число RSA-1024, то время работы будет эквивалентно факторизации числа RSA-1000 на обычной машине. Но, теоретически возможно построить машину у которой время работы нахождения обратного преобразования было примерно равно времени нахождения прямого преобразования. Однако, на создание микросхем для такой машины не хватит песка на планете.

И еще, для выпуска криптографии на рынок, как продукта, что бы убедить юзеров в ее надежности, очень важна гарантия ее криптостойкости, сейчас это основано не просто разной сложности алгоритмов создания и взлома, а на том что они принадлежат к разным классам сложности. И это дает им статус - возможно надежны.
Даже криптосистемы основанные на сложности нахождения дискретного логарифма в поле эллиптической кривой не все считают лучшими, так как теория эллиптических кривых еще не прошла вековой выдержки. Хотя судя по теор. данным - надежнее нет, т.к. для взлома этих систем нет еще даже субэкспоненциальных алгоритмов.

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

[ddn]

Хотел бы обратить внимание не обсуждавшиеся еще вопросы доказуемости по данной проблеме. Возможно превеликое множество разных вариантов:
- не существуют полиномиальные $NP$-полные алгоритмы ($P\not=NP$);
-- существует доказательство несуществования полиномиальных $NP$-полных алгоритмов, ($Proof(P\not=NP)$), степень неразрешимости $=0$;
-- не существует доказательства несуществования полиномиальных $NP$-полных алгоритмов, ($\neg Proof(P\not=NP)$), степень неразрешимости $\geqslant 1$;
--- существует доказательство несуществования доказательства несуществования полиномиальных $NP$-полных алгоритмов, ($Proof(\neg Proof(P\not=NP))$), степень неразрешимости $=1$;
--- не существует доказательства несуществования доказательства несуществования полиномиальных $NP$-полных алгоритмов, ($\neg Proof(\neg Proof(P\not=NP))$), степень неразрешимости $\geqslant 2$;
и т.д......
- существуют полиномиальные $NP$-полные алгоритмы ($P=NP$);
-- ...(аналогичные вопросы разрешимости утверждения $P=NP$ решаются тривиально, см. ниже)...

Такие же цепочки вопросов можно поставить и в отношении свойств (полиномиальность, $NP$-полнота) какого-либо конкретного алгоритма:
- данный алгоритм $A$ обладает свойством $P$, ($P(A)$);
-- существует доказательство того, что данный алгоритм $A$ обладает свойством $P$, ($Proof(P(A))$);
-- не существует доказательства того, что данный алгоритм $A$ обладает свойством $P$, ($\neg Proof(P(A))$);
--- существует доказательство несуществования доказательства того, что данный алгоритм $A$ обладает свойством $P$, ($Proof(\neg Proof(P(A)))$);
и т.д......
- данный алгоритм $A$ не обладает свойством $P$, ($\neg P(A)$);
-- ...(аналогичные вопросы разрешимости утверждения $\neg P(A)$)...;
здесь $P$ - одно из свойств: полиномиальность, $NP$-полнота.

Также, возможны различные утверждения относительно отдельных классов полиномиальных $NP$-полных алгоритмов, обладающих одинаковой разрешимостью по этим свойствам:
- существуют указанные алгоритмы, для которых существует доказательства их полиномиальности и $NP$-полноты (каждый из них можно найти явно);
- существуют указанные полиномиальные алгоритмы, для которых существует доказательство их $NP$-полноты, но не существует доказательства их полиномиальности;
- существуют указанные алгоритмы, для которых существует доказательство их полиномиальности, но не существует доказательства их $NP$-полноты;
- существуют указанные алгоритмы, для которых не существует ни доказательства их полиномиальности, ни доказательства их $NP$-полноты;
...(прочие комбинации)...
полагаю, если некоторый класс не пусть, то и все классы с более неразрешимыми свойствами своих алгоритмов не пусты.

Можно рассмотреть аналогичные вопросы разрешимости, затрагивающие параметры полиномиальной сложности алгоритмов ($C$ и $K$).

Есть ли какие либо результаты по перечисленным проблемам?


Простое доказательство существования полиномиальных $NP$-полных алгоритмов не предполагает еще явного построения такого алгоритма, и поэтому оно, само по себе, полностью бесполезно для практической криптографии.
Если же у нас имеется конкретный полиномиальный $NP$-полный алгоритм, то недоказуемость его полиномиальности и $NP$-полноты в принципе не помешает его практическому использованию - за полиномиальное время мы всегда сможем получить и проверить результат.

Как же найти такой алгоритм, если он существует? На него можно выйти за конечное, заранее ограниченное, но возможно, никогда точно не известное, число шагов.
Простейший вариант: выберем какую-нибудь $NP$-полную задачу и будем перебирать для нее все возможные алгоритмы по порядку (номер каждого алгоритма можно сделать б.-м. регулярно зависящим от длины его описания), на каждом шаге рассматривая для проверки только один алгоритм. Для первого шага рассмотрим первый алгоритм. Если рассматриваемый на $n$-ом шаге алгоритм для каждого из аргументов длины $m$ от $1$ до $n$ дает правильное решение за время не более, скажем, $n\cdot m^n$, то на следующем ($(n+1)$-ый) шаге будем рассматривать тот же алгоритм, иначе - на следующем шаге рассмотрим первый, еще не рассмотренный, алгоритм (следующий по порядку за алгоритмом $n$-ого шага). Рано или поздно, на каком-то шаге (его номер может быть очень велик) мы выйдем на какой-нибудь полиномиальный $NP$-полный алгоритм, который далее не будет сменятся на всех следующих шагах (стационарный).
Если некоторый полиномиальный $NP$-полный алгоритм имеет порядковый номер $n_0$ и решает указанную задачу за время не более $Cn^K$ при длине аргумента $n$, то он пройдет проверку для всех шагов $n\geqslant n_0$ в данном случае, если и только если $n_0\geqslant C$. Мы выйдем на тот их полиномиальных $NP$-полных алгоритмов, удовлетворяющих вышеуказанному условию, что имеет наименьший номер. Но мы никогда не сможем определить достигли ли мы этого алгоритма, если (что вполне возможно) для него невозможно доказать ни одной верхней оценки времени выполнения, вида $Cn^K$.
Такой (или подобный) алгоритм лучше использовать совместно с конкретными практическими вычислениями, по мере роста потребностей, находя алгоритм, применимый для все большего диапазона длин аргументов, но и со все большей допустимой временной сложностью.
Сам предложенный (перебирающий алгоритмы) алгоритм может быть использован как полиномиальный $NP$-полный (когда $P=NP$): если условием проверки рассматриваемого на $n$-ом шаге алгоритма будет получение алгоритмом правильного (проверяется) результата за время не более $n\cdot m^n$, где $m$ - длина аргумента. Данный $NP$-полный алгоритм будет полиномиальным, в отличие от переборного (перебирающего результаты и проверяющего их) алгоритма.
Таким образом, существуют полиномиальные $NP$-полные алгоритмы, то существует алгоритм с доказательством своей полиномиальности и $NP$-полноты.
Предложенный алгоритм сам имеет номер, притом небольшой (посему, он, скорее всего, дойдет и до шага с собственным номером), а так как для того, чтобы дойти до стационарного полиномиального $NP$-полного алгоритма, потребуется вероятно очень большое (но постоянное) число шагов, то предложенный алгоритм, рассматривая себя, скорее всего проверки не пройдет.

[Ираклий]

ddn в сообщении #272916 писал(а):

Есть ли какие либо результаты по перечисленным проблемам?

Было бы интересно узнать это! Думаю, нет.

ddn в сообщении #272916 писал(а):

номер каждого алгоритма можно сделать б.-м. регулярно зависящим от длины его описания

Не понял, расшифруйте, пожалуйста. Что это значит и почему это важно? Произвольная эффективная нумерация не годится?

ddn в сообщении #272916 писал(а):

Таким образом, существуют полиномиальные $NP$-полные алгоритмы, то существует алгоритм с доказательством своей полиномиальности и $NP$-полноты.

Весьма интересное наблюдение! Но я не понял Вашей терминологии: алгоритм может быть полиномиальным, но NP-полной может быть только задача. Что Вы подразумеваете под NP-полным алгоритмом?

[ddn]

Ираклий писал(а):

ddn писал(а):

номер каждого алгоритма можно сделать б.-м. регулярно зависящим от длины его описания

Не понял, расшифруйте, пожалуйста. Что это значит и почему это важно? Произвольная эффективная нумерация не годится?

Это не важно, но желательно. Если мы будем перебирать алгоритмы по мере роста длины их описания, мы (я уверен) быстрее выйдем на стационарный полиномиальный $NP$-полный алгоритм (уменьшим очень большую константу $C_1$ во временной сложности $Cn^K+C_1$ нашего переборного алгоритма), по сравнению с произвольным эффективным упорядочением (делающим $C_1$ заранее неограниченной - до выбора конкретного упорядочения).

Ираклий писал(а):

ddn писал(а):

Таким образом, если существуют полиномиальные $NP$-полные алгоритмы, то существует алгоритм с доказательством своей полиномиальности и $NP$-полноты.

Весьма интересное наблюдение!

Это тривиальное наблюдение. Специалистам оно должно быть давно известно, они на таких конструкциях собаку съели.

Ираклий писал(а):

Но я не понял Вашей терминологии: алгоритм может быть полиномиальным, но NP-полной может быть только задача. Что Вы подразумеваете под NP-полным алгоритмом?

Да, вы правы. Я имел ввиду полиномиальный алгоритм решающий некоторую конкретную NP-полную задачу.