Симметричный алгоритм Bijective для целых чисел

Нарисуйте большой круг на большом листе бумаги. Запишите все целые числа от 0 до MAXINT по часовой стрелке от вершины круга через равные промежутки. Запишите все целые числа от 0 до MININT против часовой стрелки, снова через равные промежутки. Обратите внимание, что MININT находится рядом с MAXINT в нижней части круга. Теперь сделайте копию этой фигуры на обеих сторонах жесткой карты. Приколите жесткую карточку к кругу через центры обоих. Выберите угол поворота, любой угол, который вам нравится. Теперь у вас есть сопоставление 1-1, которое отвечает некоторым вашим требованиям, но, вероятно, недостаточно неясно. Открепите карту, переверните по диаметру, любому диаметру. Повторяйте эти шаги (в любом порядке), пока не получите желаемое, которое вас устраивает.

Если вы внимательно следите, то запрограммировать это на предпочитаемом вами языке не составит труда.

Для пояснения после комментария: Если вы только поверните карточку против бумаги, тогда метод будет таким же простым, как и вы. Однако, когда вы переворачиваете карту, отображение не эквивалентно (x + m) mod MAXINT для любого m . Например, если вы оставите карту без вращения и перевернете ее по диаметру до 0 (который находится в верхней части циферблата), то 1 будет отображаться на -1, 2 на -2 и так далее. (x + m) mod MAXINT соответствует только поворотам карты.

Я попытаюсь объяснить свое решение этой проблемы на гораздо более простом примере, который затем можно легко расширить для вашего большого.

Скажем, у меня есть 4-битное число. Есть 16 различных значений. Посмотрите на него как на четырехмерный куб:
_{(источник: ams.org )}
.

Каждая вершина представляет одно из этих чисел, каждый бит представляет одно измерение. Итак, это в основном XYZW, где каждое из измерений может иметь только значения 0 или 1. Теперь представьте, что вы используете другой порядок измерений. Например XZYW. Теперь каждая из вершин поменяла свой номер!

Вы можете сделать это для любого количества измерений, просто переставьте эти измерения. Если безопасность вас не беспокоит, это может быть для вас хорошим быстрым решением. С другой стороны, я не знаю, будет ли вывод достаточно "неясным" для ваших нужд, и, конечно же, после выполнения большого объема сопоставления сопоставление может быть отменено (что может быть преимуществом или недостатком, в зависимости от ваших потребностей).

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

• XOR
• симметричная перестановка битов (например, сдвиг 16 бит или преобразование 0-31 в 31 -0, или переверните 0-3 в 3-0, 4-7 в 7-4, ...)
• подробнее?

Можете ли вы использовать случайно сгенерированную таблицу поиска? Пока случайные числа в таблице уникальны, вы получаете биективное отображение. Однако это не симметрично.

Одна таблица поиска размером 16 ГБ для всех 32-битных значений, вероятно, непрактична, но вы можете использовать две отдельные 16-битные таблицы поиска для старшего и младшего слова.

PS: Я думаю, вы можете создать симметричную биективную таблицу поиска, если это важно. Алгоритм будет начинаться с пустой таблицы LUT:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Выберите первый элемент, назначьте ему случайное отображение. Чтобы сделать отображение симметричным, назначьте также обратное:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Выберите следующий номер, снова назначьте случайное отображение, но выберите номер, который еще не был назначен. (т.е. в этом случае не выбирайте 1 или 3). Повторяйте, пока LUT не будет завершен. Это должно генерировать случайное биективное симметричное отображение.

В следующем документе дается 4 или 5 примеров сопоставления, дающих вам функции, а не построение сопоставленных наборов: www.cs.auckland.ac.nz/~john-rugis/pdf/ BijectiveMapping.pdf

Вот моя простая идея: Вы можете перемещать биты числа, как предложил ПетерК, но вы можете иметь различную перестановку битов для каждого числа и при этом иметь возможность его расшифровать.

Шифр ​​выглядит так: Считайте входной номер массивом битов I [0..31] , а выходным - O [0..31] . Подготовьте массив K [0..63] из 64 случайно сгенерированных чисел. Это будет ваш ключ. Возьмите бит входного числа из позиции, определяемой первым случайным числом ( I [K [0] mod 32] ), и поместите его в начало вашего результата ( O [0] ]). Теперь, чтобы решить, какой бит разместить в O [1] , используйте ранее использованный бит. Если он равен 0, используйте K [1], чтобы сгенерировать позицию в I , из которой нужно брать, это 1, используйте K [2] (что просто означает пропуск одного случайного числа).

Теперь это не сработает, так как вы можете взять один и тот же бит дважды. Чтобы этого избежать, меняйте нумерацию битов после каждой итерации, опуская используемые биты. Чтобы сгенерировать позицию, из которой нужно взять O [1] , используйте I [K [p] mod 31] , где p равно 1 или 2, в зависимости от бита O [0] , так как остался 31 бит, пронумерованный от 0 до 30.

Чтобы проиллюстрировать это, я приведу пример:

У нас есть 4-битное число и 8 случайных чисел: 25, 5, 28, 19, 14, 20, 0, 18.

I: 0111    O: ____
    _

25 mod 4 = 1, поэтому мы возьмем бит, позиция которого равна 1 (считая от 0)

I: 0_11    O: 1___
     _

Мы только что взяли бит значения 1, поэтому мы пропускаем одно случайное число и используем 28. Осталось 3 бита, поэтому для подсчета позиции мы берем 28 mod 3 = 1.Берем первый (считая от 0) из оставшихся бит:

I: 0__1    O: 11__
   _

Опять пропускаем одно число и берем 14. 14 mod 2 = 0, поэтому берем 0-й бит:

I: ___1    O: 110_
      _

Теперь это не имеет значения, но предыдущий бит был 0, поэтому мы берем 20. 20 mod 1 = 0:

I: ____    O: 1101

Вот и все.

Расшифровать такое число несложно, нужно проделать то же самое. Позиция, в которую следует поместить первый бит кода, известна из ключа, следующие позиции определяются ранее вставленными битами.

Очевидно, что у этого есть все недостатки всего, что просто перемещает биты (например, 0 становится 0, а MAXINT становится MAXINT), но кажется труднее найти, как кто-то зашифровал число, не зная ключа, который должен быть в секрете.

Возьмите число, умножьте на 9, обратные цифры, разделите на 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

Должно быть достаточно непонятно!!!

Edit : it is not a bijection for 0 ending integer

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

You can always add a specific rule like : Берем число, делим на 10 x раз, умножаем на 9, обратные цифры, делим на 9, умножаем на 10^x.

И так

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t это работает!

Edit 2 : Для большей непристойности можно прибавить произвольное число и вычесть в конце.

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Если вы не хотите использовать правильные криптографические алгоритмы (возможно, по причинам производительности и сложности), вы можете вместо этого использовать более простой шифр, такой как шифр Vigenère. Этот шифр был фактически описан как le chiffre indéchiffrable (по-французски «нерушимый шифр»).

Вот простая реализация C#, которая смещает значения на основе соответствующего значения ключа:

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

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

Разделите число на два (16 старших и 16 младших разрядов) и рассматривайте биты в двух 16-битных результатах как карты в двух колодах. Перемешайте колоды, перекладывая одну в другую.

Таким образом, если ваше исходное число b31,b30,...,b1,b0, то в итоге вы получите b15,b31,b14,b30,...,b1,b17,b0,b16. Это быстрое и быстрое решение, как и обратное.

Если посмотреть на десятичное представление результатов, то серия выглядит довольно неясно.

Вы можете вручную отобразить 0 -> maxvalue и maxvalue -> 0, чтобы избежать их отображения на себя.