|
Найти обратное преобразование, y = (x * (x+1) / 2) mod N |
|
|
|
Mar 31 2009, 13:47
|

Гуру
     
Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095

|
Столкнулся с интересным алгоритмом. 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
--------------------
На любой вопрос даю любой ответ"Write code that is guaranteed to work, not code that doesn’t seem to break" ( C++ FAQ)
|
|
|
|
|
 |
Ответов
|
Apr 1 2009, 20:11
|

Гуру
     
Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095

|
Цитата(Oldring @ Mar 31 2009, 17:18)  x = a * 2^(k+1) + b * 2^k + c, где a = неизвестное целое, b - неизвестный бит, c - известное целое меньшее 2^k
x(x+1) = d*2^(k+1) + b*2^k + c(c+1) Чего-то я никак не могу понять связи между этими уравнениями. Я правильно понимаю, что с - это k-1 младших бит x? Не могли бы вы изложить это более подробно, для особо одаренных? Если можно, то на примере любого числа для N=2^4: Код 0000 0001 0011 0110 1010 1111 0101 1100 0100 1101 0111 0010 1110 1011 1001 1000
--------------------
На любой вопрос даю любой ответ"Write code that is guaranteed to work, not code that doesn’t seem to break" ( C++ FAQ)
|
|
|
|
|
Apr 2 2009, 07:06
|
Частый гость
 
Группа: Свой
Сообщений: 79
Регистрация: 8-04-05
Из: Санк-Петербург
Пользователь №: 3 972

|
вроде получается так:
2*y = x*(x+1) mod 2*N = x*(x+1)mod 2^(k+1), N = 2^k
В общем случае это означает, что:
2*y = x*(x+1) - ЦелаяЧасть[ (x*(x+1))/(2^(k+1)) ] * 2^(k+1);
Обозначим ЦелаяЧасть[ (x*(x+1))/(2^(k+1)) ] = n , n = 0, 1, 2 ...
2*y = x*(x+1) - n*2^(k+1);
x^2 + x - 2*(n*2^k + y);
x = [-1 + sqrt(1 + 8*(n*2^k + y)) ] / 2 (второй корень, где -1 - sqrt() отбрасываем, т.к. интересуют x > 0)
т.о. нахождение х следующее: 1. Ищем такое минимальное n, при котором корень будет целым числом. 2. Считаем х.
Пример N = 2^4 = 16, n_max = 7
x = 0, 1, 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 y = 0, 1, 3, 6, 10, 15, 5, 12, 4, 13, 7, 2, 14, 11, 9, 8
Итак, y = 10, 1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 10)) ] / 2 = [-1 + 9] / 2 = 4
y = 13 1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 13)) ] / 2 = [-1 + sqrt(105) ] / 2; sqrt(105) - не целое 2) n =1, x = [-1 + sqrt(1 + 8*(1*16 + 13)) ] / 2 = [-1 + sqrt(233) ] / 2; sqrt(233) - не целое 3) n =2, x = [-1 + sqrt(1 + 8*(2*16 + 13)) ] / 2 = [-1 + sqrt(361) ] / 2 = [-1 + 19]/2 = 9;
y = 8 1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 8)) ] / 2 = [-1 + sqrt(65) ] / 2; sqrt(65) - не целое 2) n =1, x = [-1 + sqrt(1 + 8*(1*16 + 8)) ] / 2 = [-1 + sqrt(193) ] / 2; sqrt(193) - не целое 3) n =2, x = [-1 + sqrt(1 + 8*(2*16 + 8)) ] / 2 = [-1 + sqrt(321) ] / 2; sqrt(321) - не целое 4) n =3, x = [-1 + sqrt(1 + 8*(3*16 + 8)) ] / 2 = [-1 + sqrt(449) ] / 2; sqrt(449) - не целое 5) n =4, x = [-1 + sqrt(1 + 8*(4*16 + 8)) ] / 2 = [-1 + sqrt(577) ] / 2; sqrt(577) - не целое 6) n =5, x = [-1 + sqrt(1 + 8*(5*16 + 8)) ] / 2 = [-1 + sqrt(705) ] / 2; sqrt(705) - не целое 7) n =6, x = [-1 + sqrt(1 + 8*(6*16 + 8)) ] / 2 = [-1 + sqrt(833) ] / 2; sqrt(833) - не целое 8) n =7, x = [-1 + sqrt(1 + 8*(7*16 + 8)) ] / 2 = [-1 + sqrt(961) ] / 2 = [-1 + 31]/2 = 15
|
|
|
|
Сообщений в этой теме
Сергей Борщ Найти обратное преобразование Mar 31 2009, 13:47 MrYuran Щас сумничаю..
Чето мне подсказывает про поля Галу... Apr 2 2009, 07:17 petrov Цитата(MrYuran @ Apr 2 2009, 10:17) Щас с... Apr 2 2009, 07:48 Сергей Борщ Цитата(MrYuran @ Apr 2 2009, 10:17) Чето ... Apr 2 2009, 09:56  mikeT Я бросил вашу задачку на форум мехмата НГУ (Новоси... Apr 2 2009, 11:26   Сергей Борщ Цитата(mikeT @ Apr 2 2009, 14:26) Я броси... Apr 2 2009, 12:18    singlskv Цитата(Сергей Борщ @ Apr 2 2009, 16:18) П... Apr 2 2009, 12:40     singlskv Цитата(singlskv @ Apr 2 2009, 16:40) На с... Apr 2 2009, 20:08      Сергей Борщ Цитата(singlskv @ Apr 2 2009, 23:08) кста... Apr 3 2009, 05:31       singlskv Цитата(Сергей Борщ @ Apr 3 2009, 09:31) у... Apr 3 2009, 09:12        xemul Цитата(singlskv @ Apr 3 2009, 13:12) не, ... Apr 3 2009, 11:12         singlskv Цитата(xemul @ Apr 3 2009, 15:12) А как з... Apr 3 2009, 14:20        Сергей Борщ Цитата(singlskv @ Apr 3 2009, 12:12) не, ... Apr 3 2009, 11:31         singlskv Цитата(Сергей Борщ @ Apr 3 2009, 15:31) Н... Apr 3 2009, 12:31       Oldring Цитата(Сергей Борщ @ Apr 3 2009, 09:31) у... Apr 9 2009, 08:00        singlskv Цитата(Oldring @ Apr 9 2009, 12:00) Проте... Apr 9 2009, 18:52         Oldring Цитата(singlskv @ Apr 9 2009, 22:52) Я го... Apr 10 2009, 08:16 Rst7 ЦитатаСтолкнулся с интересным алгоритмом.
Позволь... Apr 2 2009, 12:45 Сергей Борщ Цитата(Rst7 @ Apr 2 2009, 15:45) Позвольт... Apr 2 2009, 13:04  mikeT Цитата(Сергей Борщ @ Apr 2 2009, 20:04) В... Apr 2 2009, 13:34 KRS а ведь
X * (X+1) / 2
это формула суммы арифметич... Apr 3 2009, 16:40 singlskv Цитата(KRS @ Apr 3 2009, 20:40) а ведь
... Apr 3 2009, 18:05
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|