论文研究-大数因子分解算法综述.pdf

所需积分/C币:50 2019-07-22 23:17:03 865KB .PDF
57
收藏 收藏
举报

大数因子分解不仅是非对称加密算法RSA最直接的攻击手段,也是RSA安全性分析最关键的切入点,对其研究具有极其重要的应用和理论价值。主要概括了大数因子分解的研究现状,回顾了当前主流的大数因子分解算法,介绍了它们的基本原理和实现步骤;此外,对比分析了现有大数因子分解技术在实现和应用上的优缺点;最后分析并展望了大整数分解未来的研究趋势。
第11期 刘新星,等:大数因子分解算法综述 3203 率。基于蒙特卡罗方法, Brent等人卲在1981年成功地分解P-1平滑时才能分解N。同样地,ECM若能成功分解N,要求 了第8个费马数,找到了一个16位数字的因子。 加群的阶也是平滑的。如果某次尝试ECM没有成功分解N, 2.3P-1法 可以重复随机选择新的椭圆曲线来提高成功率,ECⅥ的期望 Pollard23在提出了p方法之后不久,还提出了另一种方运行时间是 法,称为P-1法。假设当N有质因子P,并且p-1是一个平 0(xp((2+0(1)(legp)2(leg吗gp)12) 滑数时,使用这种方法比较有效。 其中:P为N的最小素因子 P-1方法基于费马小定理,该定理是说,对于质数p和整 这个界是所有前面介绍的大整数因子分解算法中最好的 数a,当a与P互质时,有a”=1(modp)。根据这一定理,对个界,因此椭圆曲线是所有基于平滑性的分解算法中实际运 于任意整数k,有ap=1′=1(modp)。因此对于p-1的任行最快的。特别地,当N具有小素数因子时,ECM运行更快。 意倍数M,有a"=1(modp),即p整除a"-1,又p整除N,因此外,ECM还有一个显著的优点,即它占用的内存很少,而后 此pgcd(a"-1,N),通过求gd(a"-1,N)就有可能得到N的文要介绍基于组合同余的算法需要大量的存储单元。 因子。 Bren(2,38使用FCM分解了第|和第丨一费马数。2012 构造P-1的一个倍数M很简单,可以给定一个上界B,将年 Wagstaff使用ECM分解出了一个79位数的因子,这是 小于B的些质数或质数的幂乘起来得到M。这个方法还是ECM分解最好最新的记录3 有一定效果的,根据 Brent的介绍,通过P-1方法找到了 2-1的一个因子p2这是一个32位十进制数 3基于组合同余的因子分解算法 49858990580788843054012690078841 基于组合同余的思想为:得到平方同余式x2=y2(mx1N) 此时 左右两边的整数x和y,并通过计算gcdx±y,N)来得到非平 2-1=23×5×13×19×977×1231×4643 凡的因子。它们最终的目的都是找到两个整数x和y,x≠±y 74941×1045397X11535449 对于给定的上界B,执行一次P-1算法的时间复杂度为 (modN)使得x2=y2(mody),最后计算gcd(x+y,N)和gcd (x-y.M得到非平凡的因子。这种思想相对于试除、基于随 O(B× log b x loy2y)。P-1算法能否有效地找到N的因子,机数和基于费马小定理来说是一个全新的突破当前最优秀 取决于N的因子p-1是否是半滑的;最坏情况下,(p-1)/2 的二次筛法和数域法就是基丁这样的思想。 是个质数,此时P-1法不会优于试除法。 3.1基本概念 24椭圆曲线算法 在介绍基于组合同余这一类算法前,先介绍几个基本概念: 椭圓曲线方法( elliptic curve method,ECM)是 Lenstra26于 a)平滑性。数n说是平滑的( sMootH),如果对于n的所 1987年提出来的一种亚指数级复杂度的整数分解方法。这种有质因子P4,都有P≤R。 方法使用的想法与P-1法类似,两个算法成功分解的前提是 b)因子库。质数的集合F={P1,P2,…,Pn}称为因子库 它们的群的阶平滑,与P-1方法不同的是,ECM用随机选择( ctor base)。数n说是F上平滑的,如果n的所有质因子都 的椭圆线的加法群来取代P-1方法中的乘法群F FCM使用了椭圆曲线的群结构,假设N是被分解的数,所出现在F中。 机选择一条椭圆曲线E:y2=x2+ax2+bx3,如果(x,,x)满足3.2随机平方法 该方程,并且c≠0modp,则(cr,ey,cx)也满足该方程,因此(x, Dixon随机平方法为了能够有效进行整数因子分解,得到 ,2)和(,q,)可以看成是等价的。用(x:y)表示包含(x,同余式x=y(m),基本思想为:给定一个国子库F=ip, )一类等价点的等价类 P2,…,n},生成一系列的随机数r1>N,使得f(r;)=r2(md 在这个群F。中的加法零元O是(0:1:0),此时=0mdN)的左边在F上是平滑的。寻找足够多的这样的同佘式,并 P,即z是P的倍数因此在群E中,如果某一步运算得到了加选择这些同余式的个子集U,使得乘积中的怎个质因子的指 汰零元O=(x,y,),那么通过计算gd(N,z)就能得到个大数都是偶数形式,就得到了满足平方模N同余条件的x和y 于1的值,这样就可能将N分解。 接下来计算gcd(x±y,N)即可 设P1=(x1:y1:1)为椭圆曲线上的一点,nP1=P1+ 找到满足所需条件的集合U,就是寻找向量之问的线性相 P+…+P(共n个P1相加),记Pn=nP=(xn:yn:zn)。对于关。许多重要的算法,包括二次筛法数域筛法,最后都有寻找 大整数r米计算P,一般地,是所有小于给定上界B1的向量之间的线性相关的步骤,这种01矩阵是有限域GF(2)上 质数幂的乘积。群F、,的阶为g,如果g是B1幂平滑的,那么的大型稀疏矩阵,解决的办法可以采用高斯消元。1994年 显然有g1r,而有限群的元索的阶一定是群的阶的因子,因此 Coppersmith提出了 Block wiedemann算法,1995年Mont P等于加法零元,通过计算gcd(N,z)可以分解N gomery提出了 Block lanczos算法,这两种块形式的算法都 在 Pollard的P-1方法中,如果第一步处理屮算法没有成效缩减了高斯消元的复杂度。 功分解N,即p-1不是平滑的,那么可以转人第二步,即允许3.3二次筛法 P-1有一个质因子大于给定上界。基于同样的思想, Montgo- 二次筛法( quadratic sieve,Qs)13,3是20世纪80年代和 mery等人提出可以在ECM方法上加第二阶段的处理,改进后90年代初最为有效的一种方法,能够有效地处理十进制50 的FCM方法允许群E,的阶g有一个大于B1但小于B2的因100位的整数,包括了在因子库上寻找平滑整数、通过高斯消 子,这里0<B1<B2为预先给定的上界。 除法求向量相关性等步骤,是一种相对独立成熟的方法。该算 在P-1方法中,乘法群F的阶是p-1,这种方法只有法关键的一步,是用因子库里的质数对某个区间内的二次函数 ·3204· 计算机应月研究 笃31卷 值进行筛选,这也是该算法被称为二次筛法的原因。 行动计划。 次筛法的主要流程如下: 二次筛法的另一个改进是:允许Q(x)有一个不在F中的 )选择因子库F={p1,P2,…,pm}; 质因子q,q小于给定的界限B2这样,如果另外又找到了 b)定义多项式Q(x)=(x+「√N1)2-N,选择不同的x计算个Q(x)也是只有一个不在F中的质因子q,那么将这两个式 得到一系列的函数值Q(x),Q(x1),Q(x),…; ∫乘起来得到 c)采用筛法对这些函数值进行选,我出其中在F上平 Q(x)Q(x)=gs 滑的数值Q(x1),Q(x2),…,Q(x4); 其中:在F是平滑的。由于Q(x)Q(x')的因子分解式中q已 d)求0矩阵的线性相关性,得到一系列平滑值Q(x1),Q经是平方的形式,这样就可以把Q(x)Q(x)当成是F上平滑 (x2),…,Q(x4)后,对于每个同余式Q(x;),构造个m维向的来使用。二次筛法的这种变种可以节省约50%的计算时 量v,表示Q(x1)在因子库F中的各个质因子的指数的奇偶间,当然相应地会增大存储的需求。 性,如果能求得e;∈0,1},使得 二次筛法运行时间估计是 v1e1+v2e2+…+"e≡O、md2) O( exp((1+O( 1)( log N)( loglog N))) 那么那些e为1所对应的Q(x,)的乘积,就是一个完全平 二次筛汏的算汏特点是能够很好地进行并行化。在区间 方。这相当于求一组线性相关的向量v,如果向量的个数k大[a,进行筛选的过程可以在n个节点上并行处理,这只需要 丁向量的维数m,则一定能找到一组线性相关的向量,求解向给每个节点分配一个互不相交的区间,每个节点的区间内期望 量的相关性可以通过高斯消除法实现。 包括|m/n个平滑的Q(x)即可。但是,二次筛法还有另外 现在,假设得到Q(x,)Q(x,2)…Q(x,)是一个平方值个瓶颈,就是矩阵部分产生的大规楨的01稀疏矩阵,需要大量 取 的内存,普通计算机尢法满足。 (x,1+[)(x12+N])…(x,+[√N] 3.4数域筛法 那么x=y3(modN),最后求gd(x±y,N)即可。 数域缩法( number ficld sieve,NFS)138.由 Pollard于 寻找平滑值的过程中需要进行大量的除法运算,筛选是1993年提出,针对不同的分解对象,NFS分为特殊数域筛法 中计算量最大的部分,如图1所示,成为了整个算法的性能( pecial number field sieve,SNFS)和通用型数域筛法( general 瓶颈。 number field sieve,GNFS)。特殊数域筛法(SNFS)分解的整数 具有n=r±s的特殊形式,其中r和|s比较小,e可能很大。 般数域筛法(GNFS)则分解一般形式的整数。这里主要介绍 上,NHS一般指GNs,下文如果没有特别说明,N上S都表示 GNFS对二次筛法进行了扩展,允许更高次的多项式。当 然,所付出的代价不能像二次筛法那样,可以直观地、直接地得 martix 图1筛选部分耗时比例 到Z/NZ中的一个平方值 毫无疑问,若要提高整个算法的效率,必须有效减少筛诜 假设n是将被分解的数。首先,选择一个合适的多项式f 部分的计算量。在实际算法屮,二次筛法使用了一些技巧来进和有理整数m,使得f(m)≡0(modn),a是多项式∫的一个复 步减少除法运算。在筛选过程中,用log(Q(x)代替Q(x),数根。可以定义如下一个从R=丌[到整数域的一个环同态 用log(Q(x))-logP代替ρ(x)/即可。这里不必存储精确 q:R→Zn,即φ(a)=m(modn) 的对数值,只要存储估计值即可,最后扫描那些lg(Q(x))接则有 近于0的值。由于使用的是对数粗略值,因此会累积一些误 X2=(B)2=g(B2)=e(∏(a1+bc)) 差,log(Q(x))可能不会严格等于0。对于这些位置上的 ∏(a;+b,m)=Y2( mod n) Q(x),用因子库里的质数进行试除,进步判断是否是F上 这样求得同余式的X、Y即为所需。 的平滑数。同直接对所有Q(x)进行试除不同,由于只有极少 为了得到满足 的Q(x)可能是平滑的,这里试除的运算量几乎可以忽略不计。 ∏1(a2+6a)=B2 在基木二次筛法中只使用一个二次多项式,有一种较好的 ∏la+b,m=12 改进,这种改进的方法称为多重多项式二次筛法( mulliple pol ynomial quadratic sieve,wPs),31,是由 Montgomery在与P的整数对(a,b),需要将Za和z上平滑的概念结合起来,寻 menace0私人通信中提出来的。MS方法顾名思义,使找整数对(a,b)使得a+ha在za]的“代数因子库上平滑, 用了多个多项式,这些多项式形如 同时a+bm在Z的“有理”因子库上平滑。当找到足够的在两 Q(x)=ax2+2bx+c,其中Nb2-ae 个因子库上同时平滑的整数对之后,在Z[a]和Z上同时产生 这样 个平方值。 aQ(x)=a'x+2abx +ac 数域筛法可以分为如下几个步骤 ax+6)2-(b2-ac)=(ax+b)2mod A 1)选取多项式f1f2 1994年4月,来自多个国家的600名志愿者花了将近8个 多项式的选取是该算法中的个重要坏节,它直接影响着 月的时间,采用多重多项式二次筛法为RSA-1293找到了64后期关系对(a,b)的产量,对整个算法的运算时间影响很大 位数和65位数两个素数因子。这就是历史上著名的RSA-129通常这一步选择得到两个互质的多项式f√2,并且这两个多 第11期 刘新星,等:大数因子分解算法综述 3205· 项式模n时有相同的根。最简单的情况下使用M-基方法,即 被分解的模数过大时,矩阵将会变得很庞大,例如RSA n=∑c:m',0≤c;<m 768分解过程中,使用的矩阵达到了192,796,550×192,796, 550,普通PC机无法满足需求,这一步对庞大内存的需求,也 得到 是所有基于组合同余算法的瓶颈 f(x)=2cr, 6(x)=x-m 目前数域筛法中,矩阵求解都是采用 Block wiedemann或 可以发现1(m)=/2(m)=0mdn,2模n有相同的者 Block lanczos的算法。RSA-768团队大型稀疏矩阵192 根 7%6,550×192,7%6,550的求解就是采用 Block wiedeman。 如何选择好的多项式f12对,减少筛选时生成关系对(a 4)求平方根 b)的难度与耗时是近些年来的研究热点。现在的生成多项式 平方根的求解涉及到代数域。当找到∏(a.(a+b) 的方法分成线性和非线性两大类算法。所谓线性算法,即多项2,∏(b(a+bm)=y后,Y的值自然容易得出,X的值需要 式对f2中含有一个线性多项式,上面介绍的M-基方法就属求解Z0上的代数平方根,然后利用同态φ(B)=X得到 于这一类。线性算法在数域筛法发展初期就开始有相应的研1993年, Lenstra等人3介绍了求解平方根的步骤,Cou 究0,慢慢地 Montgomery和 Murphy以及 Kleinjung.,对gme5结合中国剩余定理,提出了新的求解平方根的方法。后 多项式选择进行了改进,这些改进成就了很多创记录的大数分者被使用得史广泛,不过它只造用多项式的次数为奇数的情况。 解,RSA-768就是最好的例子。采用线性类算法会导致两个多 数域筛法被认为是当前最好的因式分解算法,自1993年 项式指数差距大,因此寻找平滑数时在代数域上比有理数域上被提出后,不断刷新分解记录,创建了·个又个大数分解的 消耗的资源更多,会影响关系对的产生。与线性类算法正好相里程碑。 反,非线性算法2,4则选择两个指数相差不大或者一样的多 1996年, Cowie等人使用数域筛法分解了RSA512,意 项式,这样就平衡了两个多项式之间选择的平滑数的基和时味着从此RSA512将不再安伞;2009年12月,RSA7680被 间。实际上,由扌这种方式并没有被过多的实际工程采用,而成功分解,找到了两个二进制长度384位的因子,这是到目前 且限于目前的方法只能生两个二次多项式,因此,非线性算为上整数分解最好的成果。 法已绎落后于线性算法了。 除了一般形式的模数分解之外,还有类似于n=r′±s这样 2)筛选数对 特殊的数需要分解,通常采用特殊性数域筛法。2012年 在进行筛选工作前,需要确定三个基,a+ωm对应的冇理 Childers-2介绍了sNFs分解的梅森数21-1,这是特殊数域 因子基B1以及a+la对应的代数因子基B2,以及检验是否是法的一个里程碑,也是至今SNFS分解的最好的记录。其他 ZLc」中的一个完全平方值的二次特征基B3。 比较好的成果有2007年Aoki等人3分解的210-1 筛选出足够的(n,b)对,满足+加m和σ+hα都很大可能 数域筛法的时间复杂度为 在相应的因子基下完全分解。这一步进行了大量的除法操作 它是整个数域筛法中最耗时的部分。为了使得费时的除法运 exp|[0+o(1)( log N 1( log log N)23 I 算降到最低,一个很好的主意是用快速的加减法45取代通常 如同QS一样,NFS不可避免地拥有两个瓶颈,一个是寻 的除法。在检验B1上平滑性的时候,不是用除法运算,而是用找平滑数的效率,该部分占有整个过程约90%的时间;另一个 加减法排除大部分不平滑的α-加m值,只有当α+hm几乎肯是内存。NFS流程复杂,不像二次脩法和椭國曲线算法那样简 定是平滑的时候才使用试除法进行。所采用的簧略是:在筛选易,这也是近些年来;人们在分布式环境或者哽件环境下没有 数组中,存储的是hn(a-加m)的估计值,而非a+bm。根据对采用数域夼法的主要原因。 数运算的基本性质,将a+bm除以质数p,等价干从ln(a+ bm)中减去lnp,然后用B1中的质数进行试除,检验这些a+4对比与分析 bm的平滑性。 这科一般的算法就是绽筛,第一次被 Lenstra等人提出。4.1各类大数分解算法对比 1993年 Pollard在线筛的基础上进行了改进,提出了格筛的方 如上介绍的两类算法中,椭圆曲线和二次筛法适合分解中 法,上文介绍的降低除法运算的策略同样适用在柊筛里,现在各大等规模的整数,即二进制长度100~110位左右;数域筛法则适 工程项目,比如文献ˆ47]等,都是采用格筛。紧接着在19蚪4年,合分解大规模整数,这样的数一般大于110li。试除法和其他 ( Colliver等人郴在 Pollard的工作基础上加入了试除的操作,进一算法当前使用不多,适合分解规模比较小的整数。表2对各个 步改善了格筛的效率;此后在2005年, Franke等人则提出了在因式分解算法特点作了总结。结合各个算法的特点,它们的优 格筛的基础上采用连分数来改善筛诜的办法。 缺点分析如下 3)矩阵求解 a)P±1法,实质上是假定对于N的某个质因子pp±1是 与二次筛法一样,求解线性相关是为了得到平方数,不过平滑的因此能够通过一些同余式的特点,在较小的搜索范围内 这里需要得到有理数因子基B1和代数因子基B2下的两个平找出这个因子来,从这个意义十来说,试除法就可以称为P法 方数。求解方法与二次筛法一样。 因为该方法要求N具有一个较小的质因子p.也就是说P是平 定义σ(B为因子基B1的大小,那么三个因子基构成的滑的。RSA公钥密码算法,选择参数N=四,要求p-1,p+1 向量大小为丌(B)+丌(B2)+丌(B3),因此,至少要找到q-1,q+1应该有大质数因子,就是为了防止被P±1法攻击。 丌(B1)+丌、B2)+丌、B3)+1组关系(a,b),才能使ve1+ b)椭圆曲线算法相对于其他中等规模整数分解算法而 v2e2+…+vek=O(mod2)有解。 言,如Q5(或者MPQS),具有结构简单的特点,内存使用量也 3206 计算机应用研究 笃31卷 少,只不过通用性不够,不像QS(或者MPQS)那样任何整数都平滑值的方法,通过使用筛选的过程来得到平滑值,这是整数 可以分解。 分解技术方面的一个突破。GNFS的一个重要突破,是认识到 c)几乎所有的通过寻找形如x2=y2(modN)形式平方差不必像Don方法和QS方法那样限制使用二次多项式,也许 的大数因子分解方法,都使用了因子库、平滑、寻找Z/2Z上向某些三次、四次、五次甚至更高次的多项式,能比二次多项式产 量相关性等基本概念。妟想取得关键突破,必须用更少的吋间生更多的半滑值。 在因子库上产生更多平滑的值。例如,Q方法对Dion方法 根据上闻的分析,可以对各个算法的优点和缺点进行总结 的改进就是使用了不同的多项式,同时更重要的是改变了寻找如表3所示 表2典型大数分解算法的特点 算法名称 时间复东度 分解对象 试除法 O(√N) 小规模整数 P方法 O( N4logN) 小规模整数 方法 0(B x log B x loy2N 小规模整数 圆曲线算法(ECM) 0(e((万+0(1)(hgP)2( Ing log p)2)中等规嗅整数 次筛法(QS) 0( exp(( 1+0( 1))(log N)2( log Ing N)2)) 中等规嫫整数 数域筛法(GNFS 64 o(b)'(Ing N)3( loglog N) 大规模整数 表3典型大数分解算法优缺点比较 算法名称 优点 占 试除 筲单、并行度好,适合分解随机选取的或者拥有小质数因子的整数时间复杂度最高,只适用于分解小规模整数 P±l具有小质因子约数容易被分解 通用性不好,实用性不强 结构简单,内你使用量少,是所有基于平滑性的算法中运行最快的 通用性不够 并行度高,通用性强 内存需求高 SNFS 能够分解特殊型的中等规模和大规模整数,并行度灯 算法复杂,通用性不够,闪存需求高 GNFS分解大规模整数最快的算法,通用性高,并行度好,实用性强 算法复杂,内存需求高,工程难度大 4.2分析与展望 较了它们的优缺点,展望了大整数因子分解之路的发展趋势。 图2介绍∫过去十年,椭圆曲线算法(FCM)以及一般数参考文献: 域筛法(GNHS)和特殊数域脩法(SN上S)分解记录发展趋势。「1 RIVEST R L, SHAMIR A, ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communica tions of the acm,1978,21(2):120-126 .CM GNF [2 AGRAWAL M, KAYAL N, SAXENA N. PRIMES is in PI. An nals of Mathematics, 2004, 1 60(2): 781-79 图2ECⅥ和NFS分解记录 [3 RSA Laboratories. The RSA factoing Challenge[ EB/OL.(2013 从历史分解记录来看,随着计算机计算能力的扩大,差 http://www.emccom/emc-plus/rsa-labs/historical/the-rsa-facto 不多每10年会多分解掉100dgis的数。可以估计,在实 ring-challengehtm 用型的量子计算机没有闻世之前,只要拥有足够的人力和 [4 BONENBERCER D, KRONE M. Factorization of RSA[R I 财力,NFS可于2020年左右分解现在通行的RSA1024 Wolfenbiittel: Ostfalla Clniversity of Applied Sciences, 2010 (309dgis)。从实际情况来看,目前所拥有的算法存在算5 DANILOV S, POPOVYAN L. Factorization of Rs180.EBOU 法复杂性高、算法流程复杂、耗资巨大等实质性问题,硬件 IacR(2010-05-09).http://eprint.iacr.org/2010/270.pdf 加速大数分解的研究也停留在初始阶段,较好的成果仅仅 6 POPOVYAN I, TIMOFEEV A. RSA-190 factored[ EB/OL].(2010 只是对数域夼法作的一些改进,从1993年至今都没有在算 11-10).http://maths-people.anuedu.au/-bai/factor/rsa190.ht 法或架构上垮越性的进展。分解1024bit以上的 RSA nu- ber仍然是一项耗资巨大的工程难题,大整数分解问题仍然 7 KLEINJUN T. We have factored RSA200 by CNFS EB/OL 1 被认为是困难的。 2005-05-09).http://www.loriafr/-zimmerma/records/rsa200 从总体上看,未来大数分解研究方向会在并行的前提下, [8] PROPPER R. RSA-210 factored EB/OL].(2013-10-17)hip: / 尽可能提高系统效率,基于新的计算机体系结构设计出新的高 度并行的适合哽件的算法,采用专用硬件设备加速大整数分解 L9 BAl Shi, ' THOME E', ZIMMERMANN P. Factorisation of RSA-7U4 很有可能是未来整数分解新的发展方向。 with CADo-NFS[EB/OL].(20100509)[201207405].hp:/ e'prinl. laer. org/2012/369. plf 5结束语 [10 KLEIN.JUNG T, AOKI K, FRANKE L, et al. Factorization of a 768-bit RSA modulus[ C|//Advances in Cryptology. Berlin: Springer, 2010 对大整数因子分解的研究不仅具有挑战性还具有重要的 333-350 理论和应用价值,它涵盖的领域包括计算机科学、数论、代数、[1]付向群,鲍皖苏,周淳,等.具有高概率的整分量子算決 密码学。几百年来,众多优秀学者加入其研究行列,在算法上 [冂].电子学报,2011,39(1):35-39 取得了不错的进展,但仍然不清楚该难题属于哪个计算复杂性[12]DEⅤ G Ying-u, PAN Yan-bin. An algorithm for factoring integers 类。本文介绍了当前流行的大整数因子分解算法,详细分析比 [be/Olj.(2012-02-29).http://eprint.iacr.org/2012/097.pdf 第11期 刘新星,等:大数因子分解算法综述 3207 [13] BAI Shi, ZIMMERMANN P. Size optimization of sextic polyno [33 LANDQUIST E. The quadratic sieve factoring algorithm[C]//Ad thenumberfieldsieveleb/ol.(2012-12-03).http://hal.inria vances in Cryptology. Berlin: Springer, 1985: 169-182 fr/ docs/00176103/31/PDh [34 SILVERMAN R D. 'The multiple polynomial quadratic sieve.J] [14]李骏,分布式计算环境下大整数分解的研究[D].上海:上海交 Mathematics of Computation, 1987, 48(177): 329-339 通大学,2007 [35 GUAN D J. Experience in factoring large integers using quadratic [15 GIIEBREGIORGISII S T. Quadratic sieve integer factorization using sieve[R]. Kaohsiung: National Sun Yat-Sen University, 2005 Hadoop d. Stavanger: University of Stavanger, 2012 I 36 POMERANCE C. A tale of two sieves[ J. Notices of the American [16. TORDABLE J. Map Reduce for integer factorization[ EB/OL Mathematical Society, 1996, 43(1) (2010-01-04).http://www.jhvierlordable.com/files/maprerluce-[37AtkiNsD,GrafFM,LensTraAK,elal.themagicwordsare ForlntegerFactorization, pdf squeamish ossifrage C]//Advances in Cryptology. Berlin: Springer [17 ZIMMERMANN R, GUNEYSU T, PAAR C. High-performanee inte 1995:261-277 ger factoring with reconfigurable devices[C]//Proe of International [38 LENSTRA A K, Jr LENSTRA H W. The development of the number Conference on Field Programmable Logic and Applications. Washing- field sieve[ M]. Berlin Springer, 1993 ton DC: IEEE Computer Society, 2010:8388 [391 LANDQUIST E. The number field sieve factoring algorithm T [18] ATANASSOV E, GEORGIEV D, MANEV N L. ECM integer factor Kutztown: Kutztown University, 2002 vation on GPU cluster[ C.//Prmc of the 35th Inlernational Conven -[40 BL HLER J P, Jr LE\STRA H W, POMERANCE. C Factoring inle tion.2012:328-332 gers with the number field sieve[ M]//The Development of the um [19 LI Lei, HAN Wen-bao Hardware implemention of the pipeline arehi ber Field Sieve. Berlin: Springer, 1993: 50-94. tecture of integer factorization based on elliptic curve method [J] 41 MURPHY B A. Polynomial selection for the number field sieve int Journal of Information Engineering University, 2012, 13(1): 13- ger factorisation algorithm[ D. Canberra: Australian National Lniver [20 ARCHER C. GPU Integer factorisation with the quadratic sieve[D] [42 KLEINJUNG T. On polynomial selection for the general number field Bath: L. niversily of Bath, 2010 sieve[J].Mathematics of Computation, 2006, 75(256): 2037-2047 [21 IZU T, KOGURE J, SHIMOYAMA T. CAIRN: dedicated integer [43 KLEINJUNG T. Polynomial selection[C//Proc of CADO Workshop factoring devices[ C]//Proc of the 13th International Conference on on Integer Factorization. 2008 Network-based Information Systems. Washington DC: IEEE Computer [44 PREST T, ZIMMEMANN P. Non-linear polynomial selection for the Society,2010:558-563 number field sieve J] Journal of Symbolic Computation, 2012, 47 22 POLLARD J M. A Monte Carlo method for factorization.BIT Nu (4):401409 merical Mathematics, 1975, 15(3): 331-334 [45 CAVALLAR S, DODSON B, LENSTRA A K, et al. Factorization of a [23 BRENT R P. An improved Monte Carlo factorization algurithm[J] 512-bit RSA modulus[ C//Advances in Cryplology- EUROCRYPT BIT Numerical Mathematics, 1980, 20(2): 176-184 Berlin: Springer, 2000: 1-18 [24 BRENT R P, POLLARD J M. Factorization of the eighth Fermat [46 POLLARD J M. The lattice sieve[ M//The Development of the lumber J. Mathematics of Computation, 1981, 36(154):627 Number Field Sieve. Berlin: Springer, 1993: 43-49 [47 BAI Shi, GAUDRY P, KRUPPA A, et al. CADO-NFS, an implemen- [25 POLLARD J M. Theorems on factorization and primality testing J ationofthenumberfieldsieveEb/ol1.(2011-10-27).http://ca Mathematical Proceedings of the Cambridge Philosophical So- do-nfs. gforge inria. fr ciey,1974,76(3):521-528 [48 GOLLIVER R A, LENSTRA A K, MeLRLFY K S. I allire sieving [26 Ir LENSTRA H W. Factoring integers with elliptic curves[ I. An and trial division[C]//Proc of the lst International Symposium on nals of Mathematics. 1987, 126 (3 ): 64-73 Algorithmic Number Theory. Berlin: Springer, 1994: 18-27 [27 BRENT R D. Factorization of the tenth Fermat number[ J]. Mathe- [49 FRANKE J, KLEINJUNG T. Continued fractions and lattice sieving matics of Computation of the American Mathematical Society [C//Proc of the I st Workshop on Special-Purpose I lardware for At- 19%,68(225):429451 tacking Cryptographic Systems. 2005 [28 BRENT R. Factorization of the tenth and eleventh Fermat numbers [50 COUVEIGNES J M. Computing a square root for the number field [R]. Canberra: Aust ralian National University, 1996 sieve[ M] //The Developmenl of the Number Field sieve. Berlin [ 29] ZIMMERMANN P 50 largest factors found by ECM[ EB/OL J Springer, 1993: 95-10 [2013.http://www.loriafr/-zimmerma/records/top50.html [51 COWIE J, DODSON B, ELKENBRACHT-HUIZING R, et al. A world 30] COPPERSMITH D. Solving homogeneous linear equations over GF wide number field sieve factoring record: on to 512 bits[C]//Ad- (2)via block wiedemann algorithm J. Mathematics of Computa vances in Cryptology. Berlin: Springer, 1996: 382-394 ton,1994,62(205):333-350 52 CHILDERS G. Factorization of a 1061-bit number by the Special [31 MONTGOMERY P L. A block Lanczos algorithm for finding depend- NumberFieldSieveEb/oL.(2012-08-06).http://eprint.iacr ncies over GF(2)[C]//Advances in Cryptology. Berlin: Springer org/2012/444.pdf.2012:44 1995:106-120 [53 AOKI K, FRANKE L, KLEINJUNG T, et al. a kilobit special number I 32 POMERANCE C. The quadratic sieve factoring algorithm[ C|//Ad field sieve factorization[ C l// Advances in Cryptology. Berlin: Sprin vances in Cryptology. Berlin: Springer, 1985: 169-182 er.2007:1-12

...展开详情
试读 7P 论文研究-大数因子分解算法综述.pdf
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-大数因子分解算法综述.pdf 50积分/C币 立即下载
1/7
论文研究-大数因子分解算法综述.pdf第1页
论文研究-大数因子分解算法综述.pdf第2页

试读结束, 可继续读1页

50积分/C币 立即下载