有限域中的开平方算法

《有限域中的开平方算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3卷　第5期广州大学学报(自然科学版)Vol.3No.52004年　10月　JournalofGuangzhouUniversity(NaturalScienceEdition)Oct.2004文章编号:167124229(2004)0520392205有限域中的开平方算法12董军武,胡　磊(1.广州大学信息安全研究所,广东广州　510405;2.中国科学院研究生院信息安全国家重点实验室,北京　100037)2摘　要:提出了一种新的GF(p)上的开平方算法,与普通的开平方算法相比,该算法的计算速度有明显提高.关键词:有限域;平方剩余中图分类号:O1

2、53.4文献标识码:A　　在密码学尤其是公钥密码学中,经常用到有里从略.[1]限域中的开平方算法.Rabin算法中的解密要用定义1　设p>2为素数,gcd(a,p)=1,如果[2,3]到这个算法.椭圆曲线密码体制中要选择椭下面方程2圆曲线的基点,为了计算椭圆曲线上的基点,要用x≡a(modp)到开平方算法.同样在椭圆曲线密码系统中,不管有解,则称a为模p的二次剩余.否则,称a为模是加密后的密文信息还是对明文做签名后的信p的二次非剩余.息,都包含有椭圆曲线上的一个点,为了减少要传对于给定的a和素数p,当gcd(a,p)=1时,输的数据长度,表示椭圆曲线

3、上的一个点(x,y)有如下的判别法:时,可以采用压缩的方式(x,„y),其中„y是一个比定理1(Euler)　设p为素数,gcd(a,p)=1,[4]则a为模p的二次剩余的充分必要条件是特,而„y的计算需要开平方算法.p-1在计算有限域上椭圆曲线点数的SEA算法(a2≡1(modp)(1)2中,要用到有限域GF(p)和GF(l)中的开平方算更进一步,对于给定的素数p,我们可以写出法,对于后者,l是很小的素数(不超过1000).模p所有的二次剩余,即如下定理:近年来,基于双线性映射(如Tate对)的公钥定理2　设p>2为素数,则模p恰好有(p-[5,6

4、]密码系统成为研究的热点,在选择合适的椭圆1)/2个二次剩余和(p-1)/2个二次非剩余,而这曲线及基域时,特征p的二次扩域作为基域是比些二次剩余是较好的选择,也要用到有限域中开平方算法.222p-121,2,3,⋯,()(modp).基于有限域上开平方算法的广泛应用,本文2首先给出一些常用的开平方算法:GF(p)、GF(2m)为了讨论上的方便,还需要如下结果.上的开平方算法.然后对于基域GF(p2)的情形,定理3　当p≡±1(mod8)时,2为模p的二提出了一种新的效率比较高的开平方算法.最后次剩余,而当p≡±3(modp)时,2是模p的二次给出了

5、这个算法的复杂度分析.由于目前还没有非剩余.2一个多项式时间的寻找非平方元的算法,因此在定理4　设p为素数,方程x≡1(modp)有选择基域时,可根据需要选择合适的参数.且只有两个根x≡±1(modp).设f(x)为GF(2)上的m次不可约多项式,则m1　预备知识以f(x)为定义多项式可以构造有限域GF(2),m下面介绍GF(2)上迹的定义和性质.m本节介绍若干涉及初等数论和有限域方面的定义2　对任意α∈GF(2),定义α的迹为2m-1[7～9]222预备知识,所引用定理的证明都非常简单,这Tr(α)=α+α+α+⋯+α.　　收稿日期:2003-12

6、-19　　作者简介:董军武(1971-),男,讲师,硕士,主要从事信息安全和密码学研究.©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.　第5期董军武等:有限域中的开平方算法393m迹定义了一个从GF(2)到GF(2)上的线性模p的二次非剩余.寻找模p的非二次剩余时,函数,有:可以随机产生1

7、则继续.由定理2知,GF(P)中有一半Tr(α)+Tr(β);元素为模p的非二次剩余,因此上述方法重复nmn(2)对任意的c∈GF(2)及任意的α∈GF(2)成功的概率为1-(1/2).(p-1)/2有Tr(cα)=cTr(α);例2　设p=269,a=138,因为a=m2138134≡1(mod269),故a是模p二次剩余.计算(3)对任意的α∈GF(2)有Tr(α)=Tr(α).(p-1)/467u≡a≡138≡-1(mod269),由上述算法(p-1)/4(p+3)/867342GF(p)上的开平方算法可知x≡±2·a≡±2·138≡±262为

8、方程x≡138(modp)的解.讨论(3)p≡1(mod8)的情况GF(p)上方程sx2≡a(modp)(2