Найти обратное преобразование, y = (x * (x+1) / 2) mod N Опции

[Сергей Борщ]

Столкнулся с интересным алгоритмом. y = (x * (x+1) / 2 ) mod N (N - степень двойки) дает взаимно однозначное преобразование x[0...N-1] в y[0...N-1]. Собственно задача: имея y найти х. Табличный метод не предлагать - у меня x имеет 24 бита.
На всякий случай привожу таблицу для N = 2^8:

Код

y(x):
00 01 03 06 0A 0F 15 1C 24 2D 37 42 4E 5B 69 78
88 99 AB BE D2 E7 FD 14 2C 45 5F 7A 96 B3 D1 F0
10 31 53 76 9A BF E5 0C 34 5D 87 B2 DE 0B 39 68
98 C9 FB 2E 62 97 CD 04 3C 75 AF EA 26 63 A1 E0
20 61 A3 E6 2A 6F B5 FC 44 8D D7 22 6E BB 09 58
A8 F9 4B 9E F2 47 9D F4 4C A5 FF 5A B6 13 71 D0
30 91 F3 56 BA 1F 85 EC 54 BD 27 92 FE 6B D9 48
B8 29 9B 0E 82 F7 6D E4 5C D5 4F CA 46 C3 41 C0
40 C1 43 C6 4A CF 55 DC 64 ED 77 02 8E 1B A9 38
C8 59 EB 7E 12 A7 3D D4 6C 05 9F 3A D6 73 11 B0
50 F1 93 36 DA 7F 25 CC 74 1D C7 72 1E CB 79 28
D8 89 3B EE A2 57 0D C4 7C 35 EF AA 66 23 E1 A0
60 21 E3 A6 6A 2F F5 BC 84 4D 17 E2 AE 7B 49 18
E8 B9 8B 5E 32 07 DD B4 8C 65 3F 1A F6 D3 B1 90
70 51 33 16 FA DF C5 AC 94 7D 67 52 3E 2B 19 08
F8 E9 DB CE C2 B7 AD A4 9C 95 8F 8A 86 83 81 80

x(y):
00 01 8B 02 37 99 03 D5 EF 4E 04 2D 27 B6 73 05
20 9E 94 5D 17 06 E3 CA CF EE DB 8D 07 A9 AC 65
40 C1 4B BD 08 A6 3C 6A AF 71 44 ED 18 09 33 C5
60 21 D4 E2 28 B9 A3 0A 8F 2E 9B B2 38 96 EC DA
80 7E 0B 82 48 19 7C 55 6F CE 84 52 58 C9 0C 7A
A0 E1 EB 22 68 86 63 B5 4F 91 5B 0D 78 29 D3 1A
C0 41 34 3D 88 D9 BC EA 2F 0E C4 6D 98 76 4C 45
E0 5E AB 9D A8 39 23 8A 0F AE 1B CD B8 E9 93 A5
FF FE 74 FD C8 66 FC 2A 10 B1 FB D2 D8 49 8C FA
DF 61 6B A2 E8 F9 1C 35 30 11 24 72 F8 56 53 9A
BF 3E B4 42 F7 59 C3 95 50 8E BB 12 E7 F6 CC 3A
9F DE 2B 1D D7 46 5C F5 70 D1 64 4D C7 69 13 25
7F 81 F4 7D B7 E6 83 AA 90 31 7B AD A7 36 F3 85
5F 1E 14 DD 97 79 9C 4A B0 6E A4 F2 87 D6 2C E5
3F BE CB C2 77 26 43 15 D0 F1 3B 92 67 89 B3 BA
1F A1 54 62 57 C6 DC 75 F0 51 E4 32 47 16 6C 5A

Возможно, это какое-то общеизвестное преобразование, но моих знаний не хватает.

P.S. добавил таблицу x(y)

Сообщение отредактировал Сергей Борщ - Mar 31 2009, 19:03

[MrYuran]

Щас сумничаю..
Чето мне подсказывает про поля Галуа
Ссылу дал от балды, лучше в учебниках поискать

[Сергей Борщ]

Чето мне подсказывает про поля Галуа

Угу. Насколько я ничего не понимаю, это поле Галуа с определяющим полиномом X^2+X+1. X - к-кортеж (N=2^k). Фактически это задача нахождения индекса элемента в поле. 

1. Ищем такое минимальное n, при котором корень будет целым числом.

Алгоритм в целом правильный. Но для x=2^24-1 придется искать корень 2^24-1 число раз. Перебором будет проще и быстрее.

ReAl на сахаре попытался решить уравнение x = [-1 + sqrt(1 + 8*(n*2^k + y)) ] / 2 аналитически. Очевидно, что подкоренное выражение должно быть квадратом. Поскольку присутствует деление на 2 и -1, то квадратом нечетного числа, или числом вида (2m + 1)^2. Подстановка под корень этого выражения дает тождество x=m. Попытка решения уравнения 1+8(n*2^k + y) = (2m+1)^2 приводит к исходному уравнению:

1+8(n*2^k + y) = 4m^2+4m+1
8(n*2^k + y) = 4m^2+4m
2(n*2^k + y) = m^2+m
2(n*2^k + y) = m(m+1)
n*2^k + y = m(m+1)/2
Круг замкнулся.

Вчера мне пришел в голову более простой алгоритм: элементы этого поля представляют собой суммы членов арифметической прогрессии. Т.е. x[n] = (x[n-1]+x) mod 2^k. То есть вычитая из y по модулю 2^k числа x = 1,2,3... до получения 0 мы находим х за максимум 2^k - 1 вычитаний. Ну или восстанавливая последовательность x суммированием последовательности 1,2,3... по модулю 2^k до совпадения результата с y, что то же яйцо, только в профиль.

Но должен же быть какой-то алгоритм побитового восстановления, вроде деления полиномов!