Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
| | | | | | | | | |
Спасибо! 19.12.04 16:16 Число просмотров: 3067
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
|
> Обычно по теории чисел рекомендуют Виноградова "Теория > чисел", однако мне её так и не удалось найти, к сожалению. > > Зато нашёл замену: > http://www.3ka.mipt.ru/vlib/books/Mathematics/Theory/Number > Theory/1.html > > Там единицу надо заменять на номер главы и читать - > индексной страницы не удалось найти (этот адрес выдал > Яндекс по цитате из книги, которую я раньше полностью > выкачивал с уже не существующего адреса). Книжка > интересная, а главное простая и местами с юмором. Правда, > частично устарела, но всё равно ознакомиться стоит.
У меня в архиве есть все главы. Но все равно спасибо.
|
<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 уже не будет.
> она ни как не влияет на эти результаты. Двойка обязательно > присутствует в качестве множителя во всех четных числах и - > обязана быть простым числом.
Я в своих выкладках специально оговорил выбрасывание четных чисел из "хранилища".
|
|
|