基礎數學 - 有限體

Finite field 有限體:

有限體是進行加減乘除運算都有定義並且滿足特定規則的集合。有限體最常見的例子是當 p 為質數時，

整數對 p 取模，用 表示。例如：質數 7 的有限體 =>

$${ F }_{ 7 }\quad =\quad \{ 0,\quad 1,\quad 2,\quad 3,\quad 4,\quad 5,\quad 6\}$$

在有限體裡，加和減也符合有限體的規範，例如：

$${ F }_{ 7 }\quad \\ 3\quad +\quad 4\quad =\quad 7\quad (mod\quad 7)\\ 1\quad +\quad 2\quad =\quad 3\quad (mod\quad 7)$$

乘法和次方也符合有限體規範：

$${ F }_{ 7 }\quad \\ 3\quad \times \quad 4\quad =\quad 12\quad (mod\quad 7)\\ 1\quad \times \quad 2\quad =\quad 2\quad (mod\quad 7)\\ { 11 }^{ 2 }\quad \quad \quad =\quad 121\quad (mod\quad 7)$$

這裏有一些有趣得特性：

1. 在有限體裡，例如 $F_{31}$， 對於任意的 k，{0k, 1k, 2k, ...... 30k} 的結果會是 {0 ~ 30}
2. 在有限體裡，例如 $F_{p}$， 對於任意的 k， $k^{p - 1}$ 會是 1 (Fermat little theorem)

除法視為乘法的反向

$${ F }_{ 19 }\quad \\ 2\quad \times \quad 4\quad =\quad 8\quad =>\quad 8/4\quad =\quad 2\quad \\ 11\quad \times \quad 11\quad =\quad 7\quad =>\quad 7/11\quad =\quad 11$$

但是 /4, /11 還是不知道怎麼做？

剛剛的特性 2 我們可以拿來用，在特性 2 ，只要 p 是質數，可以套用到任何的 k，因此

我們知道

$$\frac { 1 }{ n } { \quad =\quad n }^{ -1 }$$

，

所以

$${ n }^{ -1 }={ n }^{ -1 }\times 1={ n }^{ -1 }\times { n }^{ p-1 }={ n }^{ p-2 }$$

也就是說，要除一個數，就是乘上這個數的 p-2 次方，就能滿足質數有限體

EX: ${ 17 }^{ -3 }\quad$ prime = 31

${ 17 }^{ -3 }\quad =\quad { ({ 17 }^{ -1 } })^{ -2 }\quad =\quad { ({ 31 }^{ -2 } })^{ -2 }\quad =\quad { { 31 }^{ -4 } }$

定義 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)

由費馬小定理我們知道：

$a^{p - 1} = 1$ (mod p)

所以我們先把次方數取 $(p - 1)$ 的模數，這些次方乘積都是 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)

而有限體裡的除法即是將被除數乘上除數的$(prime - 2)$ 次方