基礎數學 - 有限體
Finite field 有限體:
有限體是進行加減乘除運算都有定義並且滿足特定規則的集合。有限體最常見的例子是當 p 為質數時,
整數對 p 取模,用 表示。例如:質數 7 的有限體 =>
在有限體裡,加和減也符合有限體的規範,例如:
乘法和次方也符合有限體規範:
這裏有一些有趣得特性:
- 在有限體裡,例如 , 對於任意的 k,{0k, 1k, 2k, ...... 30k} 的結果會是 {0 ~ 30}
- 在有限體裡,例如 , 對於任意的 k, 會是 1 (Fermat little theorem)
除法視為乘法的反向
但是 /4, /11 還是不知道怎麼做?
剛剛的特性 2 我們可以拿來用,在特性 2 ,只要 p 是質數,可以套用到任何的 k,因此
我們知道
,
所以
也就是說,要除一個數,就是乘上這個數的 p-2 次方,就能滿足質數有限體
EX: prime = 31
定義 FieldElement
有兩個成員:num, prime,分別代表數值和質數
class FieldElement:
def __init__(self, num, prime):
self.num = num
self.prime = prime
if self.num >= self.prime or self.num < 0:
error = 'Num {} not in field range 0 to {}'.format(
self.num, self.prime-1)
raise RuntimeError(error)
並且複寫加、減、乘、相等、不相等的function
def __eq__(self, other):
if other is None:
return False
return self.num == other.num and self.prime == other.prime
def __ne__(self, other):
if other is None:
return True
return self.num != other.num and self.prime != other.prime
def __repr__(self):
return 'FieldElement_{}({})'.format(self.prime, self.num)
def __add__(self, other):
if self.prime != other.prime:
raise RuntimeError('Primes must be the same')
num = (self.num + other.num) % self.prime
prime = self.prime
return self.__class__(num, prime)
def __sub__(self, other):
if self.prime != other.prime:
raise RuntimeError('Primes must be the same')
num = (self.num - other.num) % self.prime
prime = self.prime
return self.__class__(num, prime)
def __mul__(self, other):
if self.prime != other.prime:
raise RuntimeError('Primes must be the same')
num = (self.num * other.num) % self.prime
prime = self.prime
return self.__class__(num, prime)
以上的方法都是遵守有限體的規則,出來的數值都是取 prime 的模數
另外還要複寫次方:
def __pow__(self, n):
# self.num**(p-1) % p == 1
prime = self.prime
num = pow(self.num, n % (prime-1), prime)
return self.__class__(num, prime)
由費馬小定理我們知道:
(mod p)
所以我們先把次方數取 的模數,這些次方乘積都是 1,所以可以減少計算
除法:
def __truediv__(self, other):
if self.prime != other.prime:
raise RuntimeError('Primes must be the same')
num = (self.num * pow(other.num, self.prime-2, self.prime)) % self.prime
prime = self.prime
return self.__class__(num, prime)
而有限體裡的除法即是將被除數乘上除數的 次方