算法数论中的椭圆曲线

本学期椭圆曲线课的课外阅读材料。我们希望讨论椭圆曲线在算法数论中的应用。

约定以\Bbb Z/n\Bbb Z/n\Bbb Za/na \in \Bbb Z的模n约化。

之前介绍过的Miller-Rabin算法AKS素性测试均基于如下观察:乘法群\Bbb (Z/n)^*的性质反映了n的算术性质。Fermat小定理就是一例(用\Bbb (Z/n)^*的阶检验n的素性)。作为1维交换代数群,\Bbb Z/n上的椭圆曲线E:y^2=x^3+ax+b也反映了n的算术性质。它的优势在于:给定n(\Bbb Z/n)^*随之确定,但此时却有大量不同的椭圆曲线可资利用。更加令人满意的是,在提高算法可靠性的同时,我们并没有浪费时间:对不同曲线的测试可以并行计算

针对哪些初等算法能够设计出相应的椭圆曲线算法?一般来说,基于Fermat小定理/Euler定理的算法都是可以的。另一方面,AKS等算法本质地利用了\Bbb Z/p作为域(而不仅仅是乘法群)的性质,所以或许在代数数域上寻找改进更为合适。

E(\Bbb Z/p)的阶

为类比Fermat小定理,首先要确定|E(\Bbb Z/p)|Hasse定理给出基本估计|t|\leq 2\sqrt{p},其中t=p+1-E(\Bbb Z/p)。换言之,|E(\Bbb Z/p)|大致在p+1附近涨落。

在设计算法时,只需对N >4\sqrt{p}确定t/N即可确定|E(\Bbb Z/p)|。Schoof提出可选取N=\prod l_i(l_i \neq p为足够小的奇素数)以利用中国剩余定理。注意到t等于Frobenius映射\phi的迹,可以借助约化特征方程\phi^2-(t/l_i)\phi+(p/l_i) \equiv 0计算t/l_i

Schoof Elliptic Curves over Finite Fields and the Computation of Square Roots mod p

Schoof算法是计算|E(\Bbb Z/p)|的第一个多项式算法。遗憾的是对于不少应用Schoof算法仍不够高效。经Elkies和Atkin改进后的SEA算法要更好一些。

素性测试

经典的Pocklington-Lehmer素性测试基于如下原理:若存在素因子p \leq \sqrt{n},则满足q>p-1的、n-1的素因子q必与p-1互素。取某个a使得a^{n-1}/n=1,则p|\mathrm{gcd}(a^{(n-1)/q}-1,n)。反之,二者互素即推出n为合数。

现取椭圆曲线E:y^2=x^3+ax+ba,b \in \Bbb Z/n\mathrm{gcd}(\triangle(E),n)=1。素因子p \leq \sqrt{n}诱导同态E(\Bbb Z/n) \to E(\Bbb Z/p),后者的阶不大于(\sqrt[4]{n}+1)^2,即对于素数n_1> (\sqrt[4]{n}+1)^2E上不可能有n_1阶点。

这个想法发展为Goldwasser-Kilian算法:若n是素数,则Schoof算法可决定E(\Bbb Z/n)的阶m。给定r=(x,y),随机选取可能的a,b直至m可以分解一个小素数k和“疑似素数”n_1,要求kr \neq 0n_1> (\sqrt[4]{n}+1)^2(但最好尽量小)。若mr \neq 0,则n是合数,否则n_1r=0。为测试n_1的素性,继续调用上述算法得到n_2……

Goldwasser, Kilian  Almost all primes can be quickly certified

一个绕开Schoof算法的重大改进是Atkin-Morain椭圆曲线素性测试(ECPP):先选取合适的m,再借助复乘理论反过来构造E。这样一来算法的效率就大大提高了。

Atkin, Morain  Elliptic Curves and Primality Proving

大数分解

素性测试的复杂度是多项式级的(P),远为困难的是大数分解(NP)。这种难度差是RSA公钥密码得以成立的关键(换言之,P=NP若经证实,至少在理论上将极大威胁到此类公钥密码)。

Pollard的p-1分解算法:若p|n,则对r\in \Bbb (Z/n)^*r \neq 1(p-1)|kr^k/p=1,从而得到N的因子d=\mathrm{gcd}(r^k-1,N):熟知用二进制分解求次幂,用Euclid除法求gcd都相当高效。当然,困难在于我们并不知道p,否则问题已获解决!此处的诀窍在于猜测p-1的分解,例如很可能p-1=\prod p_i^{r_i}p_i^{r_i}\leq CC并不太大。于是可尝试着逐步增大C并令\displaystyle k=2^{[\log_2 C]}3^{[\log_3 C]}5^{[\log_5 C]}\cdots。缺陷在于:如果p是一个强素数p-1将包含大素因子,此时要选择很大的C才能见效。

Pollard  Theorems of Factorization and Primality Testing

上述是代数群分解算法的简单例子。一般的想法是构造代数群函子G_n,要求m|n时有(满)同态\phi_{n,m}:G_n \to G_m。任取非零元r\in G_n并对适当选择的k考察kr。若kr \in \mathrm{ker}\phi_{n,p},则往往能找到n的因子。

现在介绍Lenstra的椭圆曲线分解算法(ECM)。仍取椭圆曲线E:y^2=x^3+ax+ba,b \in \Bbb Z/n\mathrm{gcd}(\triangle(E),n)=1。任取r \in E,随机生成小素数的低次幂乘积k,计算kr。若p_1|np_2|n,由Hasse定理知|E(\Bbb Z/p_i)|p_i附近的随机数,它们有大量相同素因子的概率是很低的,故很可能选到某个k使得\phi_{n,p_1}(kr)=0\phi_{n,p_2}(kr)\neq 0,此时在E(\Bbb Z/n)上将出现kr无法计算的现象。仔细分析椭圆曲线的加法,就会发现问题在于求斜率时分母v\notin \Bbb (Z/n)^*,从而找到n的因子v

调整参数a,b|E(\Bbb Z/p)|也将随之改变,这就避免了|\Bbb (Z/p)^*|\equiv p-1因而难以应付强素数的尴尬。

Lenstra  Factoring integers with elliptic curves

已知的大数分解算法大多是亚指数级的,其中ECM排名第3(表现最好的是一般数域筛法(GNFS))。迄今为止利用ECM分解得到的50个最大的素因子参见这里

离散对数问题

与大数分解同样臭名昭著的是离散对数问题。给定有限交换群Gq阶元素g,以G_0g生成的循环子群,我们可以定义离散指数函数\exp_g: \Bbb Z/q \to G_0和离散对数函数\log_g: G_0 \to \Bbb Z/q。离散指数易于计算,计算离散对数则远为困难:这种难度差使得诸如Diffie-Hellman密钥交换(DH)、ElGamal加密术乃至数字签名算法(DSA)成为可能。

通用的算法都是指数级的(相对于输入数据的位数):如“大步-小步”(BSGS),Pohlig-Hellman算法袋鼠算法。对于有限域的乘法群,已知有更好的亚指数算法:指标计算以及数域和函数域上的筛法。对于有限域上的椭圆曲线,一般来说仅有指数级的算法可用。不过对于特定曲线,可以采用Menezes-Okamoto-Vanstone攻击(基于Weil配对)或Frey-Rück攻击(基于Tate-Lichtenbaum配对)将E(\Bbb Z/p)嵌入到有限域的乘法群中计算,因而在应用基于离散指数问题的椭圆曲线加密术时应尽量随机选择参数a,b

最后是几点补充:

(1)更一般的,可以选取超椭圆曲线Jacob簇作为待考察的代数交换群,由此发展出超椭圆曲线密码学。这是一个尚未成熟的领域。

(2)利用Shor的量子算法可以在多项式时间内求得大数分解和离散对数,量子计算机的前景因此显得格外诱人。我们希望有机会讨论这个问题。

参考文献 

算法数论的标准参考书是

Cohen  A course in Computional Algebraic Number Theory

专论椭圆曲线的有

Washington  Elliptic Curves: Number Theory and Cryptography

2种初等素性测试

(2)之所以想到介绍常用的素性测试,源于与王哲瑫学弟讨论Miller-Rabin算法。特此鸣谢。

(3)我并不轻视应用数学,只要结果是美的,深刻的。当然,通常来说实用与否才是决定性的判据。对此我的辩护词是:解决一个有重大实用价值的难题,这一征服行为本身往往就构成某种美感,所谓pour la gloire de L’esprit humain.

(5)行文中省略的技术细节可以在下面这篇介绍性文章中找到:

Schoof  Four primality testing algorithms

此文还介绍了另外2种常用素性测试:APR算法Atkin-Morain椭圆曲线素性测试。不过,它们背后的数学就远非“初等”的了。有机会的话,我们将另文介绍之。

Wiki上关于素性测试算法的资料经百十人锤炼,同样是可靠的信息源。

这种“提纯”的行为看似毫无必要,实则对己大为有利。而我微薄的愿望,是于人也有些许好处。

(7)\tilde{O}:以f(n)=\tilde{O}(g(n))f(n)=O(g(n)\log^k g(n))k为某常数。

(11)最朴素的素性测试基于Fermat小定理:对于a \in (\mathbb{Z}/n\mathbb{Z})^*a^{n-1} \equiv 1(\mathrm{mod} n)对素数n成立。找到不满足条件的a即排除了n为素数的可能性。利用n-1的二进制分解,对每个a的验证可以在对数级时间内完成。

这个算法的缺陷在于Fermat小定理的逆不真。事实上,存在以a为基的Fermat伪素数甚至绝对Fermat伪素数,后者可以通过一切基于Fermat小定理的测试。

一种可能的改进是Miller-Rabin算法。它基于如下简单事实:给定素数\displaystyle p=2^s d+1\forall a \in (\mathbb{Z}/p\mathbb{Z})^*,(a)对某个r \leq s-1\displaystyle a^{2^r d}=-1或(b)a^d=1

任取a \in (\mathbb{Z}/n\mathbb{Z})^*,若(a)(b)均不成立即可推断出n是合数。反之,能通过这一测试的n称为以a为基的强伪素数。令人欣慰的是不存在绝对强伪素数

这当然仍取决于运气,不过Rabin注意到如下正面结果:n>9时至多有\frac{1}{4}a使得n为以a为基的强伪素数。由此他提出一个随机算法:若n成功通过了十几次随机测试,则有充分的把握断定n为素数。

(13)假定广义Riemann猜想成立,Miller指出只需通过1 <a < 2\log^2(n)的测试即可证明n是素数。这个确定性算法的复杂度为\tilde{O}((\log^4(n)),简单高效。

Miller Riemann’s hypothesis and tests for primality

(17)经典的Solovay-Strassen素性测试基于类似的原理。其数学依据是当n为素数时有Euler恒等式a^{(n-1)/2}=(\frac{a}{n})(\mathrm{mod} n)成立。Euler-Jacobi伪素数出现的概率上界是1/2,因而它远不如Miller-Rabin算法可靠。

(19)2002年,Agrawal, Kayal和Saxena提出了煊赫一时的AKS素性测试。注意到n是素数当且仅当对所有0<k<nn整除\displaystyle \binom{n}{k},换言之,对所有(a,n)=1(x+a)^n \equiv x^n+a (\mathrm{mod} n)。这推广了Fermat小定理。

为降低验证此式的计算量,AKS建议先将左右同时模去某个x^r-1再进行比较。此处的关键是:若素数r选择得当,则仅需验证特定的a即可证明(较弱的)n是素数的幂。确切的条件是:(a)nr的阶至少是\log^2 n;(b)n的素因子均大于r;(c)对0 \leq a<r(x+a)^n \equiv x^n+a (\mathrm{mod} (n,x^r-1))

由此AKS设计了如下算法:(\alpha)若n是某个整数的幂,输出“合数”;(\beta)不断增大r直至满足(a),验证(b),不满足则输出“合数”;(\gamma)若r \geq n,输出“素数”;(\delta)验证(c),满足则输出“素数”,否则输出“合数”。

Agrawal,Kayal & Saxena  PRIMES is in P

(23)结合快速乘法,AKS算法的复杂度为\tilde{O}(\log^{12}(n))。经Lenstra和Pomerance改良后,算法的复杂度为\tilde{O}(\log^{6}(n))

Lenstra,Pomerance  Primality testing with Gaussian periods

AKS算法是第一个(*)不依赖于任何未证明猜想的、(**)多项式复杂度的(***)确定性素性测试算法(对Miller-Rabin算法来说,(*)(***)不可得兼)。3位作者因此赢得了06年的Gödel奖(理论计算机科学)和Fulkerson奖(离散数学)。