НГУ

Форумы НГУ
Текущее время: Ср окт 23, 2019 9:08 pm

Сообщения без ответов | Активные темы


Список форумов » Образовательные форумы » Алгебра, логика, теория чисел и теория алгоритмов

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  Страница 1 из 1
  [ Сообщений: 7 ] 
  Версия для печати Пред. тема | След. тема 
Автор Сообщение
mikeT
 Заголовок сообщения: небольшая задачка
СообщениеДобавлено: Чт апр 02, 2009 12:52 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт апр 02, 2009 12:33 pm
Сообщения: 3
Откуда: Миха
Имеется алгоритм, заданный соотношением: 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 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
Попробуйте такой алгоритм (я даже не знаю, работает ли он)

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 12:33 pm
Сообщения: 3
Откуда: Миха
Цитата:
Попробуйте такой алгоритм (я даже не знаю, работает ли он)


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

Не могли бы вы написать какой "аппарат" вы использовали при решении? Просто "головой подумали" :) Или это какие-то "типовые" (относительно типовые) методы из соответствующего раздела?
Вернуться к началу
 Профиль  
 
Гост_Я
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 02, 2009 8:42 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Ср июн 15, 2005 4:00 pm
Сообщения: 1155
mikeT писал(а):
Не могли бы вы написать какой "аппарат" вы использовали при решении?
Аппаратов у меня нет, просто догадался.
Вернуться к началу
 Профиль  
 
mikeT
 Заголовок сообщения:
СообщениеДобавлено: Чт апр 02, 2009 8:45 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт апр 02, 2009 12:33 pm
Сообщения: 3
Откуда: Миха
Цитата:
Аппаратов у меня нет, просто догадался.


:)

в мемориз
Вернуться к началу
 Профиль  
 
guest
 Заголовок сообщения: Re: небольшая задачка
СообщениеДобавлено: Пт апр 24, 2009 3:00 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Сб мар 15, 2003 1:40 am
Сообщения: 163
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
 Заголовок сообщения: Re: небольшая задачка
СообщениеДобавлено: Ср апр 29, 2009 10:48 am 
Не в сети
Частый гость

Зарегистрирован: Вт июл 26, 2005 4:27 pm
Сообщения: 31
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
  [ Сообщений: 7 ] 

Список форумов » Образовательные форумы » Алгебра, логика, теория чисел и теория алгоритмов

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB