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ⁿ)或者𝔽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 (Logarithm)(Under Construction!)

Discrete Logarithm

演算法是「Number Field Sieve (Index Calculus Algorithm)」和「Function Field Sieve」。

演算法(Index Calculus Algorithm)

簡單起見,討論特例GF(p)。即是餘數,模數是質數p。

find a ^ x ≡ b (mod p)
find x ≡ logₐb (mod φ(p))        (φ(p) = p-1 when p is prime)

1. random number:  α (mod p)
2. exponentiation: a^α (mod p)
3. factorization:  a^α = p₁^e₁ × p₂^e₂ × ...
4. logarithm:      α   ≡ e₁ logₐp₁ + e₂ logₐp₂ + ... (mod φ(p))
   (in mind)                ^^^^^^      ^^^^^^ (unknown variables)
5. solve linear equations:
   { α₁ ≡ e₁₁ logₐp₁ + e₁₂ logₐp₂ + ... (mod φ(p))
   { α₂ ≡ e₂₁ logₐp₁ + e₂₂ logₐp₂ + ... (mod φ(p))
   {    :
6. multiplication: a^α × b (mod p)
7. factorization:  a^α × b = p₁^f₁ × p₂^f₂ × ...
8. logarithm:      α + logₐb ≡ f₁ logₐp₁ + f₂ logₐp₂ + ... (mod φ(p))
   (in mind)           ^^^^^ (unknown variable)
9. solve equation: α + logₐb ≡ f₁ logₐp₁ + f₂ logₐp₂ + ... (mod φ(p))

隨機選擇x,計算a^x,質因數分解,在心中取對數。質因數對數視作變數,形成一次方程式。

隨機選擇大量x,數量是質因數種類(φ(p)的某個因數)。形成一次方程組。解出每種質因數對數。

a^x額外乘上b,質因數分解,在心中取對數。出現logₐb,形成方程式。移項求得logₐb。

質因數種類不能太多,運氣成分很高。

餘數隨機數:整數隨機數,範圍[0,p)。
餘數乘方:倍增法。
整數分解:試除法。
餘數一次方程組求解:高斯消去法。

回到正題,討論GF(pⁿ)。

有限體隨機數:n個整數隨機數,範圍[0,p)。
有限體乘方:請參考多項式乘方。
餘數多項式分解、模數是質數p:有限體多項式分解的特例。請見後面章節。
有限體一次方程組求解:高斯消去法。

演算法(Number Field Sieve)

演算法(Function Field Sieve)

Finite Field (Polynomial)(Under Construction!)

多項式

整數多項式(Integer Polynomial):係數和變數均為整數。標記成ℤ[X]。

餘數多項式(Residue Polynomial):係數和變數均為餘數。標記成(ℤ/mℤ)[X]或者ℤₘ[X]。

有限體多項式(Finite Field Polynomial):係數和變數均為有限體。標記成GF(pⁿ)[X]或者𝔽pⁿ[X]。

餘數多項式、模數是質數p:可以視作有限體多項式的特例。標記成GF(p)[X]或者𝔽ₚ[X]。

GF(p)擴張體(Extension Field of GF(p)):把GF(p)[X]弄成有限體。等價於GF(pⁿ)。

Finite Field (Divisibility)(Under Construction!)

Polynomial GCD

https://math.mit.edu/classes/18.783/2021/lectures.html

https://mathoverflow.net/questions/239354/

Finite Field (Primitivity)(Under Construction!)

Fermat's Little Theorem

GF(pⁿ)有限體費馬小定理:x^pⁿ ≡ x。

Primitive Polynomial

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

專著《Cryptography and Secure Communication》

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

不可約多項式(Irreducible Polynomial):無法因式分解。地位宛如質數。乾脆叫做質式。

最小多項式(Minimal Polynomial):次方值最低、首項係數為1、包含指定的根。可視作質式,前提是質式們沒有共同的根。

單位根(Root of Unity):方程式xⁿ = 1的根。複數平面單位圓n等分。每個指數對應每個單位根。

單位原根(Primitive Root of Unity):n次單位根,且不是更低次單位根。顯然指數與n互質。顯然數量是φ(n)個。任意一個n次單位原根,其每個次方恰好生成每個n次單位根。

分圓多項式(Cyclotomic Polynomial):第n個分圓多項式,根是所有的n次單位原根。恰巧得到整數多項式。可視作最小多項式,可視作質式。

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

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

原根(Primitive Root):GF(p)生成元,每個次方恰好生成每個非零元素。GF(p)恰有φ(p - 1) = φ(φ(p))個原根。地位宛如p-1次單位原根。

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

原多項式(Primitive Polynomial):n次原多項式,根是n個相異的GF(pⁿ)原元素,而且必須恰巧得到GF(p)[X]。n次原多項式的數量是φ(pⁿ - 1) / n個。可視作最小多項式,可視作質式。

Primitive Polynomial Generation

演算法是「Saxena–McCluskey Algorithm」。

Finite Field (Irreducibility)(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ⁿ              有限體尺寸

有限體分圓多項式:n次質式總乘積。

x^qⁿ - x ≡ pro Pₖ         次數是因數的首一質式總乘積
           k|n

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

利用最大公因式,擷取n次質因式。

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 Irreducibility Test」和「Ben–Or's Irreducibility Test」。

Irreducible Polynomial Generation

我沒有研究。

Finite Field (Factorization)(Under Construction!)

Factorization

專著《Algorithms for Computer Algebra》

三個步驟。

square-free → distinct-degree → equal-degree

三個技巧。

1. gcd(f, f')             decrease exponent over Z[X]
2. gcd(f, x𐞥 - x)         extract factors of degree 1 over GF(q)[X]
3. x𐞥 - x ≡ x (x⁽𐞥⁻¹⁾ᐟ² - 1) (x⁽𐞥⁻¹⁾ᐟ² + 1)

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=a′;c=gcd(a,b);w=a/c;
while(c!=1){g=gcd(w,z);z=w/y;output=gⁱ;i++;w=y;c=c/y;}
return output*wⁱ;

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=a′;c=gcd(a,b);if(c==1){w=a;return wⁱ;}
w=a/c;y=b/c;z=y-w′;
while(z!=0){g=gcd(w,z);output=gⁱ;i++;w=w/g;y=z/g;z=y-w′;}
return output*wⁱ;
Yun's algorithm = Gram–Schmidt Orthonormalization
square-free = linear
dot product = gcd
derivative = shearing
basis = exp incremental

pth root

GF(q) = GF(pⁿ)
1. a^q ≡ q
2. a^(1/p) ≡ a^(q/p) ≡ a^(pⁿ⁻¹)
3. (a+b)^pⁱ ≡ a^pⁱ + b^pⁱ
4. if a′ ≡ 0 then a ≡ bᵖ

a(x)  = a₀x⁰ + a₁x¹ + a₂x² + a₃x³
b(x)ᵖ = b₀ᵖx⁰ᵖ + b₁ᵖx¹ᵖ + b₂ᵖx²ᵖ + b₃ᵖx³ᵖ
i=1;output=1;b=a′;if(b==0){return SFF(a¹ᐟᵖ)ᵖ;}
c=gcd(a,b);w=a/c;
while(w!=1){y=gcd(w,c);z=w/y;output=zⁱ;i++;w=y;c=c/y;}
if(c!=1)output*=SFF(c¹ᐟᵖ)ᵖ;
return output;

Distinct-degree Factorization

相同指數的因式,依照度數,進行分類。

演算法是「Rabin's Irreducibility Test」。

度數過半的質因式頂多一個,窮舉一半足矣。

Equal-degree Factorization

相同指數、相同度數的因式,徹底分解。

演算法是「Cantor–Zassenhaus Algorithm」。隨機演算法。

when p = 2 (when pⁿ = q is even)
x𐞥 - x ≡ (x¹ + x² + x⁴ + ... + x𐞥ᐟ²) (x¹ + x² + x⁴ + ... + x𐞥ᐟ² + 1)

when p > 2 (when pⁿ = q is odd)
x𐞥 - x ≡ x (x⁽𐞥⁻¹⁾ᐟ² - 1) (x⁽𐞥⁻¹⁾ᐟ² + 1)

substitute pᵈ for pⁿ = q, where d is target degree
v = random();
//if ((g = gcd(a,v)) != 1) return CZ(g) ∪ CZ(a/g);
if (p == 2) v = v^1 + v^2 + v^4 + ... + v^2ᵈ⁻¹
else v = v^((pᵈ-1)/2) + 1
g = gcd(a,v)
if (0 < deg(g) < deg(f)) return CZ(g) ∪ CZ(a/g);

Distinct-degree and Equal-degree Factorization

相同指數的因式,徹底分解。

演算法是「Berlekamp's Algorithm」。一口氣做完兩個步驟,但是整體速度較慢,不實用。

gcd(x-s, x-t) = 1   when s ≠ t

x^q - x = pro (x-s)
        s∈GF(q)

V(x)^q - V(x) = pro (V(x)-s)
              s∈GF(q)

a = pro gcd(V(x)-s, a)
  s∈GF(q)

aᵢ | (V(x)^q - V(x)) => aᵢ | gcd(V(x)-sᵢ, a)   where a is square-free
find T that Tx = x^q for all x
find B = T-I that Bx = (x^q - x) for all x
find b = kernel(B)
for (each α ∈ span(b))
	g = gcd(α⁽𐞥⁻¹⁾ᐟ²+1, a)
	if (0 < deg(g) < deg(a)) return g;

Elliptic Curve(Under Construction!)

Elliptic Curve

專著《Serious Cryptography: A Practical Introduction to Modern Encryption》

專著《Introduction to Cryptography with Coding Theory》

E: y² = x³ + ax + b
⇒ 2ydy = 3x²dx + adx
⇒ dy/dx = (3x²+a)/(2y)

P₁ = (x₁,y₁)
P₂ = (x₂,y₂)
P₁ + P₂ = P₃ = (x₃,y₃) ≠ 0

{ x₃ = m² - x₁ - x₂
{ y₃ = m(x₁-x₃) - y₁

m = { (y₂ - y₁) / (x₂ - x₁)   if P₁ ≠ P₂
    { (3x₁² + a) / (2y₁)      if P₁ = P₂, y₁ ≠ 0