2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Трудоемкость алгоритма факторизации
Сообщение20.07.2010, 04:14 
Читал, что самый оптимальный алгоритм факторизации числа - GNFS.
Вопрос - какова у него трудоемкость в зависимости от N, где N - длина числа?

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

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


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

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 01:22 
Ну, может быть стоит начать с wiki/GNFS?

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 16:15 
Пишут, что НЕ СУЩЕСТВУЕТ полиномиальных алгоритмов факторизации. Существуют только экспоненциальные алгоритмы. Отличие всем известно. Начиная с некоторого большого 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 (в данном случае).

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

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 17:12 
Цитата:
где N - это как бы мера входных данных, а для факторизации - это длина числа
Вроде пишут, что n это не длина числа, а само число, а длина log n:
Цитата:
for factoring an integer n (consisting of log n bits)

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

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

Опередили :-)

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 17:57 
Skipper в сообщении #340214 писал(а):
(иногда для удобства буду брать в квадратные скобки, они у меня эквивалентны круглым; * - умножение, ^ - возведение в степень.)
Категорически прошу не придумывать собственные обозначения, а использовать $\TeX$, как это принято на форуме.
 !  Тема перемещена в карантин до исправления.
Чтобы тему вернули, нужно всё исправить и постучать сюда.

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 19:45 
Аватара пользователя
Вернул...

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение21.07.2010, 22:42 
Ну что ж...
Когда пытаются вычислить трудоемкость алгоритма, то в формуле за 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-килобитного числа, и получу еще большие временные результаты. Т.е. можно гарантированно раз и навсегда взять ключ достаточных размеров и никто его не взломает в ближайшие тысячелетия?

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение22.07.2010, 01:36 
Аватара пользователя
Skipper в сообщении #340298 писал(а):
Значит, 4-килобитное число, никогда никто разложить не сможет в обозримом будущем и бояться нечего?

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

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

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

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение22.07.2010, 05:22 
Квантовые компьютеры достаточной мощности (с достаточным количеством кубитов), возможно, не будут созданы никогда.

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение22.07.2010, 07:12 
maxal в сообщении #340306 писал(а):
Skipper в сообщении #340298 писал(а):
Значит, 4-килобитное число, никогда никто разложить не сможет в обозримом будущем и бояться нечего?

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

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

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

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение22.07.2010, 11:33 
как легко распознать степень математической безграмотности:
rush в сообщении #340319 писал(а):
$O(\frac {\sqrt N}{2})$.

 
 
 
 Re: Трудоемкость алгоритма факторизации
Сообщение22.07.2010, 14:41 

(Оффтоп)

2terminator-II
Цитата:
как легко распознать степень математической безграмотности

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

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group