информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Spanning Tree Protocol: недокументированное применениеСетевые кракеры и правда о деле Левина
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 HP закрыла 16-летнюю уязвимость... 
 Microsoft советует пользователям... 
 MS Edge обогнал FireFox 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / beginners
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
re: Психологу. 17.12.04 08:43  Число просмотров: 2341
Автор: Какоткин Р. В. Статус: Незарегистрированный пользователь
<"чистая" ссылка>
> Есть задачи, о самом факте попытки решения которых можно
> заявлять только имея на руках какой-либо результат,
> представляющий научную ценность (пусть, даже,
> отрицательный). Конечно, компрометировать самого себя не
> запретишь, но вам теперь до конца дней будут крутить
> пальцем у виска, даже если вам, и правда, удастся что-либо
> доказать.

Такой результат есть. Вернемся к разговору после его публикации.

С уважением! Какоткин Р. В.
<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-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach