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

[Skipper]

Читал, что самый оптимальный алгоритм факторизации числа - GNFS.
Вопрос - какова у него трудоемкость в зависимости от N, где N - длина числа?

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

Цитата:

Для 100-значного GNFS справляется за несколько часов.

Поэтому хотелось бы узнать более точную формулу трудоемкости этого алгоритма, какие дробные степени и т.д. Может кто знает?

[Circiter]

Ну, может быть стоит начать с wiki/GNFS?

[Skipper]

Пишут, что НЕ СУЩЕСТВУЕТ полиномиальных алгоритмов факторизации. Существуют только экспоненциальные алгоритмы. Отличие всем известно. Начиная с некоторого большого N, где N - это как бы мера входных данных, а для факторизации - это длина числа, для всех случаев с входным числом, длинее чем N, экспоненциальный алгоритм будет дольше работать чем полиномиальный!

Вы дали ссылку на википедию, а там написана такая формула -

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

O большое - можно представить как некий множитель, зависящий в том числе и от архитектуры компьютера. Т.е. если мы пишем что трудоемкость алгоритма $O(X)$, это может занимать и $5*X$ операций, и $50*X$ операций и т.д. Докажем что это не экспоненциальный алгоритм, а самый что ни на есть - полиномиальный. Будем упрощать эту формулу, в сторону увеличения трудоемкости, и если окажется, что все равно она сводится к полиному, то мы докажем, что истинная трудоемкость тоже сводится к полиному и даже еще меньше. Заменим $(log log N)$ на $(log N)$. Ведь очевидно, что мы этим только увеличили трудоемкость, множитель $(log N)$ стал больше чем $(log log N)$. Чему равно $((log N)^{1/3}) * ((log N)^{2/3})$ ? Степени складываются, значит, мы получим $(log N)$. Все. (в 1-й степени). Посмотрим теперь на $(c+o(1))$. o маленькое от 1 не будет играть никакой роли для достаточно больших N при данном c, поэтому нашу исходную формулу можно переписать так -

$O( e^{ (c) (log N) } )$

Это равно

$O( (e^{log N}) ^ {c} ) $

и это равно

$O(N^{c})$

O большое - какой-то множитель, который не играет роли для достаточно больших N, т.к. N растет, а множитель не растет. Главная часть - $(N^c)$

Значит, исходя из того, что пишут - алгоритм факторизации - ПОЛИНОМИАЛЬНЫЙ алгоритм эквивалентный полиному степени c (в данном случае).

Или я что-то не так понял? Или данная формула в википедии не верна, и факторизация числа все таки имеет другую, экспоненциальную трудоемкость?

[deep blue]

Цитата:

где N - это как бы мера входных данных, а для факторизации - это длина числа

Вроде пишут, что n это не длина числа, а само число, а длина log n:

Цитата:

for factoring an integer n (consisting of log n bits)

[worm2]

Всё правильно, алгоритм полиномиальный, даже линейный, даже лучше. Но: если длиной ввода считать величину числа n. То есть, если, условно говоря, для факторизации числа, примерно равного $10^{10}$ нам понадобилась 1 секунда, то для факторизации числа, примерно равного $10^{1000}$, нам понадобится не $10^{990}$ секунд, а меньше. Гораздо меньше. Даже меньше, чем $10^{330}$, наверное.

Но в задаче факторизации под длиной ввода подразумевается отнюдь не величина самого числа, а длина его двоичной (ну, или там десятичной) записи, т.е. $\log n$. Вот относительно этого $\log n$ алгоритм хуже, чем любой полиномиальный, как легко видеть.

Опередили

[AD]

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

(иногда для удобства буду брать в квадратные скобки, они у меня эквивалентны круглым; * - умножение, ^ - возведение в степень.)

Категорически прошу не придумывать собственные обозначения, а использовать $\TeX$, как это принято на форуме.

Тема перемещена в карантин до исправления.
Чтобы тему вернули, нужно всё исправить и постучать сюда.

[AKM]

Вернул...

[Skipper]

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

Но давайте посчитаем, что у нас получается с данной формулой. O большое - какой то множитель, который не имеет зависимости от N, а зависит от реализации алгоритма, архитектуры компьютера и т.д. Писали что, для 100-значного числа, компьютер работающий с GNFS справляется за несколько часов. За секунду процессор производит до 3 млрд процессорных инструкций, за 3 часа - примерно 30 триллионов. Если алгоритм хорошо написан, то обычно минимальные количества процессорных инструкций достигает 1000, на не самую простую операцию. Значит O большое равно, скажем 1000, и это довольно заниженная его оценка. Значит, при подстановке числа $10^{100}$ , вместо N, в формулу

$ 1000 * ( e^{ (C) * ((log N)^{1/3}) * ((log log N)^{2/3}) } )$

мы должны получить около 30 триллионов. Отсюда вытекает что множитель c, находящийся в показатели степени, (или (c+o(1))), равен примерно 1,2726. И формула приобретает окончательный вид,

$ 1000 * ( e^{ (1,2726) * ((log N)^{1/3}) * ((log log N)^{2/3}) } )$

Теперь, если подставим в нее вместо N, $10^{100}$, то получим нужные нам 30 триллионов инструкций процессора.

Пишут, что могут взломать 2-килобитные и даже 3-килобитные криптографические ключи, т.е. могут факторизовать 3-килобитные полупростые числа. Поэтому рекомендуется использовать 4-килобитные и даже более. Но 3-килобитное число, примерно 1000-значное в десятичном представлении.
Для 1000-значного числа, мы получим число инструкций процессора, подставив в ту же формулу вместо N, число

$10^{1000}$

Получаем, что для того чтобы факторизовать $10^{1000}$, нужно
36 403 757 143 561 648 114 449 345 553 254 инструкций процессора.
Учитывая, что компьютер может выполнить примерно 3 млрд инструкций в секунду, мы получаем, что требуется около 10 000 квинтиллионов секунд, или 384 триллиона лет!
Если даже запустить на анализ 100 миллионов компьютеров (почти столько, сколько жителей в России), т.е. вся страна будет заниматься вычислениями, то потребуется около 4 миллионов лет! Надеятся что будет увеличение мощностей компьютеров в тысячи раз уже не приходится - многие пишут что закон Мура перестанет действовать уже к 2015 году, и размеры транзисторов не могут быть меньше 12-16 нанометров.

Значит, 4-килобитное число, никогда никто разложить не сможет в обозримом будущем и бояться нечего?

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

[maxal]

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

Значит, 4-килобитное число, никогда никто разложить не сможет в обозримом будущем и бояться нечего?

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

[Skipper]

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

[maxal]

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

[Skipper]

Квантовые компьютеры достаточной мощности (с достаточным количеством кубитов), возможно, не будут созданы никогда.

[rush]

maxal в сообщении #340306 писал(а):

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

Значит, 4-килобитное число, никогда никто разложить не сможет в обозримом будущем и бояться нечего?

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

неверно, разложить смогут, но не всякое. взять то же ${10}^{1000} = 2^{1000} \cdot 5^{1000}$. битовым сдвигом практически моментально получаем $5^{1000}$, а там всего 600-700 циферок, не проблема.

все алгоритмы, кроме полного перебора - вероятностные. оценивать трудоемкость вероятностного алгоритма есть грубость и за это полагается в морду. Трудоемкость же перебора $O(\frac {\sqrt N}{2})$. Это напрямую связано с определением простого числа.
Какие определения простых чисел ты знаешь?

[terminator-II]

как легко распознать степень математической безграмотности:

rush в сообщении #340319 писал(а):

$O(\frac {\sqrt N}{2})$.

[Circiter]

(Оффтоп)

2terminator-II

Цитата:

как легко распознать степень математической безграмотности

Это вы про знаменатель? :)