基礎數學 - 有限體

Finite field 有限體:

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

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

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

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

這裏有一些有趣得特性:

  1. 在有限體裡,例如 , 對於任意的 k,{0k, 1k, 2k, ...... 30k} 的結果會是 {0 ~ 30}
  2. 在有限體裡,例如 , 對於任意的 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)

而有限體裡的除法即是將被除數乘上除數的 次方

results matching ""

    No results matching ""