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 (Factorization)(Under Construction!)

Reducible

不可約多項式(Irreducible Polynomial):質數,推廣到餘數多項式。無法因式分解。

有限體費馬小定理:x^q ≡ x。

x^q  - x ≡  pro (x-a)       所有一次多項式連乘積
          a∈GF(q)
x^q² - x ≡  pro (x²+bx+c)   所有二次多項式連乘積
          a∈GF(q)
x^q³ - x ≡  pro (x³+...)    所有三次多項式連乘積
          a∈GF(q)

利用最大公因式擷取因式。

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)所有三次因式連乘積

Factorization

square-free
distinct-degree
equal-degree

Square-free Factorization

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

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
gcd(f, f')       square part (Z)
gcd(f, x^p - x)  factor (GF)

Distinct-degree Factorization

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

Equal-degree Factorization

Root Finding

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

Finite Field (Logarithm)(Under Construction!)

Discrete Logarithm

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

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

Finite Field (GCD)(Under Construction!)

Greatest Common Divisor

Finite Field (Group)(Under Construction!)

乘法群

原多項式(Primitive Polynomial):原根,推廣到餘數多項式。用來生成所有元素。

http://www.seanerikoconnor.freeservers.com/Mathematics/AbstractAlgebra/PrimitivePolynomials/theory.html

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

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