雅克比和素性判别方法的软件实现
- 格式: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是否为素数”,否则转到