НГУ
http://forum.nsu.ru/

небольшая задачка
http://forum.nsu.ru/viewtopic.php?f=24&t=19819
Страница 1 из 1

Автор:  mikeT [ Чт апр 02, 2009 12:52 pm ]
Заголовок сообщения:  небольшая задачка

Имеется алгоритм, заданный соотношением: y = (x * (x+1) / 2 ) mod N (N - степень двойки). Это взаимно однозначное преобразование x[0...N-1] в y[0...N-1] (проверяли тупо на компьютере). Собственно задача: имея y найти х. Конкретно в задаче N = 2^24.
Буду благодарен, если грамотные в этом вопросе люди объяснят:
1) можно ли вообще написать «простую» формулу для x=f(y)
2) если нет, то каков оптимальный алгоритм поиска x по известному y
3) какую-нибудь общую информацию по теории – на уровне ссылок на разделы и книжки

Автор:  Гост_Я [ Чт апр 02, 2009 5:24 pm ]
Заголовок сообщения: 

Попробуйте такой алгоритм (я даже не знаю, работает ли он)

function F(y, k)
if y<2 then {F=y, exit}
yy=y mod 2^{k-1}; xx=F(yy, k-1)
if y=xx(xx+1)/2 mod 2^k then F=xx else F=2^k-1-xx
end of F

Автор:  mikeT [ Чт апр 02, 2009 8:27 pm ]
Заголовок сообщения: 

Цитата:
Попробуйте такой алгоритм (я даже не знаю, работает ли он)


Спасибо большое. Мне сказали что работает! :)

Не могли бы вы написать какой "аппарат" вы использовали при решении? Просто "головой подумали" :) Или это какие-то "типовые" (относительно типовые) методы из соответствующего раздела?

Автор:  Гост_Я [ Чт апр 02, 2009 8:42 pm ]
Заголовок сообщения: 

mikeT писал(а):
Не могли бы вы написать какой "аппарат" вы использовали при решении?
Аппаратов у меня нет, просто догадался.

Автор:  mikeT [ Чт апр 02, 2009 8:45 pm ]
Заголовок сообщения: 

Цитата:
Аппаратов у меня нет, просто догадался.


:)

в мемориз

Автор:  guest [ Пт апр 24, 2009 3:00 pm ]
Заголовок сообщения:  Re: небольшая задачка

mikeT писал(а):
Имеется алгоритм, заданный соотношением: y = (x * (x+1) / 2 ) mod N (N - степень двойки). Это взаимно однозначное преобразование x[0...N-1] в y[0...N-1] (проверяли тупо на компьютере). Собственно задача: имея y найти х. Конкретно в задаче N = 2^24.
Буду благодарен, если грамотные в этом вопросе люди объяснят:
1) можно ли вообще написать &laquo;простую&raquo; формулу для x=f(y)
2) если нет, то каков оптимальный алгоритм поиска x по известному y
3) какую-нибудь общую информацию по теории – на уровне ссылок на разделы и книжки

Бухштаб. Теория чисел. Глава 21

Автор:  maxal [ Ср апр 29, 2009 10:48 am ]
Заголовок сообщения:  Re: небольшая задачка

mikeT писал(а):
y = (x * (x+1) / 2 ) mod N (N - степень двойки). Это взаимно однозначное преобразование x[0...N-1] в y[0...N-1] (проверяли тупо на компьютере). Собственно задача: имея y найти х.

Соотношение y = (x * (x+1) / 2 ) (mod N) переписывается в виде:
8y+1 = (2x+1)^2 (mod 8N)
Таким образом, вычисление x по заданному y сводится к вычислению квадратного корня по модулю 8N. Для степени 2-ки это легко осуществляется с помощью леммы Гензеля (что по сути и предложил Гост_Я):
http://en.wikipedia.org/wiki/Hensel%27s_lemma

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/