caxapa.ru :: Для (x*(x+1)/2)>=N не существует взаимно однозначного обратного преобразования.

Рэйлвэй Каген (01.04.2009 13:33, просмотров: 171) ответил Сергей Борщ на Не все ходят на Электроникс, продублирую: надо найти преобразование, обратное y = (x * (x+1) / 2) mod N. N- степень двойки.

Для (x*(x+1)/2)>=N не существует взаимно однозначного обратного преобразования. Вы бы хоть область определения указали, что-ли. Приведённые Вами таблицы - лишь частный случай для x<<N(в смысле "сильно меньше"). Но самое интересное, если (x*(x+1)/2)<N и отрицательные корни не имеют физического смысла в исходной задаче, то x=floor(sqrt(2*y)). p.s.: для справки - отрицательный корень будет (-1)*ceil(sqrt(2*y)). pps: убрал гундёж - невнимательно читал корневой пост.

Ответить

- Я же сказал, что диапазон входных значенией - 0...N-1. На этих значениях преобразование однозначно. И как вы в формуле x=floor(sqrt(2*y)) учли mod N? - Сергей Борщ(01.04.2009 13:30)
  - Просто квадратное уравнение направильно составлено. Надо так: ReAl(697 знак., 01.04.2009 14:08)
    - k=[0,N/2], причем единственное, но от этого не сильно легче. - amusin(01.04.2009 14:52)
      - K<(N-1)/2, а если учесть, что К-целое, то N/2 надо бы исключить. Но это несущественно сократит поиск. - Рэйлвэй Каген(01.04.2009 15:01)
        
        Ну да, про бесконечность - это от разворачивания mod, дальше понятно, что надо накладывать ограничения задачи. Но как-то оно явно не хочет быть симметричным по затратам. - ReAl(01.04.2009 16:17)
        
        Вот еще что придумал: y(x) = (y(x-1) + x) mod N. Поэтому если из y вычитать по модулю N числа 1,2,3,4, то на шаге x получится ноль. То же количество итераций, что и перебором, но вместо умножения x и деления на 2 - вычитание. - Сергей Борщ(02.04.2009 03:22)
        
        Решение найдено. Спасибо коллегам с Электроникса, которые напрягли математиков на форуме НГУ :) Если кому интересно - по ссылке. - Сергей Борщ(02.04.2009 18:39, ссылка)
        
        Развернул рекурсию. Это какой же склад ума надо уметь, чтобы писать рекурсию прямо из головы? Сергей Борщ(387 знак., 04.04.2009 13:04)
        
        Вполне обычный. Мы тут все забыли, как складывать лист бумаги :). А оно вон как выходит -> - Рэйлвэй Каген(04.04.2009 14:45, картинка)
        
        Класс! - Рэйлвэй Каген(03.04.2009 09:03)
  - Да, я уже заметил. А формула работает только в области (x*(x+1)/2)<N, т.е. до первого разрыва. - Рэйлвэй Каген(01.04.2009 13:36)
- Оно есть, просто есть сомнения в существовании аналитической записи - amusin(01.04.2009 09:56)
  - Однакось! 3mod2=1, 5mod2=1, 7mod2=1.. Заверните-ка обратное однозначное преобразование. Пожалуйста. - Рэйлвэй Каген(01.04.2009 10:36)
    - Ваш случай тривиален. Попробуйте найти два икса, при которых формула Сергея даст одинаковый результат. - amusin(01.04.2009 10:37)

Средства и методы разработки