Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
| | | |
Согласен! 17.12.04 10:34 Число просмотров: 2757
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
|
|
|
<beginners>
|
Факторизация натурального ряда 08.12.04 13:52 [leo, LLL, whiletrue]
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
Подскажите пожалуйста!
Как определить время, за которое с помощью алгоритма факторизации приведенного на: 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 достаточно велики, поэтому Ваш алгоритм здесь неприменим.
|
| | | | |
и еще раз о практике 17.12.04 10:25
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
> > Если необходимо факторизовать сразу большое количество
> > чисел, то какой из алгоритмов будет наиболее
> эффективным?
>
> На практике факторизовывать числа приходится не от 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
Что (из литературы) посоветуете?
|
| | | | | | | |
links 19.12.04 01:50
Автор: 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
|
Обычно по теории чисел рекомендуют Виноградова "Теория чисел", однако мне её так и не удалось найти, к сожалению.
Зато нашёл замену:
http://www.3ka.mipt.ru/vlib/books/Mathematics/Theory/NumberTheory/1.html
Там единицу надо заменять на номер главы и читать - индексной страницы не удалось найти (этот адрес выдал Яндекс по цитате из книги, которую я раньше полностью выкачивал с уже не существующего адреса). Книжка интересная, а главное простая и местами с юмором. Правда, частично устарела, но всё равно ознакомиться стоит.
|
| | | | | | | | | |
Спасибо! 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
|
|
Если Виноградова, то был бы очень признателен, если бы Вы отослали их мне на почту (в профиле есть адрес).
|
| | | | | | | | | | | |
Виноградов 20.12.04 10:29
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
> Если Виноградова, то был бы очень признателен, если бы Вы
> отослали их мне на почту (в профиле есть адрес).
У меня в архиве те же файлы, что и в нете. Вот ссылка:
http://gbg.ru/unit/145149
Книга стоит всего 77 руб.
|
|
а для n какого примерно порядка предполагается использовать сей алгоритм? 15.12.04 20:30
Автор: LLL <Алексей> Статус: Member
|
|
|
| |
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 уже не будет.
> она ни как не влияет на эти результаты. Двойка обязательно
> присутствует в качестве множителя во всех четных числах и -
> обязана быть простым числом.
Я в своих выкладках специально оговорил выбрасывание четных чисел из "хранилища".
|
|
|
подробно о проекте
Анализ криптографических сетевых...
