大整数因子分解问题的研究

《大整数因子分解问题的研究》由会员分享，可在线阅读，更多相关《大整数因子分解问题的研究（39页珍藏版）》请在金锄头文库上搜索。

1、武汉大学 硕士学位论文 大整数因子分解问题的研究 姓名：戴阔斌 申请学位级别：硕士 专业：基础数学 指导教师：陈建华 20040501 摘要 大整数因子分解问题( I F P ) 在近二十年引起了数学家、计算机科学家以及 密码学家的极大关注。其中的一个原因是在信息安全上得到广泛应用的R S A 密 码系统是建立在I F P 的难解性上。本文研究了各种大整数因子分解算法，包括 我们传统上的各种分解算法以及现代最常用的二次筛法( Q s ) 和数域筛法 ( N F S ) 。文中分析了各种算法优劣性，着重讨论了Q s 和N F S 的优化问题。最后 讨论了I F P 相关问题：R S A 密码系统

2、、R S A 问题、R S A 数、D L P 、E C D L P 、E C C 等 问题。目前为止I F P 还不存在多项式时间算法，人们也无法证明在将来有还是 没有多项式时间算法。今后I F P 的研究方向是在现有的分解算法的基础上寻求 分解过程的进一步优化和设计出适合高度并行化的算法和大型计算机来。I F P 的进展关系到R S A 密码系统的安全性，影响到国家的信息安全，它也促进了椭 圆曲线密码系统( E C C ) 的研究。 关键字：大整数因子分解；二次筛法；数域筛法；优化：信息安全。 A b s t r a c t L a r g ei n t e g e rf a c t o

3、r i n gp r o b l e m ( I F P ) h a sb e e na t t e n d i n gb ym a t h e m a t i c i a n s ， c o m p u t e rs c i e n t i s t sa n dc r y p t o g r a p h i s t si n f i n i t e l yi nt h er e c e n tt w e n t yy e a r s O n e r e a s o ni st h a tR S A c r y p t o s y s t e ma p p l i e dw i d e l y

4、i ni n f o r m a t i o ns e c u r i t yi sb a s e do n t h ed i f f i c u l t yo fI F EI nt h i sp a p e r , w er e s e a r c hk i n d so f i n t e g e rf a c t o r i n ga l g o r i t h m s ， w h i c hi n c l u d et r a d i t i o n a li n t e g e rf a c t o r i n ga l g o r i t h m sa n d q u a d r

5、a t i cs i e v ea l g o r i t h m ( Q S ) a n dn u m b e rf i e l d s i e v ea l g o r i t h m ( N F S ) i nc o m m o nu s e n o w a d a y s W e a n a l y z et h ea d v a n t a g e sa n dd i s a d v a n t a g e so f a l lk i n d so f a l g o H t h m s a n d e m p h a s i z e t h ed i s c u s s i o n

6、a b o u tt h eo p t i m i z a t i o n so fQ Sa n dN F S A tl a s tw ed i s c u s st h e r e l a t i v er e l a t i o n so fI F P ：R S Ac r y p t o s y s t e m ，R S Ap r o b l e m ，R S An u m b e r ，D L P , E C D L Pa n dE C Ce t c U n t i ln O WI F Ph a sn o p o l y n o m i a lt i m ea l g o r i t h

7、 m ，a n dW e C a n n o tp r o v ew h e t h e rw ec a nf m da na l g o r i t h mw h i c hh a sp o l y n o m i a lt i m e I nt h e f u t u r et h er e s e a r c hd i r e c t i o ni ss e e k i n gt h ef a c t o r i n g p r o c e s s f o rf u r t h e r o p t i m i z a t i o n o nt h eb a s i so fe x i s

8、 t i n ga l g o r i t h m s ，a n dd e s i g n i n ga na l g o r i t h ma d a p tt oh i g h e r p a r a l l e l T h e e v o l u t i o no fI F Pr e l a t e st ot h es e c u r i t yo fR S A c r y p t o s y s t e m ，a n d i n f l u e n c e sn a t i o n a li n f o r m a t i o ns e c u r i t y , a l s op

9、r o m o t e st h er e s e a r c ho f e l l i p t i cc u r v e c r y p t o s y s t e m ( E C C ) K e yw o r d s ：l a r g ei n t e g e rf a c t o r i n gp r o b l e m ；q u a d r a t i cs i e v e ；n u m b e rf i e l ds i e v e ； o p t i m i z a t i o n ；i n f o r m a t i o ns e c u r i t y 郑重声明 本人的学位论文

10、是在导师指导下独立完成的，学位论 文没有剽窃，抄袭，造假等违反学术道德，学术规范和侵权 行为，本人愿意承担由此而产生的法律后果和法律责任，特 此郑重声明。 学位论文作者签名：戴i 裁斌 2 0 0 4 年5 月 引言 大整数因子分解问题( I n t e g e r F a c t o r i n g P r o b l e m ，简记为I F P ) 是一个在数论、理论计算 机科学以及密码学上悬而未决的问题。引起数学家、计算机科学家及密码学家的极大关注是 近二十多年的事情，最直接的原因是因为一些密码体制及签名机制的安全性被认为是基于 I F P 的难解性。I F P 的任何一点进展都将引起密

11、码学家们的关注；I F P 属于N P 类。它是否存 在多项式时间算法是数学家及计算机科学家极其关注的；I F P 作为数论的一个基本问题直接 影响到数论及通讯领域币其它一些问题的解决，这也起我们关注它的原因之一。 最初人们用得最多的是试除法，就是用越来越大的素数来试除，直到得到所有的素因子 为止。试除法一直没有得到很好地提高，著名数学家F e r m a t 借助两个平方数的差： 口2 一b 2 = 0 6 + 6 ) 使分解技术得到很大地提高。虽然F e r m a t 法比试除法要快得多， 但遇到非常大的整数( 如几百位十进制数) 时，纯粹用F e r m a t 法显然是太慢了。一些分

12、解方法 出现了，如在1 9 8 7 年H L e n s t r a 1 提出的椭圆曲线法( E l l i p t i c C u r v e M e t h o d ，简记为E C M ) ； 在7 0 年代中期P o l l a r d 提出的一对概率算法：P 一1 法 2 】和P 法【3 】。目前最好的方法有连分 数分解法 4 】( C o n t i n u e dF r a c t i o nM e t h o d ，简记为C F M ) 、二次筛法 5 】( Q u a d r a t i cS i e v e 筒 记为Q s ) 和数域筛法【6 】( N u m b e r F

13、 i e l dS i e v e ，简记为N F S ) 。以上提到的算法我们将在第 一章和第二章里面详细介绍。 虽然I F P 还无法找到多项式时间算法，但一个引起巨大兴趣的、经验上的事实是：当一 个更快的整数分解算法能运行出来的话，在公钥密码学上最流行的R S A 算法【7 】将变得不荐 安全。 大整数因子分解算法基本上属于随机算法算法的运行时间都要好于最坏的情况，在大 多数情况下算法的时间是估计的而没有得到严格的证明。有些算法的时间复杂度依赖于所要 分解的整数n 的长度，有些是取决于分解出的最小因子P 的长度：属于前者的L e h m a n 算法 8 】的最坏时间为D G l 3 )

14、 ，c F M 算法和Q s 算法的为D ( e x p ( 五蕊) ) ( c 约为1 ) N F S 算法的为D ( e x p G ( 1 n n ) v 3 ( 1 n l n n ) V 3 ( c 约为1 9 2 2 3 ) ：属于后者的试除算法的为 D 咕( 1 。g 力) 2 ) ，P 。l l 。dp 法的 b O ( p v ：O o g ”) 2 ) ，E c M 的为o ( e x p ( 、层i 巧i 五面I l 。g n ) 2 ) ( 这里c 为约为2 ) 。 现代大整数分解是不可能在P C 机上完成的，往往需要很多处理器协同工作，于是人 们提出了并行算法人们设计

15、并行算法是期望在单处理器上算法所需时间为正而在P 个处 理器上所需时间为耳，要求乃约为正P 。往往不能达到如此好的效果，这是因为不可能 使P 个处理器都有效地工作。设一个并行算法的提高是s = 正耳，我们的目的就是为了s 有个线性提高，即s = D ( P ) 。并行算法的研究是I F P 中一个很值得研究的课题，它在Q s 算法和N F s 算法中得到了广泛琏应用。 I F P 存不存在多项式时间算法呢? 1 9 9 4 年S h o r ( 9 、【1 0 】) 提出了Q u a n m m 算法：这个算 法在量子计算机上存在多项式时间内分解出大整数来。尽管很多研究机构投入了很大努力， 但

16、这样的计算机依然无法遗出来，并且将来是否能造出来是一个很大的疑问。 I F P 涉及了数论、信息论、概率统计、计算机科学、密码学等科学领域，并得到了广泛 地研究和应用。对I F P 的研究促进了其他诸多学科的发展，丰富了其他学科的研究途径和方 法。本人研究了I F P 的各种分解方法，并作了优劣上的分析；对大整数分解算法的两种算 法：Q s 算法和N F $ 算法的优化问题做了讨论和分析 并讨论了I F P 相关问题。本文的安排 如下： 第一章主要介绍了传统的大整数分解方法。试除法是最简单方法，效率比较低，但判断 小因子比较快。P o a r d 提出的P 一1 和p 方法是两种概率方法，它的局限性在于要有小素因 子存在。椭圆曲线法是借助于椭圆曲线理论的，也是分解相对大整数的好方法。F e n n a t 方 法借助平方差得到非平凡因子，不过有时花费很多的时闯和存储空间，分解大整数有很大的 局限性。 第二章主要介绍了基于分解基的凡种大整数分解方法。首先介绍了M K r a i t c h i