Столкнулся с интересным алгоритмом. 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
Найти обратное преобразование, y = (x * (x+1) / 2) mod N
Mar 31 2009, 13:47
