（计算数学专业论文）概率型与确定型素数生成算法及在密码学中的应用.pdf

a b s t r a c t 1 f i t l e ：1 1 圮a l g o r i t h mo f g e n e r a t i o no f 胁b a b l ep r i m e s 锄dd 明1 1 i t i v ep r i m e s 粕di t sa p p l i c a t i o i l si nt h ec 巧p t o l o 斟 m 萄o r ：c o m p u t a t i o n a lm a m e m a t i c s a b s 丁r a c t p r i m en 啪b e r st e s t i n ga n ds e a r c l l i n gt o g e t h e rw i t hi t s a p p l i c a t i o i l sa l w a y ss e e m st 0b ea c o m p e l l i n gt h e m ei nt h e 叫p t o l 吩l 皿e 仃a d i t i o m la l g 州t sf o rs 黜1 1 i n ga 1 1 dt e s t i n gp r i m e n 啪b e r si i l a i m yi n c l u d er a b i n - m - 1 1 e r 州m et e s t i n 舀s o l 0 v a 妒s 仃a s s e n 州m et e s t i n & e t c b m u 1 1 f ；d r t u n a t e l y t h e s em e c h o d sm e n t i o n e da b o v ea r e 翻1 e dp r o b a b i l n yt e s t i n 吕w 1 1 i c hm e a n st h e r 鹊u l tr e t 啪b yt h o s ea l g o f i t h m sc 锄b ep s e u d 伊p r i m e s0 t h e rt l l a nr lp r i m 器t h o u g ha k sp r i m e t e s t i n gi sad e f i i l i t i v ep r i m et e s t i n gm e t h o d b u ti ti sn o ts u i t e df 0 r p r a c t i c eb e c a u s eo fi t sl o w p e r f 0 1 1 1 1 a n c e t 1 1 i sp a p e ri n 仃o d u o 郎a 鹏wm e t h o df o rf i n d i n gd e f i n i t i v es a 危p r i m e s n e 州m e sf 0 咖db y t h j sm e 廿1 0 da r ee s p e c i a l l ys u k df o rt h ef a c t 粥u s e d mr s a c r y p t 0 1 0 趴d t oi t ss a f ep r o p e 咄 a l t h o u 曲甜sn o t 缸t e rt h a l ls o m ep r o b a b i l 时a l g o r i t l l i 璐，b l i ti ta i 衄a tc h e c k i n gp r i m e s0 fa 矗x e d m o d e ，s oi ti s 缸t e r 她nt h e 仃a u d i t i 0 越la k sa i g o r i t 量l i n st 0s o m ee x t e n t ，a n dt h ep r i m e sf 0 嘶d b y l i sm e t h o dm u s tb ed e f i m t i v ep r i m e s k e yw - o f d s ：p m e s ，c 呵p t o i o g y n u m b e rt h e o p r i m es e r i e sg e n c r a t i n 舀s a r 匆p r i m e s ，d e f i n i t i v e p r i m e s 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究作出重 要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声 明的法律结果由本人承担。 学位论文作者签名：滞币电 日期：1 年歹月1 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质 版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书 馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：诟钥地 月 日 | 第l 章引言 第1 章引言 随着计算机技术的飞速发展，互联网使用日益频繁，我们进入一个崭新的 信息时代。在这个时代里，我们大量使用信息，信息安全问题成为关系到国计民 生的大问题，引起各国政府到普罗大众的关注与重视。采取密码学的方法将信息 加密成为信息安全广泛运用的手段。我们注意到两个大的素数相乘其积十分容易 由计算机算出，但反过来知道这个积求其素因子就十分困难了。这个性质经常用 于编制密码。本文主要针对素数在密码学中的应用，提出两类可以生成确定性素 数的方法。下面首先简要地介绍一下密码学的概况，关于密码学的进展情况，可 以参阅文献 2 3 】。 1 1 密码学简介 密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观 规律，应用于编制密码以保守通信秘密的，称为编码学；应用于破译密码 以获取通信情报的，称为破译学，两者一起总称密码学。密码是通信双方 按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变 明文为密文，称为加密变换；变密文为明文，称为解密变换。密码在早期 仅对文字或数码进行加密变换和解密变换，随着通信技术的发展，对语音、 图像、数据等都可实施加密和解密变换。 密码学是在编码与破译的斗争实践中逐步发展起来的，并随着先进科 学技术的应用，已成为一门综合性的尖端技术科学。它与语言学、数学、 电子学、声学、信息论、计算机科学等有着广泛而密切的联系。它的现实 研究成果，特别是各国政府现用的密码编制及破译手段都具有高度的机密 性。 ， 进行加密变换的法则，称为密码的体制。指示这种变换的参数，称为密钥。 它们是密码编制的重要组成部分。密码体制的基本类型可以分为四种：错乱 按照规定的图形和线路，改变明文字母或数码等的位置成为密文；代替一用一 个或多个代替表将明文字母或数码等代替为密文；密本用预先编定的字母或 第1 章引言 数字密码组，代替一定的词组单词，变明文为密文；加乱用有限元素组成的 一串序列作为乱数，按规定的算法，同明文序列相结合变成密文。以上四种密码 体制，既可单独使用，也可混合使用，以编制出各种复杂度很高的实用密码。 1 2 密码学的应用 2 0 世纪7 0 年代以来，一些学者提出了公开密钥体制，即运用单向函数 的数学原理，以实现加密与解密之间密钥的分离。加密密钥是公开的，解 密密钥是保密的。这种新的密码体制，引起了密码学界的广泛注意和探讨。 利用文字和密码的规律，在一定条件下，采取各种技术手段，通过对 截取密文的分析，以求得明文，还原密码编制，即破译密码。破译不同强 度的密码，对条件的要求也不相同，甚至很不相同。 中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁 度等编撰武经总要“字验 记载，北宋前期，在作战中曾用一首五言 律诗的4 0 个汉字，分别代表4 0 种情况或要求，这种方式已具有了密本体 制的特点。 1 8 7 1 年，由上海大北水线电报公司选用6 8 9 9 个汉字，代以四码数字， 成为中国最初的商用明码本，同时也设计了由明码本改编为密本及进行加 乱的方法。在此基础上，逐步发展为各种比较复杂的密码。 在欧洲，公元前4 0 5 年，斯巴达的将领来山得使用了原始的错乱密码； 公元前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；之后逐步发 展为密本、多表代替及加乱等各种密码体制。 二十世纪初，产生了最初的可以实用的机械式和电动式密码机，同时 出现了商业密码机公司和市场。6 0 年代后，电子密码机得到较快的发展和 广泛的应用，使密码的发展进入了一个新的阶段。 密码破译是随着密码的使用而逐步产生和发展的。1 4 1 2 年，波斯人卡 勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到1 6 世纪末期， 欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有 了相当的发展。1 8 6 3 年普鲁士人卡西斯基所著密码和破译技术，以及 1 8 8 3 年法国人克尔克霍夫所著军事密码学等著作，都对密码学的理论 2 第1 章引言 计算机却十分容易。三位数学家们就是利用了这一点发明了编制容易而难于破译 的加密方法。这种编码方式以三位发明者姓氏的首字母命名为r s a 码。r s a 提出 后，三位发明家曾经公布了一条密码，称为r s a 一1 2 9 ，它是一个具有1 2 9 位数 的大数字，由一个6 4 位的素数与另外一个6 5 位的素数相乘而得到。 他们预言，人们至少需要2 0 0 0 0 年，才能破译这条密码，即使计算机性能提 高百倍，也需要2 0 0 年。虽然只是过了8 个月，这个密码就被人破译了，意思是： “t h em a g i cw o r d sa r es q u e a m i s ho s s i f r a g e ”( 挑食的秃鹰) ，不过之所以这 个密码如此快的破解，是因为全世界二十多个国家的六百多位工作者自发联合起 来，利用计算机网络，同时进行因式分解，并不断交流信息，汇总计算结果，用 了不到一年的时间，就将1 2 9 位的n 分解成6 4 位和6 5 位的两个素数的积。计算 机网络将分解效率提高了近万倍，这是发明者当初没有预想到的。但是，如果提 高位数到2 0 0 或3 0 0 位，工作量将会大的不可思议，即使计算机技术有重大突破， 破译也几乎不可能。由此可见素数在密码学中扮演着重要的角色，本文下面的章 节将会介绍素数在密码学中的各种应用，在这之前，有必要回顾一下数论的基础 知识，它是整个密码学的基石。 1 4 全文结构 本文的主要内容是素数在密码学中的应用，探讨用非概率算法检测素数和生 成素数的一种方法。全文共分为六章： 第一章是绪论，它是全面的总概，说明了密码学的起源，加密的手段，以及 密码学在应用领域的重要性。 第二章讲述了密码中要用到的基础知识，也就是初等数论的基础方法，特别 详细地介绍了f e r i n a t 定理，e u l e r 定理，w i l s o n 定理，中国剩余定理以及原根的 性质，鉴于二次互反率的重要性，本文还给出了二次互反率的详细证明。 第三章是总结现有的素数测试的成果，着重突出了现在比较流行的素数检测 的两个概率算法，m i l l e r 算法以及s 0 1 0 v a r y s t r a s s e n 算法，描述了a k s 算法的 详细流程，对比了各种算法之间的优点与不足之处，为第五章中一种新的搜索算 法的特出做了铺垫。 4 第1 章引言 第四章介绍素数在密码学中的具体应用以及各种流行的加密方法，举出的例 子使得抽象的理论能够结合实际，切入主题。 第五章是全文的创新点，文中提出一种可以生成确定性的素数的算法，并结 合现代密码学的需要，讨论了强素数的生成方法。 第六章是总结与展望，讨论了本文方法的不足之处，以及以后的努力方向。 本文列举和对比了多种素数测试的方法，阐述了现在用于检测素数的各种概 率算法的优点与缺点，利用初等数论以及抽象代数的基本理论为基础，提出 了一类确定型的素数的生成算法，以及两种多项式环上的概率型素数生成 算法。本文的确定型算法只生成某一特定类型的素数，从而在一定程度上 弥补了a k s 算法执行效率低的缺点，而且按照这种算法所生成的素数是安 全度较高的，因而它特别适合于用作r s a 密码体系中的素因子。 第嚣铺臻酗墓馥鞫i | 羹面露器量；三主主喜妻 萋= 主姜薹蒂矍藐萋蠢羹三雾鏊丝 型斋篓叱。坩囊薹翼前霪羹雩延扑影薹彗彗一 囊j 墅耋蓁蚕：薹霎羹霎囊冀蓁冀羹耋公；磊萋羹薹薹雾 隧墼奏薹霪羹茎霎囊蓁繁! 些篓鬟觏鋈霎囊篓冀蓁 蓁一鋈薹薹篓墓薹；蓁研蓁冀霎囊瑶雾霎箍萋霎篓 簿塞篓霎；急恿羹薹薹| 茎警雾霎萎季矗蓁乖奏鼍薹 雾篓囊；冀霎薹商基霎| 薹墓薹薹羹i 薹萋兰薹雾薹耋薹 冀蓄薹饕裹莱蟛蒌重蓁茎茎耋鏊囊奏霎主萎蚕鬟 薹奏i 三莓 挈i 薹霉手! 茧i ；耋1 乒霎霪量曩妻；零i ；塞鼋! l i 墓| 三霪 需望塞蠹璧蓁薹薹剁羹羹篓霎| 萋；诧薹錾萎蠹强翼塞薹面= 霎羹薹薹萋薹萎饽羹茎；雀萋萋蓁耋覆霎羹妻錾 冀篓篓蓁薹孳= 薹剩薹奏墓塞薹囊羹：雾羲霎碍薹盂竖羹萋琴完： 誊。季囊霎囊蓁誉萋靛毫耋鍪薹冀 霎蓁薹霉薹蓁耋尢蓁瑙薹霎鬟薹冀萋薹；奏霎薹薹誓r 薹萋荔蓁鬟薹基；鍪蓁羹噤雾蠹冀孽蓁蚌薹彗；漓 鍪季囊薹囊嘶篓，羹薹雾囊蓁蒌薹i 淫羹鍪薹霎蠹奏薹羹i 蓁丝荔篓囊需雾疆；翥篓雾薹蓥i 墓薹茎囊薹雾 薰i奏餮碧萋萋墓害氢囊孛蓁蚕萋薹霎萝 雩囊： 莹# l ! ；! i ；i | ；! ! i | i 薹；i i l * 趣薹l ! i ! 囊c o i 些i i ；i | 鬃；ij i i 耄雾雾委 薹l 够 塑 。 第2 章密码学的理论基础数论 作为本节的结尾，这里回顾一下著名的e 甜胁定理，f e r m a t 小定理与w i l s o n 定理。 引理2 1 ( f e r m a t ) 若a 是整数，p 是素数，则a p 三a ( m o d p ) 。 引理2 2 ( e u l e r ) 若a ，m 是整数，且( 口，聊) = 1 ，则【肼三a ( m o d m ) 。 这里证明e u l e r 定理，并把f e r m a t 定理作为眈彪，的特殊情形。 证明：取历的一组既约剩余系，i ，吃，彩( 掰) 。g a 于c a ，聊) = 1 ，所以 嘶，a t 2 ，( 研) 是，i ，眨，彩( 小) 的一个置换。 由前面性质的推论 1 7 a r t 三兀( m o d m ) 。再由消去n 。就得到圳- - = a ( m o d m ) 。当m 是素数时 就得到f e r m a t 定理。证毕。 引理2 3 ( w i l s o n ) 若p 1 ，则p 为素数的充要条件是( p 一1 ) ! 三一l ( m o d p ) 。 这个定理非常重要，下面证明必要性：如果p 为素数，且p = 2 ，那么自然有 1 三一l ( m o d 2 ) ，结论成立，若p 为大于2 的素数，对每个满足条件1 a p 一1 的 a ，由前面所述的模逆性质存在a 的模逆b ，使得a b 三l ( m o d p ) ，现在考虑一下 方程x 2 三l ( m o d p ) ，它等价于pi + 1 ) o 一1 ) ，因为p 为素数，这时必有pix + l 或p i x - 1 。当前者满足时x 兰p l ( m o d p ) ，后者满足时有工三l ( m o d p ) 。也就是 只有当x = 1 或x = p 一1 时同余式才成立。所以除了这两个数外，对1 口p - - 1 的 a ，均有不同于a 的数b 使得a b 三l ( m o d p ) 。把这些数按上面的方法两两配对， 最后两边同乘以l p 一1 ，就得蛩 ( p - 1 ) ! - - - - - l ( m o d p ) ，这就证明了w i l s o n 定理的 必要性，而充分性是十分简单的，这里不再赘述。 9 第2 章密码学的理论基础数论 2 2 中国剩余定理 中国剩余定理是数论里面一个比较优美而又实用的定理，在数论和密 码学的应用上面常常都会使用它。这里简单地证明如下： 引理2 4 ( 中国剩余定理) 设整数，l ，吃，r k 两两互素，那么同余方程 x 三a l ( m o d r l ) x 兰a s ( m o d r 2 ) x 三a k ( r o o d r k ) 有唯一的模，1 吃r k 的解。 证明：先证存在性，记m = 5 r 2 一l + l r k ，因为1 ，吃，r k 是两两互素的， 所以鸠与互素，于是由我们熟悉的e u c l i d 求最大公约数的辗转相除法可知， 存在整数鸩的模逆m ；- 1 使得m 何1 = l ( m o d ) 。于是，容易验证 x = a l m i m f l + a 2 m 2 m f l + + 鲰心坼1 ( m o d q r 2 r k ) 就是原方程的解。最后证明唯一性，如果有整数也满足定理的条件，那么可 以知道z 一兰o ( m o d r ) ，i = 1 ，2 ，k ，按照最小公倍数的性质得 x x 0 兰o ( m o d r l ，眨，吃】) ，再由，l ，吃，珞两两互素便知道下面的同余式 x 一确三o ( m o d f i r 2 r k ) 成立。证毕。 2 3 原根 原根的理论在初等数论中具有重要的理论价值，一方面，它与二次互 反律密不可分，是二次互反律的基础，另一方面，它可以推广到域的有限 1 0 第2 章密码学的理论基础数论 乘法群的本原元素。在抽象代数的理论中是一个有价值的具体实例，很多 定理的证明利用了原根的性质都能起到化繁为简的效果。原根有很多很有 趣的性质，尤其是它和指数的关系，密码学中利用离散对数加密的问题就 与原根有关。这里限于篇幅的问题不可能对它进行详细的讨论，但是也力 求去揭露它的基本性质。 首先在讨论原根之前要用到的一个概念称为阶。 定义设口和n 互素，那么满足同余式a 工兰l ( m o d n ) 的最小正整数x 称 为a 关于模聆的阶，记为o r d n a 。 性质如果口和行互素，且a ，n 满足同余式a y 三l ( m o d n ) ， 则有o r d n a ly 。 证明：利用带余数除法y = o r d , , a q + r ( 0 ，- 0 ，且如果o r d n a = ( 甩) ，那么称a 是模n 的 原根。 性质 如果口是m o d 刀的原根，那么口，口2 ，口( n ) = 1 是疗的一个既约剩余 系。 下面给出原根的存在性，但是由于篇幅所限不能给出详细证明，定理的完整 证明过程可以参阅参考文献 1 ， 5 ， 6 。 引理2 5 ( 原根存在定理) 素数p 必有原根，且形如2 ，4 ，p k , 2 p 七的数( p 为素数) 有原根，其他形式的 第2 章密码学的理论基础数论 数没有原根。 2 4g a u s s 二次互反律 本章的最后一个内容是g a u s s 所证明的著名定理二次互反律，二次互反 律被称为初等数论的基石。本文首先引入二次剩余的概念，导出l e g e n d r e 符 号及其计算方法，最后在本节的结尾引出二次互反律及l e g e n d r e 符号的推广 一一励6 f 符号。 要了解二次互反律，首先要知道二次剩余的概念。 定义如果m 是一正整数，a 是整数，且( 口，m ) = 1 ，如果同余方程 x 2 三a ( m o d m ) 有解，则称口是m 的二次剩余，否则称a 为m 的二次非剩余。 定义设p 是奇素数，口不能被口整除，那么神符号( 詈 定姚雌兰：篙篡黧 定义了l e g e n d r e 符号之后，下面来证明一个非常有用的引理，e 跆，准则。 三解刀砒符号b 可以用以下公式算出： 曙卜川 差c 羰菱喇。 证明：如果b 的值为1 ，那么同余方程x 2 三口( m 。d 力有解，设；t 是方程的 解，那么根据f e r m a t 定理，有 a ( v 一1 ) 7 2 三r 2 ( p 一1 ) 7 2 三r ( v 一1 ) 三l ( m o dp ) 。 1 2 第2 章密码学的理论基础数论 数列甜l ，甜2 ，“，与数列m ，v 2 ，u 是1 ，2 ，( p 一1 ) 2 的一个置换， ，最后得到式子 把等式两边取模2 ，得到 o 三丁( 口，p ) 一s ( m o d 2 ) ，最后由已经证明的g 口娜引理得到 睁c 卅卵以叫，= 警2 叫p ，一一删艇完。 有了以上的准备，最后来证明g 口娜二次互反律。 证明：考虑以o ，么，b ，c 为顶点的矩形似b c ，其中么= ( p 2 ，0 ) ， b = ( o ，g 2 ) ，c = ( p 2 ，g 2 ) 。容易由计算知道，矩形中不含边界的格点个数是 立专尘鱼詈旦。而且矩形的对角线不含任何格点，这是因为如果有格点( x ，y ) 位 于对角线上，应有等式= 弘成立，但是( p ，g ) = l ，推出pl 掣，但是由于是矩 形的内点且不为零，所以有( p ，弘) = 1 ，这是一个矛盾，从而可知矩形的对角线 不含任何格点。现在来考虑矩形的下三角形区倒c 内的格点个数，从下三角形 底边上的某一个整数点( ，0 ) ( 但是不含( ，o ) ) 开始垂直往上数，因为矩形的对 角线方程为= 职，所以当y 问p 】时格点就已经不在这个下三角形中了， 但是当y 问p 】时，格点还是落在下三角形，所以由( ，0 ) 开始往上数，一共 有【为p 】个点落在下三角形，把这些，按下标加起来就得到整个下三角形中的格 ( p 1 ) ，2 点，一共有 为p 】个，同理可以知道，上三角形区c 内的格点数有 一= l ( 口一1 ) 2 【归g 】个，于是结合前面已经算出的矩形的格点个数得到 1 6 得减相式两样 这 0 ，一 十 吩 。芦 一 声 = ，芦 + 叶 一 。芦 = 掣芦 知推以可又 叶 ，芦 2+ s p p 口 up 陀 删芦 l f 陀 舢闩 一 弘 删芦 ” ，州 2 + j p p 口r p = ， 川 一 口 第2 章密码学的理论基础数论 导卜川) 2 。 睁( 钟2 _ 1 ) 8 。 ( e ) 如果聊和丹是互素的奇整数，那么有彪6 f 符号的二次互反律 眺) = ( _ 1 ，譬掣魁 1 8 第3章素数的判断和测试下面将举例探讨它们。 试除法试除法的基本思想是基于一种初等的筛法，就是胁幻s 历阴p s 筛法， 对于任意正整数 1 ，用所有不超过的方根的素数去除。由素数定理知道，不超过打的素数大约有2 届l g 个，所以大约要进行2 届l g 次运算，这 个算法不是多项式算法，而且是低效的。m i l l e r 检测法 设为奇数，一l = 2 5 d 。s 0 且d 为奇数。 对于满足1 4 l 0 9 2n 成立； ( 3 ) 如果对某个a 有g ，以及1 ( a t 刀) 疗成立，输出为合数； ( 4 ) 如果n ，输出为素数； ( 5 ) 从口= l 到【2 驴) l o g n j 拄行判断： 如果( x + 口) r x r + a ( m o d x 厂一1 7 刀) ，输出n 为合数； 2 1 第3 章素数的判断和测试 ( 6 ) 输出为素数； 么髓算法给出了一个确定性的多项式时间的算法，非常有理论价值，然而实际 上却因为其比较繁琐和效率不高而很少使用。彳昭算法的主要证明思路是利用 了分圆域上的多项式的有关性质，关于么昭算法的详细讨论可以参阅参考资料 2 ， 7 ，那里有对这个算法的详细推导以及证明。 s 0 1 0 v a y - s 缸郁s e n 检测法这个检测方法与m i l l e r 检测法相似，也是一个概翠 算法，它的通过检测的几率比m i l l e r 检测法要大，也就是说检测的精度要比 m i l l e r 法的差，但是有时它用起来要比m i l l e r 检测法方便。由第二章的最后一节 所述已经知道，如果p 为奇素数，6 是与p 互素的整数，由e “彪，定理就有 ( 暑 三6 p - 1 ) 2 ( m 。d p ) 成立。所以，如果要判断一个整数，z 的素性，可以取一个整 数满足( 玩刀) = 1 的6 ，然后判断暗】三6 _ 1 ) ，2 ( m o d 刀) 是否成立。当然，同余式 的左边是如6 f 符号。我们称满足同余式曙 兰6 - 1 ) ，2 ( m 。d ，z ) 成立的奇合数刀是 以6 为基的e 甜彪，伪素数。如果同余式不成立，那么，z 必是合数。要得到 s 0 1 0 v a 弘s 仃a s s e n 检测法的正确性，需要以下引理： 引理3 1 如果万是一个奇整数，且不是完全平方数，那么至少存在个满 足1 6 以，( 6 ，聆) = 1 的整数6 ， 使得阱乩 l 咒j 证明：如果门是素数，由原根定理的推论已经知道结论的正确性。现在设以 为合数，因为，l 不是完全平方数，所以n 可以表示为，? = 矿j ，其中p 是奇素数， p 是正整数，( p ，s ) = 1 。设，是p 的原根，下面应用中国剩余定理去找一个满足 1 6 3 + 5 + 9 + 2 0 + 4 4 ，因而同余方程实际上就是方程 3 _ + 5 吃+ 9 x 3 + 2 0 确+ 4 4 x s = 6 9 ( m o d 8 9 ) ，而且由于方程的系数构成一个超递增 序列，容易解出( 而，x z ，x s ) = ( 0 ，1 ，0 ，1 ，1 ) ，这个解正是上面的非递增序列方程 2 3 x 1 + 6 8 吃+ 6 9 x 3 + 5 知- - i - 1 l x s = 8 4 的解。在对一条信息加密时，先把要加密的 部分转化为二进制的数字信息，再把这个数字信息分解为长度相同的段落，比如 说一个段落有1 0 0 个二进制数字，然后构造一个超递增序列( q ，a 2 ，a l o o ) ，选 择正整数w ，m ，满足对每个含有二进制信息( x l ，x z ，x l o o ) 的段落计算和式 1 0 0 s = 6 f 而，其中岛三w a i ( m o d m ) ，然后将序列( 6 l ，6 2 ，6 l o o ；s ) 作为公钥发送出 i = l 去，由于( 6 l ，6 2 ，岛o o ) 不是超递增的，求解极其困难，但是知道私钥沏，w ) 的人 拿到( 6 l ，6 2 ，6 1 0 0 ) 后立即计算哆三诼6 f ( m o d 聊) ， 把方程转化为 栉 滩三q _ ( m o d 聊) ，由于( q ，a 2 ，a 1 0 0 ) 是超递增的序列，所以在不到1 秒的 i = l 时间就能把这个段落的信息提取出来。但是近年来有专家发现背包密码不太适合 拿来当公钥密码，因为有人发现了当岛三w a ，( r o o d m ) 成立时( ( 口l ，a 2 ，) 超递 增) ，存在快速算法，使得能在多项式的时间内求解出( ，x 2 ，) ，从而使得 背包密码面临严重的威胁。关于背包密码的改进版本以及进一步的探讨可以参看 参考文献 9 】， 1o 】。 第5 章素数序列的生成以及安全素数 对任意的整数d ，2 g 2 0 的小正整数0 ，j f = 1 ，2 ，使 得b + i = 2 0 b + 1 为素数，对于固定的0 ： ( 2 1 ) 令g 卜2 ； ( 2 2 ) 如果g 易+ l _ 1 兰1 ( m o d 岛+ 1 ) ，g c d ( 吩一1 ，鲰1 ) = l ，其中巧毫9 2 。( m o d 办+ 1 ) ， 则跳出循环转( 3 ) ； ( 2 3 ) 令g 卜g + 1 ，如果g g o 则转( 2 2 ) 。 ( 3 ) 如果b + l 达到6 豇要求则输出p 卜b + l 否则f 卜f + 1 ，转( 2 ) 。 下列算法i i 把0 取为小素数。 算法i i 输入：要求生成素数的姗数；阀值g o ； 3 3 第5 章素数序列的生成以及安全素数 a ( 4 ，) + 卢j = l 。由中国剩余定理，取m = j ，鸩= 4 ，得到m 量p ( m o d 4 ，) ， 鸩一1 基a ( m o d s ) ，于是解出p 暑m m 一一鸩鸩暑s ( 卢+ 4 r ) 一4 r + 如s ) ， ( m o d 4 坶) 即p = s 卢一4 厂a + a 4 船= 1 8 旭+ a 4 坶，取九之2 p ， 原式化为 p = 1 + 8 ，( 脚一a ) ，由于，为素数，重而存在无限个整数j l l ，使得 g c d ( 8 ，j “s 一口) = 1 ，于是再按照定理5 1 的检测方法，如果整数p 通过检测，则 它就是素数，而且为安全素数。 这种处理的计算效率要比前面p 董5 ( i n o d 8 ) 的处理略高。 5 4 基于不可约多项式的素数测试方法 f 面提出一种新型的素性测试方法。许多素性测试方法都是基于欧拉定理 口p 一1 毫1 ( i n o d p ) 得到的，可以把口p 一1 暑1 ( m o d p ) 看成口是高次方程x p 一1 誊l ( m o d p ) 的解，但这个方程太简单，系数太少，因此有些伪素数永远无法用m r 测试排 除。为了更准确测试素数，我们在更广泛的多项式环上进行素性测试，其中要用 到不可约多项式。 下设p 为奇素数，0 x 】为系数在有限域0 上的多项式环。d e g ( 厂) 表示厂 ) 的次数。 定义5 2 称厂( x ) 0 【x 】为咒次不可约多项式，如不存在 石( x ) ，厶( x ) 名 x 】，d e g ( 石) 1 ，d e g ( 以) 1 ，使厂( x ) = 石( x ) 五( x ) 。 考虑三次多项式厂( x ) = x 3 + 6 l x 2 + 吃x + 6 3 ， 设= ( 2 j 1 6 2 ) 2 4 砰6 3 4 磋6 3 2 7 酵+ 1 8 6 1 6 2 6 3 ，其中如誊o ( m o dp ) 。 引理5 2 厂( x ) 为名 x 】上不可约多项式当且仅当 ( ，p ) = 1 与x p 一1 l ( m o d 厂( x ) ) 成立。 第5 章素数序列的生成以及安全素数 ( 6 ) 随机选择【1 ，刎中j 个数吩，计算y ( 乃+ m 2 + 朋+ 1 ) ，矿( 吩) 。如 矿( 乃+ 所2 + m + 1 ) 与y ( 吩) 厂( 乃) 不等则输出“m 非素数循环结束。 ( 7 ) f 卜f + 1 ，转( 2 ) 。 4 3 第6 章总结与展望 第6 章总结与展望 在密码学中，素数的检测和应用似乎是一个永恒的主题。数学家们在一方面 一直致力于寻找各种素数检测的有效方法，提高检测的效率，尽可能地降低时间 复杂度；在另一方面，数学家们把各种先进的数论研究成果运用到密码学中去， 数论与密码学这个应用数学分支结合成了亲密的伙伴，密码学得到了前所未有的 发展，成为了二十一世纪里面发展得最快，最令人瞩目的学科。但是在素数检测 的这