Finite Field

Residue Tuple

多個餘數,併成一個餘數組。餘數有m種數值,餘數組有m₀×m₁×m₂×...種數組。

(a₀ (mod m₀), a₁ (mod m₁), a₂ (mod m₂))

模數相同時,mod符號可以精簡成一個,寫在式子後面。

(a₀, a₁, a₂) (mod m)

中國餘數定理:模數兩兩互質的情況下,餘數組等同餘數。

(a₀ (mod m₀), a₁ (mod m₁), a₂ (mod m₂))  ⟷  a (mod m₀m₁m₂)
when mᵢ⊥mⱼ

有限體:模數是相同質數的情況下,嘗試讓餘數組宛如餘數。

(a₀, a₁, a₂) (mod p)  ⟷  a (mod p³)

方法是運用餘數多項式,多數併成一數。

(a₀, a₁, a₂) (mod p)  ⟷  a₀x⁰ + a₁x¹ + a₂x² (mod p) (mod p³)

餘數多項式a₀x⁰ + a₁x¹ + a₂x² (mod p)視作一物,此物宛如餘數,模數是p³。

Finite Field(Galois Field)

餘數系統,對象是整數。通常令模數為質數,讓每個數字都有倒數,以便建立加減乘除四則運算。

5 ≡ 2 (mod 3)
4 + 5 ≡ 0 (mod 3)
4 × 5 ≡ 2 (mod 3)

餘數系統,對象是整數多項式。通常令模數為質式,讓每個多項式都有倒數,以便建立加減乘除四則運算。

x³ ≡ -x - 1 (mod x³ + x + 1)
x² + (x² + 1) ≡ 2x² + 1 (mod x³ + x + 1)
x² × (x² + 1) ≡ -x (mod x³ + x + 1)

餘數系統,對象是餘數多項式。通常令模數為質式暨質數,讓每個餘數多項式都有倒數,以便建立加減乘除四則運算。

x³ (mod 2)x + 1 (mod 2) (mod x³ + x + 1 (mod 2))
x² (mod 2) + x² + 1 (mod 2)1 (mod 2) (mod x³ + x + 1 (mod 2))
x² (mod 2) × x² + 1 (mod 2)x (mod 2) (mod x³ + x + 1 (mod 2))

餘數系統,對象是餘數多項式,簡易的理解方式:

一、模數是質式(n次多項式):次方範圍是0到n-1。

二、模數是質數p:係數範圍是0到p-1。

標記方式是GF(pⁿ),另以文字說明質式為何。

GF(2³), irreducible polynomial is x³ + x + 1 (習慣省略mod)
x³ ≡ x + 1
x² + (x² + 1) ≡ 1
x² × (x² + 1) ≡ x

「模數是質式暨質數」暨加減乘除法,數學家稱作「有限體」。

餘數多項式改寫成數字

餘數多項式得簡化成數字:係數變位數、模數變底數。

x (mod 2)          --->  10₍₂₎ = 2₍₁₀₎
x² + 1 (mod 2)     ---> 101₍₂₎ = 5₍₁₀₎
x² + x + 1 (mod 2) ---> 111₍₂₎ = 7₍₁₀₎

將GF(pⁿ)如法炮製,便得到一個有限範圍整數的運算系統,有pⁿ種整數。不過加減乘除的結果變得非常詭異,尤其是乘除,根本毫無規律可言。由於毫無規律,所以非常適合用於製造隨機排列、製造亂數、製造密碼等等。

GF(2³), irreducible polynomial is x³ + x + 1 ---> 11
x³ ≡ x + 1         ---> 8 ≡ 3
x² + (x² + 1) ≡ 1  ---> 4 + 5 ≡ 1
x² × (x² + 1) ≡ x  ---> 4 × 5 ≡ 2

+ | 0  1  2  3 4  5  6  7     × | 0  1  2  3 4  5  6  7
--|-----------------------     --|-----------------------
0 | 0  1  2  3  4  5  6  7     0 | 0  0  0  0  0  0  0  0
1 | 1  0  3  2  5  4  7  6     1 | 0  1  2  3  4  5  6  7
2 | 2  3  0  1  6  7  4  5     2 | 0  2  4  6  3  1  7  5
3 | 3  2  1  0  7  6  5  4     3 | 0  3  6  5  7  4  1  2
4 | 4  5  6  7  0  1  2  3     4 | 0  4  3  7  6  2  5  1
5 | 5  4  7  6  1  0  3  2     5 | 0  5  1  4  2  7  3  6
6 | 6  7  4  5  2  3  0  1     6 | 0  6  7  1  5  3  2  4
7 | 7  6  5  4  3  2  1  0     7 | 0  7  5  2  1  6  4  3

只消調整一下質式與質數,輕鬆得到另一套詭異的運算表。

一、調整質數:電腦採用二進位,為了方便計算,我們習慣令質數為2,即GF(2ⁿ),把餘數多項式變成二進位數字。

二、調整質式:餘數多項式的質式不好求。我們習慣直接使用前人留下來的表格:

http://mathworld.wolfram.com/IrreduciblePolynomial.html

乘法群

模數是任意的餘數多項式。取出「與模數互質的餘數多項式」。「與模數互質的餘數多項式」暨乘法除法,也是乘法群。

進一步將多項式簡化為數字,可以得到超級詭異的運算系統,難以察覺規律!

Finite Field (Arithmetic)

四則運算

有限體運算,即是多項式運算暨餘數運算。多項式運算請見本站文件「Polynomial」。餘數運算請見本站文件「Residue」。

電腦採用二進位,大家習慣使用GF(2ⁿ)。以Bitset和Bitwise Operation,以unsigned int和& | ^,實作四則運算,事情變得簡單多了。

GF(2ⁿ)的情況下,正號=負號,加法=減法=XOR。

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2)
x ≡ -x                        ---> 010₍₂₎
x + 1 ≡ x - 1                 ---> 011₍₂₎
x² + (x² + 1) ≡ x² - (x² + 1) ---> 100₍₂₎ ⊕ 101₍₂₎

luogu P3812

Finite Field (Generator)

Fermat's Little Theorem

專著《Error Correction Coding: Mathematical Methods and Algorithms》

有限體費馬小定理:x^pⁿ ≡ x。x是任意餘數多項式。

Primitive Element

首一多項式(Monic Polynomial):首項係數為一。

不可約多項式(Irreducible Polynomial):無法因式分解。意義宛如質數。

最小多項式(Minimal Polynomial):次方值最低、首項係數為1、包含指定的根。顯然是不可約多項式。

單位根(Root of Unity):方程式xⁿ = 1的根。

單位原根(Primitive Root of Unity):n次單位根,且不是更低次單位根。顯然指數互質。

分圓多項式(Cyclotomic Polynomial):n次單位原根總乘積。

費馬小定理(Fermat's Little Theorem):等號兩側同除x,得到x^(pⁿ - 1) ≡ 1。GF(pⁿ)每個非零元素宛如pⁿ - 1次單位根。

生成元(Generator):特定元素,反覆實施特定運算,生成特定集合。

原元素(Primitive Element):GF(pⁿ)生成元,每個次方恰好生成每個非零元素。GF(pⁿ)恰有φ(pⁿ - 1)個原元素。意義宛如原根。

原多項式(Primitive Polynomial):最小多項式,根包含任意原元素。換句話說,原元素改寫成餘數多項式,次方最低、首項係數為1者。

Finite Field (Primality Test)(Under Construction!)

Monic Irreducible Polynomial

專著《A Computational Introduction to Number Theory and Algebra》

有限體費馬小定理:首一質式總乘積。

x^q - x ≡  pro  (x-a)     一次首一多項式總乘積
         a∈GF(q)

where q = pⁿ              有限體尺寸
x^qⁿ - x ≡ pro Pₖ         次數是因數的首一質式總乘積
           k|n

where Pₖ = pro (xᵏ+...)   k次首一質式總乘積
       irreducible

Monic Irreducible Divisor

利用費馬小定理、最大公因式,擷取質因式。

f₁ = gcd(f, x^q  - x)         f(x)所有一次質因式總乘積
f₂ = gcd(f/f₁, x^q² - x)      f(x)所有二次質因式總乘積
f₃ = gcd(f/f₁/f₂, x^q³ - x)   f(x)所有三次質因式總乘積

Irreducibility Test

「不可約測試」。測試一個多項式是否為質式。

質式沒有任何因式(除了1和自身)。窮舉所有可能的因式(或者質因式),沒有因式,就是質式。

次方過半的質因式,頂多只有一個。窮舉一半足矣。

Rabin's polynomial irreducibility test

Finite Field (Factorization)(Under Construction!)

Factorization

專著《Algorithms for Computer Algebra》

non-square-free → square-free → distinct-degree → equal-degree

Non-Square-free Factorization

微分、最大公因數,得到所有二次以上因式連乘積。

gcd(f, f')       square part (Z)
gcd(f, x^p - x)  factor (GF)

Square-free Factorization

所有因式,依照次方,進行分類。

演算法是「最大公因式」和「Yun's Algorithm」。

pp(f) = ((ax+b)(cx+d)(ex²+fx+g)...)¹
      × ((px+q)(rx²+sx+t)...)²
      × ...
a   = a₁¹ a₂² a₃³ ...                     pp(f)各項連乘
a′  = (1 a₁¹⁻¹ a₁′) (    a₂² a₃³ ...)     各項分別微分
    + (2 a₂²⁻¹ a₂′) (a₁¹     a₃³ ...)
    + (3 a₃³⁻¹ a₃′) (a₁¹ a₂²     ...)
    + ......

c   = gcd(a,a′) = a₁¹⁻¹ a₂²⁻¹ a₃³⁻¹ ...   次方減一
w   = a/c       = a₁ a₂ a₃ ...            次方消失
y   = gcd(c,w)  =    a₂ a₃ ...
w/y             = a₁                      得到一次項的連乘積

c/y = gcd(c,c′) =       a₂²⁻² a₃³⁻² ...   第二回合,次方再減一
 :     :                :
i=1;output=1;b=der(a);c=gcd(a,b);w=a/c;
while(c!=1){g=gcd(w,z);z=div(w,y);output=pow(g,i);i++;
w=y;c=div(c,y);}
return mul(output,pow(w,i));

Yun's algorithm

a   = a₁¹ a₂² a₃³ ...                      pp(f)各項連乘
a′  = (1 a₁¹⁻¹ a₁′) (    a₂² a₃³ ...)      各項分別微分
    + (2 a₂²⁻¹ a₂′) (a₁¹     a₃³ ...)
    + (3 a₃³⁻¹ a₃′) (a₁¹ a₂²     ...)
    + ......
c   = gcd(a,a′) = a₁¹⁻¹ a₂²⁻¹ a₃³⁻¹ ...    次方減一
w   = a/c       = a₁    a₂    a₃    ...    次方消失

y   = a′/c      = (1 a₁′) (   a₂ a₃ ...)   各項分別微分
                + (2 a₂′) (a₁    a₃ ...)
                + (3 a₃′) (a₁ a₂    ...)
                + ......

w′              = (a₁′) (    a₂ a₃ ...)
                + (a₂′) (a₁     a₃ ...)
                + (a₃′) (a₁ a₂     ...)
                + ......

z   = y-w′      = (1 a₂′) (a₁    a₃ ...)
                + (2 a₃′) (a₁ a₂    ...)
                + ......

gcd(w,z)        = a₁
i=1;output=1;b=der(a);c=gcd(a,b);
if(c==1){w=a;return pow(w,i);}
w=div(a,c);y=div(b,c);z=y-der(w);
while(z!=0){g=gcd(w,z);output=pow(g,i);i++;
w=div(w,g);y=div(z,g);z=y-der(w);}
return mul(output,pow(w,i));
Yun's algorithm = Gram-Schmidt Orthonormalization
square-free = linear
dot product = gcd
derivative = shearing
basis = exp incremental

Distinct-degree Factorization

演算法是「Berlekamp's Algorithm」和「Cantor-Zassenhaus Algorithm」。

Equal-degree Factorization

Finite Field (Logarithm)(Under Construction!)

Discrete Logarithm

演算法是「Number Field Sieve」和「Function Field Sieve」。

https://en.wikipedia.org/wiki/Discrete_logarithm_records