算法数论中的椭圆曲线


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

约定以\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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s