ECC相关概念

有限域和阶

一个域的元素是有限的，称为有限域。有限域中元素的个数被称为有限域的阶。

素域F_p

• 域中的元素用整数0,1,2,...,p-1表示
• 加法单位元是整数0
• 乘法单位元是整数1
• 域元素的加法是整数的模p加法，即若a,b∈F_p，则a+b=(a+b) mod p
• 域元素的乘法是整数的模p乘法，即若a,b∈F_p，则a · b=(a · b) mod p

二元扩域F_2^m

• 二元扩域F_2^m可以看成F₂上的m维向量空间，其元素可用长度为m的比特串表示。
• 零元0用全0比特串表示
• 乘法单位元1用比特串(00···001)表示
• 两个域元素的加法为比特串的按比特异或运算
• 域元素a和b的乘法定义如下：设a和b对应的F₂上多项式为a(x)和b(x)，则a · b定义为多项
  式(a(x)b(x)) mod f (x)对应的比特串

有限域上的椭圆曲线

有限域F_q上的椭圆曲线是由点组成的集合。在仿射坐标系下，椭圆曲线上点P(非无穷远点)的坐标
表示为P = (xP,yP)，其中xP, yP为满足一定方程的域元素，分别称为点P的x坐标和y坐标。

F_p上的椭圆曲线

定义在F_p(p是大于3的素数)上的椭圆曲线方程为：
y² = x³ + ax + b, a,b ∈ Fp，且(4a³ +27b²) mod p != 0
椭圆曲线E(Fp)定义为：
E(Fq) = {(x,y)|x,y ∈ Fp，且满足方程(1)}∪{O}，其中O是无穷远点。
椭圆曲线E(Fp)上的点的数目用#E(Fq)表示，称为椭圆曲线E(Fp)的阶

椭圆曲线多倍点运算

椭圆曲线上同一个点的多次加称为该点的多倍点运算。设k是一个正整数， P是椭圆曲线上的点，称点P的k次加为点P的k倍点运算，记为Q = [k]P = P +P +··· +P| {z }k个。因为[k]P = [k − 1]P +P，所以k倍点可以递归求得。

椭圆曲线离散对数问题(ECDLP)

已知椭圆曲线E(Fq)、阶为n的点P ∈ E(Fq)及Q ∈ ⟨P⟩，椭圆曲线离散对数问题是指确定整数l ∈[0;n− 1]，使得Q = [l]P成立。