Интересное (на мой взгляд) свойство ХОR

О некотором интересном свойстве операции XOR.
Хоть и не формат. Но, мне показалось это интересным.
Этот пост по мотивам статьи на ХАБР — Практика применения XOR в программировании.
Так вот, даны таблицы
1

и, нужно по известным ячейкам восстановить значения всех остальных ячеек. Значения двоичные, то есть, нолики и единички. Вторая таблица, с заполненной диагональю, восстанавливается в точно такую же таблицу как и первая.
Вот табличка попроще

2
В общем нужно решить эту задачку. Решение, естественно, есть. То есть нужно найти способ создания такой таблицы. Которая удовлетворяла бы свойствам частично описанным ниже.
По самой таблице
  • Заполнение таблицы происходит с помощью одного свойства операции XOR. Для
    первоначального полного заполнения таблицы нужно знать только одну из строк. В самом простом случае первую строку.
  • Каждая девятая строка, если продолжить заполнение, будет повторять первую строку от начала заполнения. То есть операция периодична(это уж слишком большая подсказка на мой взгляд, ну да ладно).
  • Последние четыре элемента пятой строки являются инверсией первых четырёх элементов пятой строки, если только все эти элементы не нулевые
  • В таблице нет ни одной одинаковой строки если первые четыре столбца ненулевые.
  • Столбцы целиком могут содержать только нули в левой части таблицы. Это произойдёт в случае если первые несколько элементов первой строки будут равны нулю.
  • Ни одной строки не может быть полностью нулевой — в этом случае вся таблица должна быть заполнена ноликами.
  • Если первый элемент первой строки равен единице то весь первый столбец будет состоять из единиц. Это свойство не распространяется на другие столбцы
  • Каждую из таблиц можно заполнить одним единственным образом.
  • Все строки этих таблиц строго связаны между собой одним единственным способом.
Зная этот способ таблицу можно полностью восстановить зная последний столбец. Так же таблицу можно восстановить зная частично столбцы — но опять же столбцы должны иметь номера и длину равные степени двойки, и при этом не должны совпадать по номеру столбца в таблице между собой.
Ещё таблицу можно восстановить зная диагональные элементы — имеется ввиду только диагональ которая идёт от левого верхнего угла к правому нижнему.
Если известна хотя бы частично какая нибудь часть столбцов слева(сохраняя при этом длину и номер столбца равную степени двойки) и при этом известна частичная диагональ(которая расположена правее частично известного столбца) идущая снизу-слева наверх (как в первой таблице) то восстановление возможно тоже.
И при этом таблица восстанавливается в одну единственно возможную.
Приведу примеры выбора элементов в таблице, зная которые, можно полностью восстановить, единственным образом, исходную таблицу. Используя только лишь свойства XOR.
Можно выбрать «главную» диагональ:

можно выбрать частично столбец и частичную диагональ таким образом:

можно выбрать частичные столбцы:

можно выбрать элементы последнего столбца:

можно выбрать частичный столбец и частичную диагональ таким образом:

и, можно выбрать частичные диагонали таким образом:


Во всех этих случаях исходную таблицу можно восстановить.
Для тех кто не ходил по ссылке вначале поста, речь идёт о свойствах операции XOR.
ПС. Возможно для кого-то это покажется слишком простым «велосипедом» – просьба не раскрывать решения сразу.
Если данная тема всё же вызовет интерес, то, позже, дополню пост описанием. Практического применения этого свойства, кроме шифрования, я пока что не вижу. Но, чёрт возьми :), это свойство XOR для меня оказалось очень интересным.
И, что ещё интереснее, описания этого свойства XOR я нигде не встречал. Может быть шифровальщикам и «генераторщикам» случайных чисел оно и известно.
  • +1
  • 29 октября 2015, 12:12
  • worker

Комментарии (35)

RSS свернуть / развернуть
Некорректно поставленную задачу решить практически невозможно.
+3
Задача, на самом то деле поставлена правильно. Просто нужно знать об одном свойстве операции ХОR. И решение даже не простое, а очень простое. Я бы даже сказал что сверхпростое.
-1
Задача поставлена некорректно потому что ничего не сказано про свойства талицы. Это таблица истинности? Там должна соблюдаться какая-то контрольная сумма? Что-то ещё? Если это просто «таблица», без уточнений, как у вас в посте, то ей можно заполнить произвольным образом и это будет правильный ответ. Нет, ну а что? Таблица? Таблица! Ответ удовлетворяет условиям задачи (в вашей постановке).
+1
Ниже я дал одну подсказку. Каждую из таблиц можно заполнить одним единственным образом.
Все строки этих таблиц строго связаны между собой одним единственным способом.
Зная этот способ таблицу можно полностью восстановить зная любой столбец с номером равным степени двойки, и количеством элементов в этом столбце равным этой степени двойки. Так же таблицу можно восстановить зная частично столбцы — но опять же столбцы должны иметь номера и длину равные степени двойки, и при этом не должны совпадать по номеру столбца в таблице между собой.
Ещё таблицу можно восстановить зная диагональные элементы — имеется ввиду только диагональ которая идёт от левого верхнего угла к правому нижнему.
Если известна хотя бы частично какая нибудь часть столбцов слева(сохраняя при этом длину и номер столбца равную степени двойки) и при этом известна частичная диагональ идущая снизу-слева наверх (как в первой таблице) то восстановление возможно тоже.
И при этом таблица восстанавливается в одну единственно возможную.

Добавлю сейчас этот текст в сам пост.
0
Зная этот способ таблицу можно полностью восстановить зная любой столбец с номером равным степени двойки, и количеством элементов в этом столбце равным этой степени двойки.
Это предложение нужно читать как
Зная этот способ таблицу можно полностью восстановить зная последний столбец.

Поторопился, не сделал вычитку, перед нажатием кнопки отправить.
0
Вам наверное очень сложно сдавать экзамены и устраиваться на работу, если и в жизни таким вот способом излагаете свои мысли)
Задача, на самом деле не поставлена никак, от слова вообще)
У вас нет никаких требований какие законы должны соблюдаться для таблицы. Так что, как уже было сказано, ее можно заполнить рандомно и это будет верно, потому что удовлетворяет условие задачи, условие то ведь отсутствует, а значит любое решение будет верным :).
+2
Да нет, большинство экзаменов, в свое время, у меня сдавались автоматом. Да и с устройством на работу проблем не было.
А с задачей — видимо я на самом деле её неудачно описал. Суть, получается, в том что нужно нужно найти способ создания такой таблицы при котором она удовлетворяет всем описанным мной свойствам.
0
То есть зная способ создания такой таблицы. И, зная только частично некоторые элементы этой таблицы, выбранные определённым образом(способы выбора элементов я попытался описать в посте). Можно восстановить исходную таблицу.
По самой таблице ещё можно сказать что нет ни одной одинаковой строки.
Ну и ещё раз повторю что используется операция XOR.
0
Ещё по таблице — ни одна строка не может состоять только из нулей.
Несколько первых столбцов могут быть целиком нулевыми.
При этом если первые четыре или больше столбцов целиком равны нулю то строки всё же повторяются с определённым шагом.
0
это подсказки, а не условия.
+1
Ну, так, я вот почему то подумал что задачка очень простая, оказалось что не так. Поэтому и написал условия-подсказки.
А что — решил задачку?
0
вопрос не в сложности задачи, а в непонятности. что вижу я «попробуйте заполнить клеточки и угадать что я имел в виду». суть задачи я вроде понял, только сама задача поставлена неверно. подобные задачи (судоку, магические квадраты) строятся на известных правилах и входных данных. в данном случае мы имеем только входные данные.
0
Самая главная подсказка это операция XOR.
0
Ну то есть, это как если человеку, который никогда не видел судоку, показать судоку со словавми: «в этой таблице должны быть цифры от 1 до 9, заполни». И всё, без дополнительных условий.
+3
Мне эта задачка показалась очень простой. Дополнительные свойства таблицы я добавил в пост.
0
Дам подсказку — используется свойство периодичности операции XOR.
-1
Какая-то головоломка для пенсионеров. Не могу придумать ни одного практического использования.

Автор, возьми таблицу поменьше (4х4) и пошагово обьясни как работает этот чудо-алгоритм.
0
Объяснение будет в следующем посте. Сейчас пишу его.
Насчёт практического применения — возможно для шифрования или генерирования случайных чисел. Другого применения я тоже, пока что, не вижу.
Для меня оказались интересными многие свойства этого алгоритма, сами по себе.
0
ну зашифруешь, замусоришь мусорным кодом, потратишь время…
а потом кто просто напишет…
begin
 s:=filename;
 z:=0;
 for i:=1 to length(s) do z:=z + ord(s[i]);
 m:=$572A+z; //маска
 j:=0;
 while j<$280 do
  begin
   m:= m + $58A3;
   e:= data.wo[j] xor m;
   r:= Rol_5(e);//e shl 5;
   m:= m - $58A3;
   a:= r xor m;
   data.wo[j]:= Rol_1(a);
   m:= (m + $9321 +z + $58A3) and $FFFF;
   inc(j);
  end;
end;

и все труды коллектива шифровальщиков будут напрасны
0
так вот с помощью каких свойств бабушкин свой архиватор написал xD
0
  • avatar
  • xar
  • 29 октября 2015, 16:16
Бабушкин, насколько я знаю, свой архиватор писал с помощью только одного деления двух чисел, каждое из которых должно быть длиной по несколько килобайт.
Ему бы про свойства чисел почитать перед этим. И теорему Ферма заодно доказать. :)
0
вообще неважно. это был сарказм на задачу восстановления исходной таблицы по одному столбцу.
0
Есть бесконечное множество таблиц, которые можно восттановить по одному столбцу (если известен алгоритм заполнения оной таблицы). Но вот с плотностью информации/этропией у них всё печально :).
0
У энтропии Шеннона есть дыра. Если взять 256 не повторяющихся восьмибитных чисел, то энтропия Шеннона говорит что сжатие невозможно. Но это не так. Я не говорю про случай когда все числа идут строго по возростанию — от 0 до 255. Или же строго по убыванию.Числа могут располагаться в произвольном порядке. Главное чтобы ни одно число не повторялось.
Если известно условие что в блоке из 256 восьмибитных чисел ни одно из них неповторяется, то, считав первые 128 чисел, вторые 128 можно будет закодировать семибитными числами.
В практическом плане это ничего не даёт, так как, число таких 256 байтных блоков с неповторяющимися числами составляет примерно 2 в степени минус 100 процента, от общего количества 256 байтных чисел.
Но, тем не менее «дыра» в формуле Шеннона есть.
0
Главное чтобы ни одно число не повторялось.
Это не дыра, а непонимание теории информации. Каждое такое условие уменьшает этропию.
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах, но если узнать что число всегда состоит из 255 нулей и одной единицы на случайной позиции, то я смогу сжать это число на 256-log2(256) бит! ДЫРА!!!!11111
2 в степени минус 100 процента
Опишите детальнее свою математику, есть подозрение что она некоим образом отличается от земной.
0
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах
Теория Шеннона будет так гласить только в случае если число единичных и нулевых бит равно
друг другу, поэтому контрпример не подходит.

Опишите детальнее свою математику, есть подозрение что она некоим образом отличается от земной.
А тут очень просто всё — 256 байт неповторяющихся чисел даёт нам 256 факториал комбинаций из них. Общее количество чисел равно 256 в 256-ой степени. Первое разделить на второё и умножить на сто — получим проценты. Вроде как, самая что ни на есть, обычная математика.
0
Теория Шеннона будет так гласить только в случае если число единичных и нулевых бит равно друг другу
Нет. Единичное число несжимаемо вообще. Вот если у нас есть канал где бесконечное время передаются 256-битные числа, тогда теория применима. Контрпример я привёл чтобы заткнуть мнимую «дыру».

256!/256^256 != 2^-100.
0
Единичное число несжимаемо вообще.
Разговор шёл о 256 битах, а не о единичном числе/бите.
И ты сам привёл формулу Шеннона
256-log2(256)
И в ней нет противоречия самому Шеннону. :)

256!/256^256 != 2^-100.
И? Где тут неземная математика? :)
0
Единственно что непонятно в формуле
256!/256^256 != 2^-100.
Откуда там два факториала?
0
И, таки можно было бы сказать да, но всё же нет :)
Вот еще идея из того же разряда: у нас есть 256 битное число. Теория Шеннона гласит что записать его можно только на 256 битах, но если узнать что число всегда состоит из 255 нулей и одной единицы на случайной позиции, то я смогу сжать это число на 256-log2(256) бит! ДЫРА!!!!11111
в этом случае выражение энтропии по Шеннону будет выглядеть так
-255*log2(255/256) — 1*log2(1/256) = 255*0.0056466 + 1*8 = 1,439883 + 8 = 8,439883 бит для кодирования всех 256 бит.
0
Второй! это не факториал, это знак неравенства…
в этом случае выражение энтропии по Шеннону будет выглядеть так
А теперь посчитайте энтропию для 256 чисел, зная что множество является размещением из 256, и каждое записанное число уменьшает количество оставшихся вариантов. Точно так же как каждый вытянутый шар из урны увеличивает наши шансы на угадывание (и уменьшает энтропию) остальных.

Я очень неровно отношусь к людям, находящим «дыры» в теории Шеннона, ОТО, и исправляющих ошибки в числе Пи. Пожалуйста, воздержитесь от подобных заявлений, а лучше допишите статью о чудодейственном XOR. Мне действительно интересно как.
0
Второй! это не факториал, это знак неравенства…
Так ведь я и написал что примерно равно 2^-100. Числа с такими порядками мало отличаются от нуля, для их практической пользы.

А теперь посчитайте энтропию для 256 чисел, зная что множество является размещением из 256, и каждое записанное число уменьшает количество оставшихся вариантов. Точно так же как каждый вытянутый шар из урны увеличивает наши шансы на угадывание (и уменьшает энтропию) остальных.
С этим согласен, только вот формуле Шеннона это никак не учтено.
В теории сложности Колмогорова уже есть учёт этих вещей. Только вот её я пролистал по диагонали.

лучше допишите статью о чудодейственном XOR. Мне действительно интересно как.
Пишу.
0
Так ведь я и написал что примерно равно 2^-100.
Даже примерно не равно. Поэтому я так удивился.
В формуле Шеннона всё учтено. Надо только применять её правильно, включая все параметры.

Оставим дискуссию до второй части.
0
Даже примерно не равно. Поэтому я так удивился.
256! = 8,5781777534284265411908227168123e+506
256^256 = 3,231700607131100730071487668867e+616

деление первого числа на второе даёт на степень приблизительно равную минус 100.

А в остальном, да, во второй части продолжим, если всё ещё будет интерес.
0
Я очень неровно отношусь к людям, находящим «дыры» в теории Шеннона, ОТО, и исправляющих ошибки в числе Пи. Пожалуйста, воздержитесь от подобных заявлений
Наш местный «прохфессор» поставил на место зарвавшегося неуча-энтузиаста :DDD
-3
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.