Числа, свободные от квадратов

Сообщение №13503 от Михалыч 25 ноября 2004 г. 13:36
Тема: Числа, свободные от квадратов

числом, свободным от квадратов (=бесквадратным числом) называется целое, не делящееся на неединичный квадрат целого.
ВОПРОС.
Существует ли СПЕЦИФИЧЕСКИЙ алгоритм "отсева" бесквадратных чисел, НЕ СВОДЯЩИЙСЯ к тому или иному ОБЩЕМУ алгоритму факторизации.
Буду благодарен за ссылки.


Отклики на это сообщение:

> числом, свободным от квадратов (=бесквадратным числом) называется целое, не делящееся на неединичный квадрат целого.
> ВОПРОС.
> Существует ли СПЕЦИФИЧЕСКИЙ алгоритм "отсева" бесквадратных чисел, НЕ СВОДЯЩИЙСЯ к тому или иному ОБЩЕМУ алгоритму факторизации.
> Буду благодарен за ссылки.

Подозреваю, что специфического алгоритма не придумано. Облазил доступные архивы препринтов и статей на предмет близости с заданным вопросом. Вывод: народ в основном занимается задачей распределения БЧ. Но следует принять во внимание ограниченность моих возможностей (подробно просканировал лишь CiteSeer.IST - http://citeseer.ist.psu.edu/cs; просмотрел еще пару более мелких архивов; не попал на MathSciNet - http://www.ams.org/mathscinet - нет доступа).
Если не секрет, Михалыч, в каком контексте всплыла эта задача? Ответьте, пожалуйста, почтой (если ответите).
С уважением, sceptic.


> > числом, свободным
от квадратов (=бесквадратным числом) называется целое, не делящееся на неединичный квадрат целого.
> > ВОПРОС.
> > Существует ли СПЕЦИФИЧЕСКИЙ алгоритм "отсева" бесквадратных чисел, НЕ СВОДЯЩИЙСЯ к тому или иному ОБЩЕМУ алгоритму факторизации.
> > Буду благодарен за ссылки.

> Подозреваю, что специфического алгоритма не придумано. Облазил доступные архивы препринтов и статей на предмет близости с заданным вопросом. Вывод: народ в основном занимается задачей распределения БЧ. Но следует принять во внимание ограниченность моих возможностей (подробно просканировал лишь CiteSeer.IST - http://citeseer.ist.psu.edu/cs; просмотрел еще пару более мелких архивов; не попал на MathSciNet - http://www.ams.org/mathscinet - нет доступа).
> Если не секрет, Михалыч, в каком контексте всплыла эта задача? Ответьте, пожалуйста, почтой (если ответите).
> С уважением, sceptic.

Не секрет.
Вы же знаете, что специально я криптографией не занимаюсь, а тут всплыло одно криптоприложение в качестве побочного продукта.
Суть вот в чем.
Секретный ключ обычно "прячут" в труднорешаемую задачу (дискретный логарифм, факторизация и тп., причем разными способами).
Возникла довольно забавная идея "сокрытия", в которой для взлома необходимо факторизовать числа при априорной информации, что они бесквадратные, причем предварительно их еще надо определить.
То есть, меня фактически интересуют две задачи
1.Поиск бесквадратных чисел - как шустро?
2. Факторизация, если они найдены - есть специфический алгоритм?

Конечно, прямой способ - просто факторизовать. Сразу и отсев и факторизация.
А существуют ли обходной двухэтапный путь?
По мне, так лучше, чтобы его не было...


> Суть вот в чем.
> Секретный ключ обычно "прячут" в труднорешаемую задачу (дискретный логарифм, факторизация и тп., причем разными способами).
> Возникла довольно забавная идея "сокрытия", в которой для взлома необходимо факторизовать числа при априорной информации, что они бесквадратные,

В классической RSA про модуль известно, что он бесквадратный. Тем не менее, исходя из этого, упростить задачу факторизации пока никому не удалось.

> причем предварительно их еще надо определить.
> То есть, меня фактически интересуют две задачи
> 1.Поиск бесквадратных чисел - как шустро?

Как нетрудно заметить, доля бесквадратных чисел больше 1-(Pi^2/6-1) ~= 0.355, т.е., грубо говоря, каждое третье число является бесквадратным. Например, если искать надо надо в каком-то интервале, то даже при наличие эффективной процедуры определения бесквадратности, задача упрощается не более чем в 3 раза.

> 2. Факторизация, если они найдены - есть специфический алгоритм?

Нет. Бесквадратный случай как раз наоборот относят к наиболее сложным для факторизации.

> Конечно, прямой способ - просто факторизовать. Сразу и отсев и факторизация.
> А существуют ли обходной двухэтапный путь?
> По мне, так лучше, чтобы его не было...


> > Суть вот в чем.
> > Секретный ключ обычно "прячут" в труднорешаемую задачу (дискретный логарифм, факторизация и тп., причем разными способами).
> > Возникла довольно забавная идея "сокрытия", в которой для взлома необходимо факторизовать числа при априорной информации, что они бесквадратные,

> В классической RSA про модуль известно, что он бесквадратный. Тем не менее, исходя из этого, упростить задачу факторизации пока никому не удалось.

> > причем предварительно их еще надо определить.
> > То есть, меня фактически интересуют две задачи
> > 1.Поиск бесквадратных чисел - как шустро?

> Как нетрудно заметить, доля бесквадратных чисел больше 1-(Pi^2/6-1) ~= 0.355, т.е., грубо говоря, каждое третье число является бесквадратным. Например, если искать надо надо в каком-то интервале, то даже при наличие эффективной процедуры определения бесквадратности, задача упрощается не более чем в 3 раза.

> > 2. Факторизация, если они найдены - есть специфический алгоритм?

> Нет. Бесквадратный случай как раз наоборот относят к наиболее сложным для факторизации.

> > Конечно, прямой способ - просто факторизовать. Сразу и отсев и факторизация.
> > А существуют ли обходной двухэтапный путь?
> > По мне, так лучше, чтобы его не было...

Есть, над чем подумать.


Уважаемый RElf, не знаете ли Вы о судьбе работы Сергея Степанова по факторизации, анонсированной в 1998 г. (упоминается в интервью В. Ященко - http://www.cryptography.ru/db/msg.html?mid=1161991)? Что-то нигде не видел саму работу. Или она попала в "закрытые источники" ?.


> Уважаемый RElf, не знаете ли Вы о судьбе работы Сергея Степанова по факторизации, анонсированной в 1998 г. (упоминается в интервью В. Ященко - http://www.cryptography.ru/db/msg.html?mid=1161991)?

Первый раз про нее слышу.

> Что-то нигде не видел саму работу. Или она попала в "закрытые источники" ?.

Почему бы не спросить у автора интервью или у самого Ященко? e-mail'ы должны быть указаны на сайты.


можно решить методом комплксного исследования, можно искать методами вероятностно расщетными методами, решение не имеется только при статическом рассмотрении структуры системы(метод Монте Карло в частности), при динамическом(вероятностном) рассмотрении решение найдется неизбежно. Наверное поподробнее попросишь ты, но не институт тебе тут чтобы мат. ан. объяснять и вероятностное моделирование, учи науки...


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100