Halo2 学习笔记——背景资料之Fields（2）

1. Fields

很多密码学协议中的基础元素为名为fields的algebraic structure。

Fields为sets of objects (通常为numbers)，其具有two associated binary operators + + +和 × \times ×，使得各种field axioms(公理) 成立。 实数 R \mathbb{R} R为具有无数元素的field。

Halo使用的是有限域，具有有限数量的元素。有限域可分为：

• 若 F \mathbb{F} F为有限域，则其包含 ∣ F ∣ = p k |\mathbb{F}|=p^k ∣F∣=pk个元素，其中整数 k ≥ 1 k\geq 1 k≥1， p p p为素数。
• 任意两个具有相同数量元素的有限域都是isomorphic的。特别地，所有的arithmetic in a prime field F p \mathbb{F}_p Fp​ 是 isomorphic to addition and multiplication of integers modulo p p p，即in Z p \mathbb{Z}_p Zp​。这就是为什么我们经常把 p p p称为modulus。

定义field F q \mathbb{F}_q Fq​，其中 q = p k q=p^k q=pk，其中prime p p p称为其characteristic。当 k > 1 k>1 k>1时，field F q \mathbb{F}_q Fq​为a k k k-degree extension of the filed F p \mathbb{F}_p Fp​。（类比于，复数 C = R ( i ) \mathbb{C}=\mathbb{R}(i) C=R(i)为实数的extension。）

但是，在Halo中不使用extension fields。 F p \mathbb{F}_p Fp​是指a prime field，其具有prime p p p个元素，即 k = 1 k=1 k=1。

重点知识为：

• 在任意域中，都存在2个特殊的elements： 0 0 0 为additive identity； 1 1 1 为multiplicative identity。
• field element的最低位可用于表示其符号。如非零element a a a的最低位为 0 0 0，则 − a = p − a -a=p-a −a=p−a的最低位为 1 1 1，反之亦然。同时，也可以借助最低位来判断该element是否大于 ( p − 1 ) / 2 (p-1)/2 (p−1)/2。

有限域对于后续构建多项式和椭圆曲线很有用。椭圆曲线为examples of groups。

2. Groups

Groups比fields更简单更受限。 Groups仅有一个binary operator，且具有更少的公理。 Groups的identity表示为 1 1 1。

group中的任意非零元素具有倒数 b = a − 1 b=a^{-1} b=a−1，即有唯一的元素 b b b使得 a ⋅ b = 1 a\cdot b=1 a⋅b=1。

如， F p \mathbb{F}_p Fp​的非零元素集形成a group，其中group operations为multiplication on the field。

可将group分别表示为加法或乘法形态：

• 乘法形态时，上面的 ⋅ \cdot ⋅对应为 × \times ×，identity为 1 1 1，倒数为 a − 1 a^{-1} a−1。
• 加法形态时，上面的 ⋅ \cdot ⋅对应为 + + +，identity为 0 0 0或 O \mathcal{O} O，倒数为 − a -a −a。

当采用加法形态时，非负数 k k k， [ k ] A = A + A + ⋯ + A [k]A=A+A+\cdots+A [k]A=A+A+⋯+A 称为“scalar multiplication”，采用的大写的字母来表示group elements变量。

当采用乘法形态时， a k = a × a × ⋯ × a a^k=a\times a\times \cdots \times a ak=a×a×⋯×a 称为“exponentiation”。

将使得 [ k ] g = a [k]g=a [k]g=a或 g k = a g^k=a gk=a成立的scalar k k k值为the “discrete logarithm” of a a a to base g g g。可将scalar值扩展至负数，即 [ − k ] A + [ k ] A = O [-k]A+[k]A=\mathcal{O} [−k]A+[k]A=O 或 a − k × a k = 1 a^{-k}\times a^k=1 a−k×ak=1。

对于finite group内的元素 a a a，使得 a k = 1 a^k=1 ak=1或 [ k ] a = O [k]a=\mathcal{O} [k]a=O成立的最小正整数 k k k值称为the order of an element a a a of the group。the order of the group是指group内的元素数。

Groups通常有a generating set，即基于该generating set可生成group中的任意元素，以乘法形态表示的话，生成方式为基于该generating set元素的product of powers。因此，若该generating set为 g 1 ⋯ k g_{1\cdots k} g1⋯k​，基于 ∏ i = 1 k g i a i \prod_{i=1}^{k}g_i^{a_i} ∏i=1k​giai​​可生成该group中的任意元素。

若generating set中仅有一个元素—— g g g（不要求generating set的唯一性），则可称该group为cyclic的。即基于 g g g可生成该group，the order of g g g为the order of the group。

任意的finite cyclic group G \mathbb{G} G of order n n n 为 isomorphic to the integers modulo n n n （表示为 Z / n Z \mathbb{Z}/n\mathbb{Z} Z/nZ），使得：

• G \mathbb{G} G的operation ⋅ \cdot ⋅ 对应为 addition modulo n n n。
• G \mathbb{G} G中的identity对应为 0 0 0。
• generator g ∈ G g\in\mathbb{G} g∈G 对应为 1 1 1。

已知generator g g g，很容易根据 Z / n Z → G \mathbb{Z}/n\mathbb{Z}\rightarrow \mathbb{G} Z/nZ→G计算isomorphism，即 a → g a a\rightarrow g^a a→ga（加法形态表示为 a → [ a ] g a\rightarrow [a]g a→[a]g），但是计算 G → Z / n Z \mathbb{G}\rightarrow \mathbb{Z}/n\mathbb{Z} G→Z/nZ会很困难。

若finite group 的order n n n为prime的，则该group为cyclic，且每个non-identity element都是generator。

3. The multiplicative group of a finite field

采用 F p × \mathbb{F}_p^{\times} Fp×​来表示multiplicative group over the set F p − { 0 } \mathbb{F}_p-\{0\} Fp​−{0}。所谓multiplicative group是指 F p \mathbb{F}_p Fp​中的group operation为multiplication。

根据费马小定理，对于任意的 a a a，有 a p ≡ a ( m o d    p ) a^p\equiv a(\mod p) ap≡a(modp) 。 因此 F p × \mathbb{F}_p^{\times} Fp×​中对于任意的非零 a a a，其倒数运算为 a − 1 = a p − 2 a^{-1}=a^{p-2} a−1=ap−2。

假设 α \alpha α为 F p × \mathbb{F}_p^{\times} Fp×​的generator，其order为 p − 1 p-1 p−1 （ F p × \mathbb{F}_p^{\times} Fp×​中的元素个数为 p − 1 p-1 p−1个）。因此，对于任意的 a ∈ F p × a\in\mathbb{F}_p^{\times} a∈Fp×​，存在唯一的整数 i ∈ { 0 , p − 2 } i\in\{0,p-2\} i∈{0,p−2}，使得 a = α i a=\alpha^i a=αi。

注意，对于 a , b ∈ F p × a,b\in\mathbb{F}_p^{\times} a,b∈Fp×​，可将 a × b a\times b a×b理解为 α i × α j \alpha^i\times \alpha^j αi×αj，其中 a = α i , b = α j a=\alpha^i, b=\alpha^j a=αi,b=αj。而对于任意的 0 ≤ i , j < p − 1 0\leq i,j < p-1 0≤i,j