Подскажите пожалуйста!
Как определить время, за которое с помощью алгоритма факторизации приведенного на: http://www.kakotkin-rv.narod.ru возможно факторизовать натуральный ряд длинною n.
С уважением! Какоткин Р. В.
Несложно понять, что сложность факторизации числа n по...17.12.04 06:03 Автор: Lexy Статус: Незарегистрированный пользователь
Несложно понять, что сложность факторизации числа n по приведенному алгоритму больше либо равна самому числу n (поскольку требует факторизации всех предыдущих чисел). Уже из этого очевидно, что алгоритм не лучше полного перебора, и прикладной ценности не имеет.
Более того, несложно заметить, что если n простое, то независимо от наличия известного разложения для всех предыдущих чисел, потребуется выполнить пробные деления на все простые числа, меньшие n. Таких чисел довольно много ( O( n/ln n ), по теореме Чебышева ), так что даже этот шаг алгоритма крайне далек от оптимального.
Очень жаль, что автор, прежде чем публиковать свою работу, не потрудился сделать самые элементарные оценки, а заодно поинтересоваться уже известными результатами в этой области.
===
Lexy
не совсем так17.12.04 08:44 Автор: LLL <Алексей> Статус: Member
> Несложно понять, что сложность факторизации числа n по > приведенному алгоритму больше либо равна самому числу n > (поскольку требует факторизации всех предыдущих чисел). Уже > из этого очевидно, что алгоритм не лучше полного перебора, > и прикладной ценности не имеет.
Этот алгоритм своей массовостью вроде бы оптимальнее прямого перебора делителей.
> Более того, несложно заметить, что если n простое, то > независимо от наличия известного разложения для всех > предыдущих чисел, потребуется выполнить пробные деления на > все простые числа, меньшие n.
Автор делить как раз не собирался. Он вроде бы планировал вычеркивать множители разложения в порядке прогрессии.
> Очень жаль, что автор, прежде чем публиковать свою работу, > не потрудился сделать самые элементарные оценки, а заодно > поинтересоваться уже известными результатами в этой > области.
Это точно.
re: не совсем так17.12.04 08:58 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
> > Несложно понять, что сложность факторизации числа n по > > приведенному алгоритму больше либо равна самому числу > n > > (поскольку требует факторизации всех предыдущих > чисел). Уже > > из этого очевидно, что алгоритм не лучше полного > перебора, > > и прикладной ценности не имеет. > > Этот алгоритм своей массовостью вроде бы оптимальнее > прямого перебора делителей. > > > Более того, несложно заметить, что если n простое, то > > независимо от наличия известного разложения для всех > > предыдущих чисел, потребуется выполнить пробные > деления на > > все простые числа, меньшие n. > > Автор делить как раз не собирался. Он вроде бы планировал > вычеркивать множители разложения в порядке прогрессии. > > > Очень жаль, что автор, прежде чем публиковать свою > работу, > > не потрудился сделать самые элементарные оценки, а > заодно > > поинтересоваться уже известными результатами в этой > > области. > > Это точно.
Мне необходим сам порядок распределения простых множителей. Он (его следствия) будет использоваться в доказательстве.
О практическом применении в криптографии речь не идет. Есть другие области применения.
К Вам на форум я обратился для всесторонней оценки самого алгоритма (и проверки наличия ошибок). А вот мнения о "ценности" алгоритма - субъективные. Все зависит от области применения.
Если необходимо факторизовать сразу большое количество чисел, то какой из алгоритмов будет наиболее эффективным?
еще раз о практике17.12.04 09:50 Автор: LLL <Алексей> Статус: Member
> > Если необходимо факторизовать сразу большое количество > > чисел, то какой из алгоритмов будет наиболее > эффективным? > > На практике факторизовывать числа приходится не от 2 до n, > а между n и m, где n и m достаточно велики, поэтому Ваш > алгоритм здесь неприменим.
Смотря о какой практике идет речь. А если необходима факторизация числа между n и m, где n и m достаточно велики, то возможно начать процесс факторизации от "опорного числа". Речь об этом пойдет позже.
Или Вы в состоянии сделать вывод исходя из первой главы моей статьи? Так это только вступление...
Не готов делать вывод, но готов ответить на вопрос :)) Как я...17.12.04 23:02 Автор: Lexy Статус: Незарегистрированный пользователь
> Или Вы в состоянии сделать вывод исходя из первой главы > моей статьи? Так это только вступление...
Не готов делать вывод, но готов ответить на вопрос :)) Как я уже писал:
>>Более того, несложно заметить, что если n простое, то независимо от наличия известного >>разложения для всех предыдущих чисел, потребуется выполнить пробные деления на все простые >>числа, меньшие n. Таких чисел довольно много ( O( n/ln n ), по теореме Чебышева ), так что даже этот >>шаг алгоритма крайне далек от оптимального.
Иными словами, независимо от предварительной обработки чисел от m до n-1, обработка числа n может потребовать значительного числа операций. Причем какие это операции - пробное деление, вычеркивание, или что-то еще - значения не имеет. Их надо сделать, каждая займет какое-то время. Стало быть она учитывается при оценке сложности алгоритма. В случае простого n - эта сложность порядка O( n/ln n ). Теорему Чебышева здесь доказывать не буду, предлагаю либо поверить мне на слово, либо (что лучше) обратиться к литературе по теории чисел.
Если, к примеру, n = pq, где p, q - простые , сложность будет порядка O( k/ln k ), где k = min( p, q ). При этом, если p ~ q ~ n^{1/2}, то имеем O( 2 n ^{1/2} / ln n ). Что не сильно лучше. Этот случай на самом деле - наиболее сложный, и совершенно не зря над ним специалисты вот уже много лет (а точнее, веков) головы ломают.
Так что, к сожалению, при неудачном выборе чисел Ваш алгоритм будет работать плохо. Причем такой неудачный выбор не является редкостью - в RSA, например, именно такие n и используются.
А с литературой все же очень советую ознакомиться :))
===
Lexy
re:18.12.04 03:56 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
> > Или Вы в состоянии сделать вывод исходя из первой > главы > > моей статьи? Так это только вступление... > > Не готов делать вывод, но готов ответить на вопрос :)) Как > я уже писал: > > >>Более того, несложно заметить, что если n простое, > то независимо от наличия известного >>разложения для > всех предыдущих чисел, потребуется выполнить пробные > деления на все простые >>числа, меньшие n. Таких > чисел довольно много ( O( n/ln n ), по теореме Чебышева ), > так что даже этот >>шаг алгоритма крайне далек от > оптимального. > > Иными словами, независимо от предварительной обработки > чисел от m до n-1, обработка числа n может потребовать > значительного числа операций. Причем какие это операции - > пробное деление, вычеркивание, или что-то еще - значения не > имеет. Их надо сделать, каждая займет какое-то время. Стало > быть она учитывается при оценке сложности алгоритма. В > случае простого n - эта сложность порядка O( n/ln n ). > Теорему Чебышева здесь доказывать не буду, предлагаю либо > поверить мне на слово, либо (что лучше) обратиться к > литературе по теории чисел. > > Если, к примеру, n = pq, где p, q - простые , сложность > будет порядка O( k/ln k ), где k = min( p, q ). При этом, > если p ~ q ~ n^{1/2}, то имеем O( 2 n ^{1/2} / ln n ). Что > не сильно лучше. Этот случай на самом деле - наиболее > сложный, и совершенно не зря над ним специалисты вот уже > много лет (а точнее, веков) головы ломают. > > Так что, к сожалению, при неудачном выборе чисел Ваш > алгоритм будет работать плохо. Причем такой неудачный выбор > не является редкостью - в RSA, например, именно такие n и > используются. > > А с литературой все же очень советую ознакомиться :)) > > === > Lexy Что (из литературы) посоветуете?
По поводу факторизации неплохой обзор результатов приведен в книге Ростовцева и Маховенко "Введение в криптографию с открытым ключом". Во второй главе рассмотрен ряд методов, с обоснованиями и оценками их сложности. В главе 3 описывается также метод решета числового поля. Этот метод сейчас считается наиболее эффективным. В книге рассматривается в приложении к дискретному логарифмированию, но он же применяется и для факторизации (с соответствующими модификациями). Плюс - там же можно найти ряд полезных ссылок.
На английском материалов на ту же тему намного больше. Начать можно, например, отсюда: http://en.wikipedia.org/wiki/Integer_factorization и дальше - по ссылкам :)) Либо просто поискать в интернете "factorization", "number field sieve", "quadratic sieve", "elliptic curve factorization" и т.п.
===
Lexy
Другие ссылки19.12.04 10:43 Автор: Heller <Heller> Статус: Elderman
Там единицу надо заменять на номер главы и читать - индексной страницы не удалось найти (этот адрес выдал Яндекс по цитате из книги, которую я раньше полностью выкачивал с уже не существующего адреса). Книжка интересная, а главное простая и местами с юмором. Правда, частично устарела, но всё равно ознакомиться стоит.
Спасибо!19.12.04 16:16 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
> Обычно по теории чисел рекомендуют Виноградова "Теория > чисел", однако мне её так и не удалось найти, к сожалению. > > Зато нашёл замену: > http://www.3ka.mipt.ru/vlib/books/Mathematics/Theory/Number > Theory/1.html > > Там единицу надо заменять на номер главы и читать - > индексной страницы не удалось найти (этот адрес выдал > Яндекс по цитате из книги, которую я раньше полностью > выкачивал с уже не существующего адреса). Книжка > интересная, а главное простая и местами с юмором. Правда, > частично устарела, но всё равно ознакомиться стоит.
У меня в архиве есть все главы. Но все равно спасибо.
Все главы чего?19.12.04 18:57 Автор: Heller <Heller> Статус: Elderman
re:а для n какого примерно порядка предполагается использовать сей алгоритм?16.12.04 09:01 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
В принципе, мне интересна оценка быстродействия алгоритма. Использовать его (на данный момент времени) я собираюсь для n , при которых уравнение a^m+b^m+c^m=z^m представимо в целых числах.
Оценку, IMHO, полезнее делать для предполагаемой реализации,...16.12.04 17:45 Автор: LLL <Алексей> Статус: Member
> В принципе, мне интересна оценка быстродействия алгоритма.
Оценку, IMHO, полезнее делать для предполагаемой реализации, а не для некоей математической абстракции.
А при реализации от порядка n очень сильно зависит выбор носителя информации, на котором будут храниться оперативные данные алгоритма. Это может быть кэш процессора, ОЗУ или даже система хранения на жестких дисках. Разница в быстродействии при этом будет измеряться порядками, а вовсе не процентами.
> Использовать его (на данный момент времени) я собираюсь для > n , при которых уравнение a^m+b^m+c^m=z^m представимо в > целых числах.
И где тут в уравнении n? Или считать, что n=m?
re:16.12.04 20:23 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
> > В принципе, мне интересна оценка быстродействия > алгоритма. > > Оценку, IMHO, полезнее делать для предполагаемой > реализации, а не для некоей математической абстракции. > А при реализации от порядка n очень сильно зависит выбор > носителя информации, на котором будут храниться оперативные > данные алгоритма. Это может быть кэш процессора, ОЗУ или > даже система хранения на жестких дисках. Разница в > быстродействии при этом будет измеряться порядками, а вовсе > не процентами. > > > Использовать его (на данный момент времени) я > собираюсь для > > n , при которых уравнение a^m+b^m+c^m=z^m представимо > в > > целых числах. > > И где тут в уравнении n? Или считать, что n=m?
Считать, что n = z^m m=4
95 800^4 + 217 519^4 + 414 560^4 = 422 481^4
тогда немного посчитаем...16.12.04 21:32 Автор: LLL <Алексей> Статус: Member Отредактировано 16.12.04 21:32 Количество правок: 1
> > > Использовать его (на данный момент времени) я > > собираюсь для > > > n , при которых уравнение a^m+b^m+c^m=z^m > представимо > > в > > > целых числах. > > > > И где тут в уравнении n? Или считать, что n=m? > > Считать, что n = z^m m=4 > 95 800^4 + 217 519^4 + 414 560^4 = 422 481^4
Конкретика приближает нас к практике...
Попробуем прикинуть нижнюю оценку требуемых вычислительных ресурсов.
Наше n по своей крутизне порядка 1e22.
Обозначим за P(N) произведение первых N простых чисел.
P(10) < 7e9, значит у каких-то чисел, больших 7e9, в разложении будет минимум 10 разных элементов (это очень заниженная оценка, т.к. к 1e22 мы и близко не подкрались).
Хранение чисел, которыми мы будем манипулировать, требует более 72 бит (1e22 > 2^74) или 9 байт, т.е. результат факторизации одного числа требует для хранения минимум 90 байт.
Четные числа можно выкинуть, поэтому где-то разместить нам придется данных более, чем на
1e22 / 2 * 90 байт > 409e9 ТБайт
(и это очень заниженная оценка).
Что-то мне подсказывает, что в ближайшие лет 30 хранилищ такой емкости у человечества не предвидится.
Кстати, об изложении алгоритма... Утверждение "Для того чтобы начать факторизацию нам не нужно знать ни одного простого числа" кажется спорным, ибо алгоритм насквозь пронизан числом 2, и интуиция мне подсказывает, что неявно мы используем его в качестве первого простого.
Разумеется! Но!16.12.04 21:57 Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
> Кстати, об изложении алгоритма... Утверждение "Для того > чтобы начать факторизацию нам не нужно знать ни одного > простого числа" кажется спорным, ибо алгоритм насквозь > пронизан числом 2, и интуиция мне подсказывает, что неявно > мы используем его в качестве первого простого.
Единица присутствует во всех результатах факторизации, но она ни как не влияет на эти результаты. Двойка обязательно присутствует в качестве множителя во всех четных числах и - обязана быть простым числом.
именно "Но!"16.12.04 22:01 Автор: LLL <Алексей> Статус: Member
> Единица присутствует во всех результатах факторизации, но
Это при промежуточном хранении, а я говорил об окончательных результатах, где 1 уже не будет.
> она ни как не влияет на эти результаты. Двойка обязательно > присутствует в качестве множителя во всех четных числах и - > обязана быть простым числом.
Я в своих выкладках специально оговорил выбрасывание четных чисел из "хранилища".