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

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

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

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

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

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2)
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 (mod 2)
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ⁿ),把餘數多項式變成二進位數字。

二、調整質式:餘數多項式的質式,目前沒有快速的演算法。我們習慣直接使用前人留下來的表格:

finite field - arithmetic

四則運算

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

電腦採用二進位,有限體適合採用GF(2ⁿ)。以bitset和bitwise operation,以unsigned int和& | ^ << >>,實作四則運算,事情簡單多了。位元運算請見本站文件「bit」。

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🚧

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-1. random number:
     α (mod p)
1-2. exponentiation:
     a^α (mod p)
1-3. factorization:
     a^α = p₁^e₁ × p₂^e₂ × ...
1-4. logarithm (in mind):
     α ≡ e₁ logₐp₁ + e₂ logₐp₂ + ... (mod φ(p))
            ^^^^^^      ^^^^^^ (unknown variables)
1-5. solve linear equations:
     ⎧ α₁ ≡ e₁₁ logₐp₁ + e₁₂ logₐp₂ + ... (mod φ(p))
     ⎨ α₂ ≡ e₂₁ logₐp₁ + e₂₂ logₐp₂ + ... (mod φ(p))
     ⎩    :
2-1. multiplication:
     a^α × b (mod p)
2-2. factorization:
     a^α × b = p₁^f₁ × p₂^f₂ × ...
2-3. logarithm (in mind):
     α + logₐb ≡ f₁ logₐp₁ + f₂ logₐp₂ + ... (mod φ(p))
         ^^^^^ (unknown variable)
2-4. 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 - group

primitive element

加法循環、乘法循環、次方循環,可以求得所有數字。加法循環、乘法循環需要兩種數字,次方循環只需一種數字。因此數學家特別喜歡次方循環。數學家以此為根基,發展了一套理論。

當g¹ g² g³ ... 恰好生成每一個元素,那麼g稱作「原元素」。

群論觀點:次方循環是「群group」,原元素是「生成元generator」。

GF(2³), irreducible polynomial is x³ + x + 1 (mod 2)

a primitive element is x + 1 (mod 2)
(x + 1)¹ ≡ x + 1                            ---> 011₍₂₎
(x + 1)² ≡ x² + 2x + 1         ≡ x² + 1     ---> 101₍₂₎
(x + 1)³ ≡ (x + 1)(x² + 1)     ≡ x²         ---> 100₍₂₎
(x + 1)⁴ ≡ (x + 1) x²          ≡ x² + x + 1 ---> 111₍₂₎
(x + 1)⁵ ≡ (x + 1)(x² + x + 1) ≡ x          ---> 010₍₂₎
(x + 1)⁶ ≡ (x + 1) x           ≡ x² + x     ---> 110₍₂₎
(x + 1)⁷ ≡ (x + 1)(x² + x)     ≡ 1          ---> 001₍₂₎

找出原元素,目前沒有快速的演算法。我不清楚這是P問題或是NP問題,我沒有查到資料。

primitive root vs. primitive element

餘數的生成元,稱作「原根」。

有限體的生成元,稱作「原元素」。

兩者概念完全相同,但是兩者名稱沒有統一。

乘法群

似乎沒有實際用途。只是順便介紹。

構造有限體,需要指定模數,模數是質數暨質式。模數可以改成任意的餘數多項式。取出「與其互質的餘數多項式」做為元素。「與其互質的餘數多項式」暨乘法除法,形成乘法群。

finite field polynomial

楔子

雖然本章標題是有限體多項式,但是為了把事情講清楚,本章將介紹各種多項式,其中包含有限體多項式。

polynomial

實數多項式(real polynomial):係數是實數。標記成ℝ[X]。

複數多項式(complex polynomial):係數是複數。標記成ℂ[X]。

整數多項式(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ⁿ)。

polynomial心照不宣的慣例

係數與變數不見得是相同類型。

經典範例:係數是實數、變數是複數(實數多項式的共軛複數根)。

每當數學家討論多項式,係數是已知類型,變數是未知類型!我們不能私自推定變數擁有特殊性質,除非明確指定了變數類型。

經典範例:餘數多項式,係數是餘數(模數為p),變數是未知類型。變數不可以次方循環(x^p ≡ x不成立)。

irreducible polynomial(prime polynomial)

「不可約多項式」。俗稱「質式」。無法用乘法分解的多項式。

係數是已知類型、變數是未知類型,則存在質式。

因式的次方值,必定遞減,直到收斂。

x² + 1 (mod 5)x + 2 (mod 5) × x + 3 (mod 5)
x² + 1 (mod 5) is not an irreducible polynomial
x + 2 (mod 5) and x + 3 (mod 5) are irreducible polynomials

係數與變數都是已知類型,則不一定存在質式。

因式的次方值,可能變大,無法收斂。

經典範例:係數與變數都是餘數。

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

irreducible polynomial心照不宣的慣例

每當數學家討論質式,習慣把變數重新視作未知類型!即便變數是已知類型!

monic polynomial

「首一多項式」。最高次方項(首項)係數是一的多項式。

實數的乘法分解有無限多種方式,導致實數多項式的倍率提取有無限多種方式。

餘數多項式、有限體多項式亦然。

  x + 2 (mod 5)2 (mod 5) × 3x + 1 (mod 5)3 (mod 5) × 2x + 4 (mod 5)4 (mod 5) × 4x + 3 (mod 5)

實數多項式的因式分解,可以提取適當倍率,讓所有因式的首項係數均是1。

餘數多項式、有限體多項式亦然。

  2x² + 2x + 1 (mod 5)2 (mod 5) × x² + x + 3 (mod 5)2 (mod 5) × x + 2 (mod 5) × x + 4 (mod 5)

當模數是質數,那麼餘數多項式恰有唯一一種因式分解方式!

monic polynomial心照不宣的慣例

每當數學家討論整數多項式,因式與質式不是首一多項式。

每當數學家討論實數多項式、餘數多項式、有限體多項式,因式與質式預設是首一多項式。

minimal polynomial

「最小多項式」。包含指定的根r(甚至指定許多根r₁ r₂ ...),而且度數盡量小(因式盡量少),而且首項係數是1。

根與係數通常是不同類型!變數仍是未知類型!

如果根與係數是相同類型,最小多項式是(x-r₁)(x-r₂)...。缺乏討論意義。

如果根與係數是不同類型,最小多項式是(x-r₁)(x-r₂)...,再乘上其他因式,使得根類型恰巧轉變成係數類型。

經典範例:係數是實數、根是複數。想要包含指定的複數根r,需要因式(x-r),還需要追加因式(x-r̅),其中r̅是r的共軛複數。兩者相乘才能湊得實數多項式。

(根與係數是已知類型)最小多項式⊂(根類型只能是係數類型)質式。數學家習慣省略前綴:最小多項式⊂質式。

minimal polynomial心照不宣的慣例

每當數學家討論最小多項式,根與係數是不同類型!

cyclotomic polynomial

「分圓多項式」。最小多項式,係數是整數,根是複數,指定的根是單位根。

數學家已經找到公式解。一步一步來:

單位圓:複數平面上,圓心為原點、半徑為1。

n次單位根:方程式xⁿ = 1的根。單位圓上的n等分點。習慣寫成歐拉公式。

n次單位原根:n次單位根,但不是更低次單位根。無法約分的等分點。跟n互質的等分點。數量顯然是φ(n)個,φ是互質數計數函數。

分圓多項式:n次單位原根,作為因式。因式相乘之後,恰為整數多項式,而且因式數量是最少的(形成最小多項式)。證明省略。

分圓多項式公式解:所有的n次單位原根,作為因式。

Φ₁(x) = (x - ω(1/1))
      = x - 1

Φ₂(x) = (x - ω(1/2))
      = x + 1

Φ₃(x) = (x - ω(1/3))(x - ω(2/3))
      = x² + x + 1

Φ₄(x) = (x - ω(1/4))(x - ω(3/4))
      = x² + 1

Φ₅(x) = (x - ω(1/5))(x - ω(2/5))(x - ω(3/5))(x - ω(4/5))
      = x⁴ + x³ + x² + x + 1

Φ₆(x) = (x - ω(1/6))(x - ω(5/6))
      = x² - x + 1
 :         :

where ω(t) = e𝑖⋅2π⋅t

primitive polynomial

「原多項式」。最小多項式,係數是有限體GF(p),根是有限體GF(pⁿ),指定的根是原元素。

原多項式宛如分圓多項式,但是細節稍微不同。數學家已經找到公式解。一步一步來:

GF(pⁿ)費馬小定理:x^(pⁿ-1) ≡ 1的解,是全體元素去掉0。

GF(pⁿ)原元素:g¹ g² ... 都不是1,直到g^(pⁿ-1)才是1。換句話說,x^(pⁿ-1) ≡ 1的解,但不是更低次的解。數量顯然是φ(pⁿ-1)個,φ是互質數計數函數。證明省略。

原多項式:GF(pⁿ)原元素,各種p次方的次方,作為因式。因式相乘之後,恰為GF(p)多項式,而且因式數量是最少的(形成最小多項式)。證明省略。

原多項式公式解:g是任意一個GF(pⁿ)原元素。

F(x) = (x - g)(x - g^p¹)(x - g^p²)...(x - g^pⁿ⁻¹)

primitive polynomial特殊功用

構造有限體,需要指定模數,模數是質數暨質式。將模數設定成原多項式,那麼x一定是原元素(生成元)。證明省略。

x是原元素,計算過程變得非常簡單!

GF(2³), irreducible polynomial is
primitive polynomial x³ + x + 1 (mod 2).

therefore x (mod 2) must be a primitive element.
x¹ ≡ x          ---> 010₍₂₎
x² ≡ x²         ---> 100₍₂₎
x³ ≡ x + 1      ---> 011₍₂₎
x⁴ ≡ x² + x     ---> 110₍₂₎
x⁵ ≡ x² + x + 1 ---> 111₍₂₎
x⁶ ≡ x² + 1     ---> 101₍₂₎
x⁷ ≡ 1          ---> 001₍₂₎

質式、原元素,目前都沒有快速的演算法,所幸網路上已經有現成的表格了。原多項式,演算法是高斯消去法。既然如此,選擇原多項式,事情比較簡單。

這個特殊功用,就是本章唯一重點。前面鋪陳一長串數學術語,就是為了介紹這個特殊功用。數學家這份工作,就是這麼辛苦。

總結

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

首一多項式(monic 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個。可視作最小多項式,可視作質式。

finite field polynomial - greatest common divisor

greatest common divisor of polynomials

「最大公因式」。兩個多項式的共同因式,度數最高者。

演算法是「輾轉相除法Euclidean algorithm」。就這樣。

特殊數學公式

finite field polynomial - irreducible polynomial

Fermat's little theorem

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

註:這裡的變數x是已知類型:有限體GF(pⁿ)。

monic irreducible polynomial

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

專著《The Art of Computer Programming, Volume 2: Seminumerical Algorithms》

有限體多項式當中,質式習慣設定成首一多項式。

「一次質式總乘積」的數學公式。證明省略。

註:這裡的變數x是未知類型。

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

where q = pⁿ               有限體尺寸

包含了「k次質式總乘積」的數學公式。證明省略。

x^qᵐ - x ≡ prod Pₖ          次數是因數的首一質式總乘積
           k|m

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

where q = pⁿ                有限體尺寸

利用最大公因式,擷取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 polynomial - factorization🚧

factorization

專著《Algorithms for Computer Algebra》

三個步驟。

1. square-free factorization
2. distinct-degree factorization
3. equal-degree factorization

三個技巧。

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

所有因式,依照指數,進行分類。

演算法是「gcd(f,f′)」和「Yun's algorithm」。

a(x) = (1+x)¹(1-2x+2x²)¹ (1-x)²(3-2x)²(2-x+x²)² x³(2x-1)³
       ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^
     = a₁(x)¹ a₂(x)² a₃(x)³ ...

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 = prod (x-s)
         s∈GF(q)

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

a = prod 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;

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;

finite field polynomial - primitive polynomial🚧

primitive polynomial

「原多項式」。最小多項式,係數是有限體GF(p),根是有限體GF(pⁿ),指定的根是原元素。

primitive polynomial generation

演算法是「Saxena–McCluskey algorithm」。

我沒有研究。

elliptic curve [𝔽]

elliptic curve

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

專著《Introduction to Cryptography with Coding Theory》

「橢圓曲線」。形如y² = x³ + ax + b的二元方程式。

此處討論有限體版本:係數和變數都是有限體。

繪圖時,可以繪製成二維曲線的整數格點。

有限體橢圓曲線,主要用來製造更加詭異的運算表(二維數對的倍率運算)。小的整數也變得沒有規律了!

有空再來整理。

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