xorのような関数について

概要

今回はxorと似た関数を探してみました。

xorには以下のような性質があります。

f(x,y) = z の場合以下の式すべてが成り立つ
f(y,x) = z
f(x,z) = y
f(y,z) = x

このような特徴があると「暗号文と鍵から平文」がつくれるので大変便利なのです。

eq関数

eq関数は、双方のbitが等しい時に1になるような関数です。
xorとちょうど反対の出力をします。

#xorの真理値表
  0 1
0 0 1
1 1 0
#eqの真理値表
  0 1
0 1 0
1 0 1

これもxorと同様な性質がありました
しかしxorと同様に(2^n)の法の中でしか成り立ちません。

補数の余りを使う関数

任意の法 R を利用できる関数として
補数と割り算の余りを利用する方法がありました。

#Rを法とする
z = (R-x + R-y) mod R
#以下でも同様
z = (-x-y) mod R

これは結構便利そうです。
あとでこれを使った方陣を作ってみます。

方陣の比較

それぞれの関数を使った0から7までの方陣を比較してみました。

方陣の読み方は以下の様な感じ。
ｘとｙの軸を交換しても大丈夫です。

#xorの方陣
  0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 0 3 2 5 4 7 6
2 2 3 0 1 6 7 4 5
3 3 2 1 0 7 6 5 4
4 4 5 6 7 0 1 2 3
5 5 4 7 6 1 0 3 2
6 6 7 4 5 2 3 0 1
7 7 6 5 4 3 2 1 0
#eqの方陣
  0 1 2 3 4 5 6 7
0 7 6 5 4 3 2 1 0
1 6 7 4 5 2 3 0 1
2 5 4 7 6 1 0 3 2
3 4 5 6 7 0 1 2 3
4 3 2 1 0 7 6 5 4
5 2 3 0 1 6 7 4 5
6 1 0 3 2 5 4 7 6
7 0 1 2 3 4 5 6 7
#補数と余りの方陣
  0 1 2 3 4 5 6 7
0 0 7 6 5 4 3 2 1
1 7 6 5 4 3 2 1 0
2 6 5 4 3 2 1 0 7
3 5 4 3 2 1 0 7 6
4 4 3 2 1 0 7 6 5
5 3 2 1 0 7 6 5 4
6 2 1 0 7 6 5 4 3
7 1 0 7 6 5 4 3 2

内容は違うのに同じ性質があるのは不思議ですね。
他にも同じ性質の関数がありそうです。

検証用スクリプト

方陣の描画と検証に使ったスクリプトを置いときます。
他の関数を調査するときもつかえるはずです。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-

charset = u'01234567'
max = len(charset)

print " ",
for x in range(max):
    print charset[x],
print

def f(x,y):
#    z = (x^y)   #xor
#    z = (~(x ^ y) & (max-1)) #eq
    z = (-x-y)%max  #modr
    return z

for x in range(max):
    print charset[x],
    for y in range(max):
        print charset[f(x,y)],
    print

#check
for x in range(max):
    for y in range(max):
        z = f(x,y)
        if (f(y,x) <> z or
            f(x,z) <> y or
            f(y,z) <> x ):
            print "error %s %s" % (charset[x],charset[y])