用数域筛法分解大整数黄敬腾（北京师范大学珠海分校信息技术与软件工程学院0401010050）摘要:数域筛法是目前最快的(渐进意义下) 整数分解方法。

多项式选择则是该算法中的一个重要环节,它关系到整个算法的运算速度及所耗时间。

而影响多项式选择的两大因素———大小和根的属性,是多项式选择的关键。

本文对数域筛法中多项式大小进行了深入的分析,并通过严密的计算给出了不同情况下,多项式次数的取值范围。

关键词:整数分解;数域筛法;多项式的大小Polynomial Selection in the NumberField SieveJingteng Huang(Information Science & Technology Beijing normal university Zhuhai campus 0401010050) Abstract:The number field sieve (NFS) is the asymptotically fastest method known thus far. Polynomialselection is one important part in the number field sieve. It affects the speed and consuming time of thewhole algorithm. The key in the polynomial selection is the size of the polynomial . In this paper ,the authors analysis the size of the polynomial in detail , and present a way of choosing the degree of the polyno2mial .Key words :facting algorithm;number field sieve ;the size of polynomial一：引言众所周知, 早期的公开密钥RSA 系统之所以流行, 是因为它是建立在大整数的分解极其困难的理论基础之上, 因而使RSA 系统有很大的安全性。

然而, 随着整数分解算法的不断改进和计算机运算速度的加快, 人们对RSA 系统的安全性又产生了怀疑。

在二战期间, 英国间谍运用古老的大型计算机成功地破译了大量的德国军事情报, 为盟军战胜法西斯赢的了主动。

正是由于计算机的迅猛发展, 加密与解密的对抗和数论自身理论的提高, 整数分解的研究也就变得特别地活跃, 算法不断地得到改进。

攻击RSA 加密算法的一种主要手段是大整数分解。

为了校验当前大整数分解的能力(包括算法和计算机的计算能力) ,选择安全的RSA 参数,RSA公司从1991 年初开始,陆续公布了一系列关于大整数分解的挑战。

为此,计算数论专家发展了许多大整数分解算法, 例如: p + 1 方法、p - 1 方法、Pomerance 的二次筛法、Lenstra 的椭圆曲线分解方法、Pollard 和Pomerance 等数域筛法。

其中广义数域筛法是目前最有效的算法。

RSA 挑战的进展情况如表1 所示。

目前国际上最新的大数分解理论与技术,包括多项式选取、筛法、过滤、大规模稀疏线性方程组求解和代数数的平方根求解5 个步骤。

二：RSA算法简介1．RSA算法公钥，私钥产生a)随机选取的在素数P和Q，还有N ，其中N = P * Q ，P和Q保密，N公开。

b)F(N) = (P-1) * (Q-1)。

c)随机E，E满足（2<=E<=F(N)）, E作为公钥公开。

d)计算D, 使E*D=1(mod F(N)),称D为E对模F(N)的逆，D作为私钥保密。

2．RSA算法的加密解密（m为明文，c为密文）a)加密算法c=E(m)=m E(mod N)b)解密算法m=D(c)=c D(mod N)3．RSA算法的特点a)RSA算法的特点是非对称加密算法，通过两个素数P和Q产生公钥(E, N)公开和产生死钥(D, N)保密。

b)通过公钥加密的密文只有私钥可以解密，而通过私钥加密的密文只有公钥可以解迷。

加密解密是非对称的。

c)正是因为RSA算法的特点，因此他可以用于数字签字，防欺骗，防抵赖，在电子商务领域被广泛使用。

4．RSA算法的不足。

由于进行的都是大数计算，使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。

速度一直是RSA的缺陷。

一般来说只用于少量数据加密。

三：数域筛选的思想一般来说, 要把整数n 进行分解通常是找到两个整数x 和y , 满足x2≡y2 (mod n)。

然后计算gcd (x - y , n) , 如果gcd (x - y , n) = 1, 表示分解失败, 否则就找到了n 的两个真因子。

各种筛法所不同的是x ,y 的找法不一样。

数域筛法的思想是:1. 构造代数数域。

找一个次数为d > 1的首1不可约多项式f 和整数m , 使f (m ) ≡0 (mod n)。

设A是f 的一个根, 于是得到扩域K = Q (A) , 作映射U: Z [A]—→Z/n Z , 由A—→(m mod n)诱导出来。

2．找一个数对(a, b) 的非空集合S , 满足以下条件:i) 对所有(a, b) ∈S , gcd (a, b) = 1;ii) Π(a, b) ∈S (a+ bm )是Z 中的平方数;iii) Π(a, b) ∈S (a+ bA)是Z [A]中的平方数。

3.令x ∈Z 是ii) 中数的平方根, B∈Z [A]是iii) 中数的平方根, 令y∈Z 适合(y mod n) = U(B) , 那么我们得到y2≡x2mod n于是, 算出n 的因子gcd (x - y , n)。

四：数域的构造数域的构造实际上是不可约多项式f ∈Z [ x ]的构造。

在实践中, 对于十进制字节在110～160之间的数n, 宜取d = 5。

理论上d = ( (31/3 + o (1) ) logn / loglogn) 1/3 , n > 22d*d> 1.下面就介绍构造f 的两种方法:方法1如果存在一个比较小的整数a 可以表示为an= r e- s 的形式, 这里r, | s | 都是比较小的整数, 那么可以令k 是满足k * d >= e 的最小正整数, t= s*r k*d - e, 则得到多项式f = x d - t, 取m = r k满足f (m ) ≡0 mod n。

方法2以“基m n的方法找f 。

取r 是一个比较小的正整数,m = [ ( rn) 1/d ], 然后把rn 表示成m 进制R*n = c d m d + c d - 1m d - 1 + ⋯+ c0, 0 <= c i < m于是得到f = c d x d+ ⋯+ c0, 并且f (m ) ≡0 mod n。

选取Σd i= 0c i2比较小的作为我们的f 。

四：数域筛选的多项式时间分析定义1 若一整数的最大素因子小于或等于B ( B 为预先给定的整数) , 则称此整数为平滑B 数。

令F i ( x , y) = y d f i ( x/ y) , d = deg( f i) 。

在数域筛法中最关键的问题就是如何建立集合S ,我们的方法是通过收集Fi 的平滑值从而构建集合S :对于某个给定的平滑界B , 我们收集互素的整数对( a , b) , 使之满足: F1 ( a , b) 和F2 ( a ,b) 为平滑B 数。

这时我们称这样的整数对为一个关系。

通过线形代数的扩张,在这许多的关系中找出( a , b) ∈S ,使得Π( a , b ∈S) , F i ( a , b)在Z 中为一平方数。

而且由上式为一平方数可得到Π( a , b ∈S) , ( a - bαi )在Z[αi ]中也为一平方数β2 (证明方法见参考文献1 中2. 1. 2) 。

事实上,数域筛法中筛的过程就是确定整数对是否是关系的过程。

因为我们需要大量的平滑数, 而平滑数又非常的稀少,所以筛的过程在数域筛法中消耗了大部分的时间。

因此选择好的多项式,使之能产生大量平滑数,对于数域筛法来说是至关重要的。

下面我们介绍一种生成满足上述要求的多项式的方法。

(Montgomery)M- 基方法将大整数n 用m ( m ∈Z) 作为基分解为n = Σd i = 0a i(m) m i ,其中0 ≤a i( m) < m ,构建f ( x) :f ( x) = Σa i( m) x i则在数域筛法中, F1 ( x) = y d f ( x/ y) , F2 ( x) = x -my ,为所选择的多项式。

五：影响数域筛法中多项式大小的因素在数域筛法中,影响其中多项式的两个因素分别是:多项式的大小及它根的属性。

在此我们着重对多项式的大小进行讨论。

定义2 多项式的大小是指多项式取值的绝对值的大小。

数域筛法中,当多项式值为平滑数时,则满足F1 ( a , b)·F2 ( a , b) ≤( d + 1) m2 U d + 1≤2 d m2 U d + 1(1) 其中, d 是F1 的次数; U 是在筛的步骤中, 所定义的| a| 和b 的上界。

(证明方法见参考文献1 中2. 2)5.1F1为首一情况时的讨论在数域筛法中, 当F1 为首一时, 由m - 基方法有m≈N1/ d ,因此F1 ( a , b) ·F2 ( a , b) ≤2 d N2/ d U d + 1(2) 在参考文献2 中,选择最优的U 和平滑界B ,确保数域筛法的运行时间不超过:exp((1+o(1))(dlogd+((dlogd)2+4log(N1/ d)loglog(N1/d))1/2)) (3) 式中, 我们计算d , 来减少数域筛法所耗的时间。

可以看到计算(3) 式的最小值时,应有( dlog d) 2 =O(log( N1/ d) loglog( N1/ d) ) (4) 因此d 应有形式O(log( N) j loglog( N) k) ) (5)(4) 式中, d 的形式应和等式的右边对应,在忽略隐含系数的情况下我们得到( dlog d) 2≈log( N) 2 j loglog( N) 2 ( k + 1)(6) log( N1/ d) loglog( N1/ d) ≈log ( N) 1 - j loglog( N) 1 – k(7)在(6) 式和(7) 式中, 当N →∞时, 可得d 的渐进值为d = (31/ 3 + o (1) ) (logN/loglogN)1/ 3(8)5.2 F1不为首一情况时的讨论上面给出了F1 为首一时, 其最高次项的次数d 的取值,当F1 不为首一时,满足F1 ( a , b) ·F2 ( a , b) ≤2 dN2/ ( d + 1) U d + 1(9)同讨论F1 为首一时一样, 我们可得当F1 不为首一时数域筛法的运行时间不超过exp ( (1 + o (1) ) ( dlog d +(( dlog d) 2 + 4log( N1/ ( d + 1) )loglog( N1/ ( d + 1) ))1/2 ) ) (10)我们分解N 时,可由(10) 式看出,当上式取得最小值时 d 的取值等价于下式取得最小值时d 的取值ε(d,N)=dlogd +((dlogd)2+4log(N1/ ( d + 1))loglog(N1/ ( d + 1)))1/2 (11) 表 2 给出了当 d 选取不同值时,ε( d , N) 的变化情况。