四則演算(加算、減算、乗算、除算)について閉じている有限体を作るために利用できる道具がモジュロ演算
モジュロ演算：1つの数を別の数で割った余りの数を求めること
(3 – 16) % 12 = 11
(12 + 843) % 60 = 15
(23 + 97) % 60 = 0
pythonのモジュロ演算
print(7 % 3) print(-27 % 13)
$ python3 app.py
1
12
有限体上の加算が閉じていることを確認する必要がある
F19 = {0, 1, 2…18}
F57
prime = 57 print((44+33)%prime) print((9-29)%prime) print((17+42+49)%prime) print((52-30-38)%prime)
### 加算と減算
// 省略
def __add__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot add two numbers in different Fields')
num = (self.num + other.num) % self.prime
return self.__class__(num, self.prime)
def __sub__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot subtract two numbers in different Fields')
num = (self.num - other.num) % self.prime
return self.__class__(num, self.prime)
a = FieldElement(7, 13)
b = FieldElement(12, 13)
c = FieldElement(6, 13)
print(a+b==c)
### 乗算とべき乗
べき乗は乗算を繰り返し
prime = 97 print(95*45*31 % prime) print(17*13*19*44 % prime) print(17**7 * 77**49 % prime)
乗算
def __mul__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot multiply two numbers in different Fields')
num = (self.num * other.num) % self.prime
return self.__class__(num, self.prime)
a = FieldElement(3, 13)
b = FieldElement(12, 13)
c = FieldElement(10, 13)
print(a*b==c)
べき乗
def __pow__(self, exponent): num = (self.num ** exponent) % self.prime return self.__class__(num, self.prime) a = FieldElement(3, 13) b = FieldElement(1, 13) print(a**3==b)
for prime in (7, 11, 17, 31): print([pow(i, prime-1, prime) for i in range(1, prime)])
### 有限体上の除算
prime = 31 print(3*pow(24, prime-2, prime) % prime) print(pow(17, prime-4, prime)) print(pow(4, prime-5, prime)*11 % prime)
def __truediv__(self, other):
if self.prime != other.prime:
raise TypeError('Cannot divide two numbers in different Fields')
num = self.num * pow(other.num, self.prime - 2, self.prime) % self.prime
return self.__class__(num, self.prime)
いきなり難しいな
