Перейти к содержанию
    

Найти обратное преобразование

Столкнулся с интересным алгоритмом. 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)

Изменено пользователем Сергей Борщ

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

2y = x(x+1) mod 2N

 

пусть на к-м шаге известны k-1 младших бит x

 

Тогда

 

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)

 

Отсюда b есть k-й бит 2y - с(с+1)

 

Пожалуй примерно так.

 

PS Кроме случая k == 0 где всего два варианта младшнго значения бита

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

вроде получается так:

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Щас сумничаю..

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

Ссылу дал от балды, лучше в учебниках поискать

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Щас сумничаю..

 

Аналогично :)

 

Читать про квадратичные вычеты, китайскую теорему об остатках и т. п.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Чето мне подсказывает про поля Галуа
Угу. Насколько я ничего не понимаю, это поле Галуа с определяющим полиномом 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, что то же яйцо, только в профиль.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Я бросил вашу задачку на форум мехмата НГУ (Новосибирск), а именно в раздел " Алгебра, логика, теория чисел и теория алгоритмов"

 

http://www.nsu.ru/phpBB/viewtopic.php?t=19...a7a4057847d2d69

там одно решение предложили, но я не проверял - гляньте

 

+ еще дал задачку ряду друзей с мех-матовским образованием, но у них специализация не та несколько. в общем пока решения быстрого нет :)

 

для себя я прикинул две "проекции" - как мне видится сама эта задача (чисто для понимания)

1) компьютерно-низкоуровневый: при выполнении операций x*(x+1)/2 на 24-битном модуле происходит wrap-around и результат записывается "как есть" - это тот самый y.

2) графический - строим график функции x(x+1)/2, где x - целые в заданном диапазоне. до 2^24 все "как обычно", а дальше мы из ответа начинаем вычитать 2^24 стоолько раз сколько надо чтобы остаток не превышал 2^24. Получится "страшная" пила какая-то. При первом взгляде в Матлабе я подумал, что какая нах тут однозначность, но оказалось что так и есть.

 

повторяю - эти "проекции" я привел только для того чтобы показать как можно образно представить саму задачу. может это на какую-то мысль натолкнет

 

по идее там решается квадратное уравнение, но нужно подобрать параметр под корнем (в дискриминанте), так 1) чтобы корень извлекался 2) чтобы это число было нечетное (т.к. общее решение должно быть целое, а там стоит 1/2)

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Я бросил вашу задачку на форум мехмата НГУ (Новосибирск), а именно в раздел " Алгебра, логика, теория чисел и теория алгоритмов"

 

http://www.nsu.ru/phpBB/viewtopic.php?t=19...a7a4057847d2d69

там одно решение предложили, но я не проверял - гляньте

Приведенный там алгоритм работает! Спасибо! в нем получается в худшем случае всего k - 1 умножений (N=2^k).

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Приведенный там алгоритм работает! Спасибо! в нем получается всего k умножений (N=2^k).

На самом деле Вам Oldring в первом же ответе дал правильный алгоритм

 

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)

 

Отсюда b есть k-й бит 2y - с(с+1)

Чего-то я никак не могу понять связи между этими уравнениями. Я правильно понимаю, что с - это k-1 младших бит x?
с это k-1 уже найденых бит

 

x(x+1) = (a * 2^(k+1) + b * 2^k + c)(a * 2^(k+1) + b * 2^k + c +1)=.....=

= d*2^(k+1) + b*2^k + c(c+1)

где d это сумма коэф. для степеней 2^(k+1) и она нас не интересует тк мы ищем k бит

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Столкнулся с интересным алгоритмом.

 

Позвольте спросить, а где такой алгоритм живет? Ноги откуда растут?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Позвольте спросить, а где такой алгоритм живет? Ноги откуда растут?
В канале связи. Видимо шифрование.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

В канале связи. Видимо шифрование.

 

 

Я так и подумал :rolleyes: Хотя я полный чайник в этих вопросах, но алгоритм показался как раз "по теме" :rolleyes:

Я попросил еще человека с того форума НГУ ответить - на чем базируется решение. Просто "голова умная" у человека (по видимому, всяко не без этого :rolleyes: ) или еще какие-то "методы" есть из соответствующего раздела

 

P.S. Самому разбираться - интересно, но времени нет. Книжки по теории чисел и по абстрактной алгебре есть и много, но все пока никак времени нет

Изменено пользователем mikeT

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

На самом деле Вам Oldring в первом же ответе дал правильный алгоритм

Не, наврал...

неправильный алгоритм у Oldring...

но очень похож на правду, там где-то апшыбка

 

кстати младший бит x определяется однозначно из значения 'y' за пару операций.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

кстати младший бит x определяется однозначно из значения 'y' за пару операций.
угу. За одну. x0 = y & 1;

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
К сожалению, ваш контент содержит запрещённые слова. Пожалуйста, отредактируйте контент, чтобы удалить выделенные ниже слова.
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...