Трудоемкость алгоритма факторизации

[rush]

Ну забыл я, что постоянный множитель не учитывается. Исправьте мое сообщение, и не истекайте желчью, пожалуйста.

[Skipper]

Попробуем вычислить трудоемкость лучшего алгоритма факторизации от длины числа в двоичной записи. В этом случае, очевидно (исходя из старой формулы), трудоемкость алгоритма станет такой (вместо log N, нужно писать N, и изменятся коэффициенты в степени) -

$O( e^{ ( (c) * ((N)^{1/3}) * ((log N)^{2/3}) } )$

При достаточно большом N, множитель $(N)^{1/3}$ станет намного больше чем множитель $(log N)^{2/3}$. Предположим, что лучший алгоритм факторизации в будущем будет модифицирован и улучшен (чего стоит ожидать), и в формуле множитель $(log N)^{2/3}$ вообще пропадет, останется только множитель $(N)^{1/3}$. Также, при улучшенной модификации множитель C станет равным 1. Изменение множителя $(N)^{1/3}$ видимо, вряд ли произойдет, это очень весомый множитель, и чтобы он изменился, скажем до $(N)^{1/4}$ или еще меньших степеней, нужно чтобы придумали алгоритм основанный на принципиально иных идеях.

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

$O( e^{ N^{1/3} } )$

O большое будет равно 1, если для факторизации сконструируют специальный компьютер с такой архитектурой, чтобы он за одну свою инструкцию выполнял необходимую операцию алгоритма (т.е. специализированный на аппаратном уровне компьютер). Стоит также ожидать, что скорости работы будут такими - порядка 1 миллиарда операций в секунду (это физический предел, и скорости эти уже почти не растут, а после 2015 года вообще перестанет действовать закон Мура). Тогда, чтобы факторизовать 1-килобитное число, потребуется всего 22026 сложных операций на аппаратном уровне такого компьютера, т.е. факторизация пройдет за доли секунды. Это число мы получили, поставив в формулу

$ e^{ N^{1/3} } $

вместо N - длину числа, 1000, т.е. экспонента возводится всего в 10-ю степень. Можно ли алгоритм с такой формулой трудоемкости, назвать экспоненциальным? Если бы N не было в степени 1/3, то количество требуемых операций было бы $e^{1000}$, т.е. порядка $10^{434}$. А так, всего 22026. Как видим, это возведение в степень 1/3, показателя N, очень сильно уменьшает трудоемкость алгоритма, настолько, что он работает по сути, как полиномиальный, и с большими N, равными нескольким тысячам.

Все это наводит на мысли о том, что возможно для факторизации числа, вообще существует самый настоящий полиномиальный алгоритм. Тогда, факторизация числа - это задача класса P, а если к ней можно свести NP-полную задачу, то тем самым мы докажем равенство P=NP, и решим математическую проблему тысячелетия, проблему Кука.

А с данным алгоритмом, для которого верна такая формула трудоемкости, и с такими компьютерами, мы не решим за разумное время, например, факторизацию 300-килобитных чисел и более. Для них, если подставить в формулу

$ e^{ N^{1/3} } $

вместо N, 300000, получим, что потребуется около $10^{29}$ операций, $10^{20}$ секунд, и даже если настроят миллион таких компьютеров, потребуется около 4 миллионов лет на решение.

Значит, если P не равно NP, и не придумают более совершенные алгоритмы чем $O( e^{ N^{1/3} } )$, то 300-килобитные ключи будут надежны на многие тысячелетия. Для этого нужно сгенерировать пару простых 150-килобитных чисел. Вопрос - существуют ли программы, которые могут генерировать такие числа на обычном персональном компьютере?

-- Пт июл 23, 2010 17:08:44 --

Возможно также, кто-нибудь изобрел алгоритм факторизации, с трудоемкостью $O( e^{ N^{1/3} } )$, а может, даже и еще лучше - $O( e^{ N^{1/4} } )$, но про это никто не знает. Спецслужбы могут легко взламывать все эти ключи, которые сейчас используются (1-2-килобитные и даже 4-килобитные), а про это никто не знает, и все уверены, что они надежно защищены.

Вот поэтому, крайне важно направить усилия по установлению, к какому подмножеству NP-задач принадлежит алгоритм факторизации. Нужно, чтобы какой-нибудь математик строго доказал, что не существует в принципе, алгоритма факторизации, с трудоемкостью, меньшей чем, скажем, $O( e^{ N^{1/3} } )$, и тогда подобрав необходимой длины ключ, можно было бы быть уверенным на тысячелетия, что никто его не взломает.

Вот поэтому, эта задача определения минимально возможной трудоемкости алгоритма факторизации, как мне кажется, должна была бы войти в семерку (или восьмерку?) проблем тысячелетия. И за нее не 1 миллион долларов надо премию выплачивать, а еще больше. Чтобы было побольше заинтересованных решить эту проблему, мне кажется, она важнее чем например, гипотеза Пуанкаре, за которую институт Клэя предлагал Перельману миллион долларов.

[worm2]

То, что Вы написали по поводу равенства P=NP, совершенно не в кассу, т.к. не доказано, что задача факторизации является NP-полной (см. http://satisfiability.narod.ru/files/www.cryptography.ru-1169817.html, вопрос 2).

[Skipper]

worm2
Я знаю что не доказано что задача факторизации является NP-полной. И я писал, что ЕСЛИ это докажут, то решим проблему. Т.к. судя по тому насколько сейчас хорош алгоритм, есть основания полагать, что его все таки улучшат и до настоящего полиномиального.

[Xaositect]

Skipper в сообщении #340554 писал(а):

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

Если факторизация является NP-полной, то NP=coNP (Это потому, что задача "имеет ли данное число $x$ делитель, меньший данного $y$", лежит в $\mathrm{NP}\cap\mathrm{coNP}$). А NP=coNP - это как-то странно.

[Skipper]

Что именно странно?

[Xaositect]

Skipper в сообщении #341182 писал(а):

Что именно странно?

NP=coNP странно.
Это значит, что TAUT лежит в NP, по сути, что любая тавтология имеет короткое доказательство. Не верится мне в это.