информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Атака на InternetЗа кого нас держат?Spanning Tree Protocol: недокументированное применение
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / beginners
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
Вопрос 15.12.04 18:45  Число просмотров: 2900
Автор: amirul <Serge> Статус: The Elderman
<"чистая" ссылка>
> Я намерен использовать данный алгоритм (вернее его
> свойства) для доказательства теорем из теории чисел.
Вам необходима именно программная реализация или все равно какая, лишь бы числа были?

Если Вам все равно и Вы собираетесь всерьез заниматься математикой, то рекомендую специализированный математический пакет.

Maple (http://www.maplesoft.com/) - сам им пользуюсь - очень мощная штука
MuPAD (http://www.mupad.de/) - ни разу не видел. Но вроде достаточно мощный и при этом есть бесплатная версия
<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 уже не будет.

> она ни как не влияет на эти результаты. Двойка обязательно
> присутствует в качестве множителя во всех четных числах и -
> обязана быть простым числом.

Я в своих выкладках специально оговорил выбрасывание четных чисел из "хранилища".
1  |  2  |  3 >>  »  




Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach