雅克比和素性判别方法的软件实现

  • 格式:pdf
  • 大小:199.40 KB
  • 文档页数:4

第28卷 

Vo1.28 第l6期 

NO.16 计算机工程与设计 

Computer Engineering and Design 2007年8月 

Aug.2007 

雅克比和素性判别方法的软件实现 

何德彪, 陈建华, 胡志金 

(武汉大学数学与统计学院,湖北武汉430072) 

摘要:给出了一种确定性素性判别方法——雅克比和素性判别方法的软件实现,并对其中最关键的多项运算给出了一种 快速算法。同时,通过对另一种确定性素性判别方法——AKs算法的存储复杂度的分析,指出AKS算法在Pc机上实现的各 

种困难。最后给出了雅克比和素性判别算法在奔腾IV 1.8 G上的实现结果。 

关键词:素数:素性判别;雅克比和素性判别;AKS算法 中图法分类号:TP309.7 文献标识码:A 文章编号:1000—7024(2007)16—3818—04 

Software implementation of Jacobi sum primality test 

HE De.biao. CHEN Jian.hua,HU Zhidin 

(School of Mathematics and Statistics,Wuhan University,Wuhan 430072,China) 

Abstract:The software implementation of a determined primality test--the Jacobi sum primality test is described,and a fast method for polynomial modular multiplication is presented.At the same time,another determined primality test--AKS S algorithm is analysed, and the difficulty in implementing the AKS S algorithm on personal computer is pointed.At lasL the result of the implementation the 

Jacobi sum primality test algorithm on Pentium IV 1.8G is given. Key words:prime;primality test;Jacobi sum primality test;AKS 

0引 言 

素数自身无穷的魅力吸引着无数的数学家和数学爱好者 

们投身于素数的研究之中。早在大约公元前2500年,古乌鲁 克城的一位牧师就用楔形文字记下了一长串素数。古希腊和 

中国都独立地发展了素性检测Ⅲ。其中一种最简单且最著名 

的方法是埃拉托色尼素数筛法,由公元前3世纪的希腊天文 学家、数学家和地理学家埃拉托色尼所发明。 大约公元前500年,中国人发现,如果P为素数,则 一2 

能被P整除。1640年,法国数学家Fermat重新发现了比他早 

近两千年前的中国人发现的结果,并加以改进,创立了著名的 Fermat小定理。且在此基础上,发明了Fermat素性检测。 

近几十年,随着公钥密码学的广泛应用和计算机性能的 不断提高,素性检测得到迅速地推动与发展。1976年,Miller 

发表了被认为是第一种现代素性检测的方法叫。这种方法表 

明,在广义黎曼猜想的基础上,素性检测可在多项式时间内完 成。4年后,Rabin在Miller方法的基础上,发展了~种概率性 素性检测方法0 。 

这种方法不再依赖于广义黎曼猜想,但是有低于1/4 的概 

率会将合数检测成素数,其中k是算法中随机选取的测试整 数的个数。可见,如果选取适当多的k,既可以保证算法的准 

确性,也可以保证算法的速度。1977年,Solovay和Strassen发 表了第一种随机化素性检测方法 ,该方法也是建立在广义黎 曼猜想的基础上的。 

2002年8月,3位印度计算机科学家Manindra Agrawal、 

NeerajKayal和NitinSaxena发表了一种确定性算法,能够在多 项式时间内确定一个数是否为素数 。但是由于其所涉及的 计算量和存储量相当大,一般只能在特定的计算机上实现。 

其实,早在1984年,H.Cohen和H. Lenstra就在计算数 

学杂志上发表了一种确定性的素性检测方法 。该方法的计 算复杂度为O((1ogN)c。 ,它几乎也是一个多项式时间算法。 

而且它的计算主要是在z[纠域上,存储量和计算量都非常小, 因此适合在PC机上实现。 

目前,在工业界使用的素性判别方法都是Rabin.Miller方 法“ ,这种方法是概率性的,可能把合数判断为素数。随着ECC 

算法的推广,尤其是ECC在一些重大项目的应用,迫切需要 

一种确定性来保证所选素域一定是素域,椭圆曲线的阶必须 为素数。 

1 AKS算法和存储复杂度分析 

AKS算法 是一种确定性素性判别方法,而且运算量级是 

多项式数量级的,具体算法如下: 算法l:AKS算法。 

输入:整数n>l。 

收稿日期:2006—07-25 E-mail:hedebiao@163.corn 作者简介:何德彪(198O一),男,博士,研究方向为密码与信息安全:陈建华,博士生导师,研究方向为密码与信息安全; 胡志金,博士,研 究方向为密码与信息安全。 

・——3818-

—— 维普资讯 http://www.cqvip.com 输出:n是为素数或者合数。 (1)如果存在aEN,b>l,使得n=d,输出n为合数,结束; 

(2)找到最小的正整数,,使得0 >41og2n; (3)对于所有口≤r,计算 , ,如果l<(口, <n,输出n为合 

数,结束; (4)如果 ≤r,输出n为合数,结束; (5)对于所有的2≤口≤L2√ (r)lo J做如下运算:如果O 口) ≠ modx"一l, ),输出n为合数,结束; 

(6)输出n为素数。 文献【5】中给出的r的上界为log’n,文献【7-8】都具体实现 

了AKS算法,并且文献【6】给出了实现过程中r的上界为64 

log2n。如果要判别一个256比特的数是否为素数,那么在第5 步的约会过程中,存储一个多项式需要641og2nx256bit=-22*bit, 

这对PC机来说是不能接受的。而且该算法的运算量约为log6n, 

这也是不能接受的。 因此这种算法不可能在PC机上实现来满足公钥密码算 

法的要求。 

2雅克比和素性判别算法 

在1984年,H.Cohen和H.W Lcnstra在素性判别方面取 

得重大突破,发明了第1种可以具体操作的素性判别方法,计 算量约为(1o )~。如果要判别一个256比特的数,那么运算 

量大概为(1ogn) ,这与AKS算法相比,运算量大大减少,而且 实现过程中需要存储量很小,非常适合在PC机上实现,具体 

见算法2。 算法2:雅克比素性判别算法。 (1)预计算。在描述雅克比素性测试算法之前,先做以下 

预计算: 

找适当的t,并根据 f)=2 H 计算 f),使得e(f>B,其 

中 为待测素数所对应的上界。f的选取原则是使其素因子尽 

可能少,而且都是小素因子组成的,为二进制140位的数。计 

算雅克比和。 对每个 f)的奇素因子q,计算模q的原根 。由于q最大为 3361,其计算是很容易的。对1≤ ≤q一2,定义函 ),满足 l一 ; ’(modq),且l )≤q一2。对每个q,造表厂 )s。 

对每个q—l的素因子P,令 (g—1),定义特征 ,满足. 

(g; 》。令z ,则z为P 次单位根,且其满足的极小多项式为 

, )=n 一 。 

当 ≥3或者p_2,k-=2的时候,计算‘, ,q .∑ mI_ 

.∑ 州,将‘, ,g)在 对应的极小多项式尺z)上约化,结果仍 

记为J(p,q)。 下面如无特殊说明,形如‘, ,q)的关于z的多项式,都是经 

过约化其对应的极小多项式后得到的多项式。当 , ≥3时, 按上面公式计算 2,曰)。计算 

舶)=. 至一 . 三一2:产 ’ 

(g ) I7(2,qj,( ) 

J2(q)=j )=.三 . 三一 州) 

以上计算结果都通过造表存储起来,以便后面计算方 便取用。 (2)测试算法。 

输入:奇数N,Ⅳ≤ 。 

输出:判断Ⅳ为素数或者合数。 . 步骤l 对Ⅳ做20次Rabin.Miller检测,若Ⅳ为合数,输出 

合数,结束;否则转到步骤2。 步骤2 GCD检测。计算gcd=GCD(te(t),AO,若gcd>l,输 

出合数,结束;否则转到步骤3。 

步骤3 对每个t的素因子P,初始化 =0。当p≥3且 ≠ 

1(modp2)时,令厶=l,然后转到步骤4。 步骤4对每个满足 ll q-1 If的 ,q)对循环,如 ≥3, 

转到4(a);如果p=2, ≥3,转到4(b);如果 2,k=2,转到4(c);如 

果p=2,k=l,转到4(d)。 

(a)令E=(xEZIl≤ 枉)。令 ,其中 = 一.X‘ 

三l(mo({ ),r-N(mo({ ),a 磊 。然后计算 ・三‘, ,g) 

(modN),&三 (mod ̄,最后计算.S ,q)i ,q) (modN)。如果 

不存在 次单位根叩,使得 ,q)=r/(modN),则输出合数,结束, 

如果 存在并且为P 次原根,令 =l。 

(b)令El—h∈zIl≤ ,x--l或3(mod8)} 令O=-Zx ̄ ,r-N 

(mod2 ̄), ∑ ,然后计算 =J3(q) ̄(modN),s2-s ̄(modN) 

最后 2,q)=swr3(q)*32(q) ̄'(modN),其中当r∈E时, ,否则 

l。 注意到 l时,涉及到两个不同自变量对应多项式的乘 积,其中 (口)和J2(q)对应的自变量分别为zt=蠡和 =6,又 

≥3,则 一,故可以利用此式将 (q)的自变量对应为z1,便 

于计算。 

如果不存在 次单位根 ,使得S(2,q)=r/(mod^D,则输出合 数,结束;如果玎存在且它是2 次本原单位根时,又若q m三 

一l(mod4),则令厶=l。 

(c)令 -./(2,q) q(mo6V),&三 (modN),当N=1(mod4)时, 计算S(2,q)=s2(modN);当N=3(mod4)时, 2,q)-s ̄l(2,q) (modN)。 

如果不存在4次单位根 ,使得S(2,q)-r/(mod^D,则输出合 数,结束;如果 存在且它是4次本原单位根,即rl= ̄i时,又若 

曰 三一1(mod4),责令 =l。 (d)计算 2,q)三(一目) (modN),如果s(2,q)≠士l(modN),则 

输出合数,结束;否则,如果S(2,q)三一l(modN),且N-1(mod4) 

时,责令 =l。 若所有的 ,q)对通过步骤4没有输出合数,则转到步骤5。 

步骤5 检测 条件。若在所有的 ,q)对通过步骤4没有 输出合数,但还存在 =0时,此时还并不能说明 条件不成立。 

做以下计算: 

随机挑选一个素数q,使得qle(t),q三l(modp)且(q =l,这 样我们得到一个新的 ,q)对。 

根据 ,g)对值,执行4(a),4(b),4(c),4(d)。如果经过一定次 数,厶依然是零,则返回“无法判断N是否为素数”,否则转到