（应用数学专业论文）计算数论中的几个问题.pdf

四川大学博士学位论文 摘要 计算数论中的几个问题 应用数学专业 博士研究生朱文余指导教师孙琦教授 本文共三章在第一章中，设n 是一个合数，玖表示模的剩余类环，r ) z 。h 是一个首一的k 次( 0 ) 不可约多项式我们引入n 是k 阶模r ( z ) 的 c a r m i c h a e l 数的定义，全体这样的数记为集q ，m 1 ，由此给出k 阶c a r m i c h a e l 数 集瞰：q = u g ，口) | r ( 。) 过全体z 。上的首一次0 i 可约多项式) 显然，g 表示通常的c a r m i c h a e l 数集我们得到了n g ，f 。) 的一个充分必要条件，进 而得到n 殴的一个充分必要条件我们分别对岛和岛进行了深入的讨论， 得到了n g 的一个更易计算的充分必要条件、n 岛的一个必要条件和 两个容易计算的充分条件我们还证明了6 1 垡q 、q 譬c a 、q 垡岛以及 l qj = o o ，部分回答了r b h a t t a c h a r j e e 和e p a n d e y 提出的两个问题 2 0 0 2 年，a g r a w a l 、k a y a l 和s a x e n a 成功地解决了多项式时间判别素数这一 著名的世界难题，他们给出了一个算法( 简称a k s 算法) ，该算法对输入整数是素 数还是合数进行判断，它是一个确定的多项式时间算法后来许多科学家对该算 法进行了改进，其中有一个比较好的改进是由b e m s t e i n 给出的( 简称b e m s t e i n 算法) 我们在第二章中主要以a k s 算法和b e m s t e i n 算法为中心，首先讨论a k s 算法和b e m s t e i n 算法的正确性，然后详细分析了这两种算法，对它们的每一步实 一t 一 四川大学博士学位论文 现给出了相应的算法，并利用c 语言和汇编语言实现了a k s 算法和b e m s t e i n 算法，并对算法的实现，提出一些改进 在第三章中，设n = p q ，p ，g 为奇素数，z 。是一个模n 的剩余类环，我们对 z 。上的椭圆曲线r ( o ，b ) 的基本性质进行了深入的讨论，给出了晶( n ，b ) 上存 在阶为螈= 2 c m 社耳( o ，6 ) ，社s o ( o ，6 ) ) 的点g 的一个充分必要条件，并给出例 子说明当日( n ，b ) 为循环群，蜀( n ，b ) 为非循环群，且对应的正j ( 。，b ) 上有阶为 矗 的点g 环z 。上的椭圆曲线e 。( n ，b ) 的q v 数字签名方案、s o m 密钥交换协 议与q v 密钥交换协议均选取_ e 。( o ，b ) 上的阶为坂的点g 作为公钥( 称g 为 基点) ，并且限定其对应的f ( d ，b ) 和日( n ，b ) 均为循环群，这就限制了只能选择 一类特殊的椭圆曲线( 。，b ) 构作数字签名方案和密钥交换协议我们通过选 取e j ( o ，b ) 上阶为l c m n 1 ，m ，) 的点作为基点得到了基于环z 。上的椭圆曲线的 一个数字签名方案和一个三方密钥交换协议，这里n ，和m ，分别为墨，( o b ) 和 日【口，b ) 的最大循环子群的阶我们提出的数字签名方案是对k m o v 方案和q v 方案的改进我们提出的一个三方密钥交换协议是对s o m 协议与q v 协议的改 进，并且有更多的z 。上的椭圆曲线可供选择 关键词 c a r m i c h a e l 数，广义c a r m i c h a e l 数，z 。吲上的不可约多项式，素数判 定，多项式时间算法，a k s 算法，b e m s t e i n 算法，环z 。，环z 。上的椭圆曲线，数字 签名方案，密钥交换协议 一i i 婴型奎兰蔓主兰垡堡塞 a b s t r a c t s e v e r a lp r o b l e m si nc o m p u t a t i o n a ln u m b e rt h e o r y m a j o r ：a p p l i e dm a t h e m a t i c s a u t h o r ：z h uw e n y us u p e r v i s o r ：s u nq i t h i sp a p e rc o n s i s t so ft h r e ec h a p t e r s i nc h a p t e rl ，w es u p p o s eni sac o m p o s i t e ，z 。i sr e s i d u ec l a s sr i n gm o dn ，r ( x ) z 。mi sam o n i ci r r e d u c i b l ep o l y n o m i a l o fd e g r e ek ( k o ) w eg i v ead e f i n i t i o nf o rni sg e n e r a l i z e dc a m l i c h a e ln u m b e r s o fo r d e rk m o d u l or ( z ) i sd e n o t e db yq ，r ( 1 s ow eg i v ea n o t h e rd e f i n i t i o nf o rc k ： 瓯= u 瓯，( 。) ir ( x ) a r e a l lm o n i ci r r e d u c i b l ep o l y n o m i a lo f d e g r e ek ( k 0 ) o v e r z n ) c l e a r l y ，c li st h eo r d i n a r i l yc a r m i c h a e ln u m b e r s w ea b t a i nan e c e s s a r ya n ds u f - f i c i e n tc o n d i t i o nf o rn q ，r m o r c o v e 5w eg e th o l do fan e c e s s a r ya n ds u f f i c i e n t c o n d i t i o nf o rn 晚w eg e th o l do f a ne a s i l yc a l c u l a t en e c e s s a r ya n ds t l 伍c i e n tc o n - d i t i o nf o rn g 2 ，an e c e s s a r yc o n d i t i o na n dt w oe a s i l yc a l c u l a t es u f f i c i e n tc o n d i t i o n f o rn gt h o r o u g hr e s e a r c h i n go nt h ep r o p e r t yo f 国a n d 凸i na d d i t i o n ，w ep r o v e q 垡伤，age 3 ，岛重ga n dl 岛i = o 。s o ，w e h a v ea n s w e r e dap a r to f t h et w o p r o b l e m so f r b h a t t a c h a r j e ea n dp p a n d e y i n2 0 0 2 ，a g r a w a l ，k a y a la n ds a x e n ap r e s e n t e dar e m a r k a b l ea l g o r i t h m ( t h ea k s a l g o r i t h m ) i tw a st h ed e t e r m i n i s t i cp o l y n o m i a l t i m ep r i m a l i t yt e s t i n ga l g o r i t h mt h a t d e t e r m i n e sw h e t h e ra ni n p u tn u m b e ri sp r i m eo r c o m p o s i t e a f t e rt h ea k sa l g o r i t h m w a sp o s e d ，m a n yr e s e a r c h e r si m p r o v e dt h ea k s a l g o r i t h m o n eo f t h eb e t t e ri m p r o v e - m e r i t sd u e dt 0b e m s t e i n ( t h eb e m s t e i na l g o r i t h m ) i nc h a r p e r2 ，w ec e n t e ra r o u n dt h e a k sa l g o r i t h ma n dt h eb e r n s t e i na l g o r i t h m 。t h ef i r s tt a s ki ss h o w i n gt h ec o r r e c t n e s s o f t h et w oa l g o r i t h m t h es e c o n dt a s ki sa n a l y z et h et w oa l g o r i t h mi nd e t a i l f o re a c h s t e pi m p l e m e n t a t i o nw eg i v ead e t a i l e da l g o r i t h m w ed e m o n s t r a t es o m ea m e l i o r a t i o nt h a tw ei m p l e m e n tt h ea k sa l g o r i t h ma n dt h eb e r n s t e i na l g o r i t h mb yu s i n gc l a n g u a g ea n da s s e m b l el a n g u a g eo nm ym a c h i n e ， l i l 四川大学博士学位论文 i nc h a p t e r3 ，w es u p p o s en = p qa n dp ，qa r eo d dp r i m e s ，z ni sr e s i d u ec l a s sr i n g m o dn w ed i s c u s ss o m ef u n d a m e n t a lp r o p e r t i e so fe l l i p t i cc u r v e so v e rr i n gz ni nd e t a i l w ep r o p o s ean e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nu n d e rw h i c he n ( o jb ) h a sap o i n t o f o r d e r 螈= f 僻岛( d ，6 ) ，存岛( 口，6 ) ) a n ds h o w b y a ne x a m p l e t h a t ba ，6 ) m a y h a v eap o i n tgo f o r d e r 螈e v e ni f 日( n ，b ) i sac y c l i cg r o u pa n d 蜀( ，b ) i sn o t q v d i g i t a ls i g n a t u r es c h e m e ，s o mk e ye x c h a n g ep r o t o c o la n dq vk e ye x c h a n g ep r o t o c o l w e r eb a s e do na ne l l i p t i cc u r v e 日( a ，b ) o v e rt h er i n g w i t hap o i n tgo f o r d e r 峨( g i sb a s ep o i n ot h e yp o i n t e do u tt h a ts u c hab a s ep o i n tge x i s t si f 岛a ，b ) a n d 岛a ，b ) a r eb o t hc y c l i cg r o u p st h i sr e s t r i c t st h ec h o i c eo fe l l i p t i cc u r v e su s e dt oi m p l e m e n t t h e i rd i g i t a ls i g n a t u r es c h e m ea n dk e ye x c h a n g ep r o t o c o l s a n dw eg i v ean e wd i g i t a l s i g n a t u r es c h e m ea n dan e wt h r e eo rm o r eu s e r sk e ye x c h a n g ep r o t o c o lw i t hap o i n to f o r d e ri c m n l ，m 1 ) a sb a s ep o i n t ，w h e r en l ，m 1a r er e s p e c t i v e l yt h eo r d e ro f t h em a x i m a lc y c l i cs u b g r o u p so fb ( 。，b ) a n d 局( o ，6 ) o u rd i g i t a ls i g n a t u r es c h e m ei m p r o v e s k m o va n dq v s c h e m e ，o u rk e ye x c h a n g ep r o t o c o li m p r o v e ss o ma n dq vp r o t o c o l s o u rg e n e r a l i z a t i o nm a k e si tp o s s i b l et oc h o o s em o r ee l l i p t i cc u r v e so v e rt h er i n gz nt o e s t a b l i s hd i g i t a ls i g n a t u r es c h e m ea n dk e ye x c h a n g ep r o t o c o l k e yw o r d s ： c a r m i c h a e ln u m b e r s ，g e n e r a l i z e dc a r m i c h a e ln u m b e r s ，i r r e d u c i b l e p o l y n o m i a lo v e rz n ，p o l y n o m i a l t i m ea l g o r i t h m ，p r i m a l i t yt e s t i n g ，a k sa l g o r i t h m ， b e r n s t e i na l g o r i t h m ，r i n gz n ，e l l i p t i cc h i v e so v e rz n ，d i g i t a ls i g n a t u r es c h e m e ，k e y e x c h a n g ep r o t o c 0 1 i v 四川大学博士学位论文 前言 计算数论一直是数论的一个重要分支近年来，由于计算机密码学和编码学 的迅速发展，使得对计算数论的研究十分活跃 在本文中，我们用三章分别研究了计算数论中的几个问题：广义c a r r n i c h a e l 数g 的性质与计算，多项式时间素性判别，环z 。上的椭圆曲线f l n ( 。，b ) 中有关 点运算和求点阶数的计算问题，基于环z 。上椭圆曲线_ ( o ，b ) 的数字签名方案 和密钥交换协议， r b h a t t a c h a r j e e 和p p a n d e y 在文 3 中主要讨论阶广义c a r m i c h a e l 数集 g 的若干性质，同时也提出了有关g 的一些未解决的问题，其中两个问题是： 1 ) g g + 1 是否成立? 2 ) 是否对于某些k ，i c f 0 ) 次不可约多项式，如果对v f ( x ) z 。，有 ，( z ) 舻i ，( r o o dr ( z ) )( o 0 1 ) 则称n 是一个阶模r ( z ) 的c a r m i c h a e l 数，全体这样的数记为瓯，( 。) 显然 c 1 ，( 。) 即为通常的c a r m i c h a e l 数之集，记为c 1 设 q = u g ，( 。) ir ( z ) 过全体z 。上的首一女次不可约多项式) ， ( oo2 ) 瓯称为阶c a r m i c h a e l 数集 容易看出，我们通过引入数集g ，( 它显然是g 的一个子集) 来定义数集 瓯，与【3 】中所定义的晚是相同的，但更为合理，刻划瓯也更清楚利用该定义 一1 一 四川大学博士学位论文 我们得到了n g ，( 。) 的一个充分必要条件，进而得到n c k 的一个充分必要 条件1 4 定理1 1 4 1 设n 是一个合数，r ( x ) z 。吲是一个首一的k ( k 0 ) 次不可 约多项式，则n eq ，( 。) 当且仅当 1 ) n = p i p 2 - p “其中t 2 ，p i 为不同的素数，【i = 1 ，- 一，t ) ；( 0 0 3 ) 2 ) 对9 2 的每一个素因子p ，有 p 忆1 弦1 ，j = l ，5 ，= k ， ( o0 4 ) j = 1 这里r ( z ) = r l ( x ) n ( 。) 是r ( z ) 在f p x 】上的分解式，o ( z ) 是嵋h 中首一的 不可约多项式，且两两不同，d e g ( r j ( x ) ) ：f j ，j = 1 ，8 推论1 1 4 1 设1 9 , 是一个合数，则nec k 的充分必要条件是存在一个z 。上 的首一k 次不可约多项式r ) ，使得n 瓯咖1 更进一步我们讨论了2 阶c a r m i c h a e t 数的性质，得到了n c 2 的一个更易 计算的充分必要条件1 4 定理1 2 1 4 1设 2 是一个合数，则neq 的充要条件是： 1 ) n 无平方因子： 2 ) 对v p l n ，均有p 一1 i n 2 1 ； 3 ) 至少存在一个p ，p i n ，使得p 2 1l n 2 一l 利用该充要条件我们证明了c - 譬c 2 和j c 2 = o o 部分回答了 3 1 中提出的 上述两个问题 更进一步我们在第一章第三节讨论了3 阶c a r m i c h a e l 数的性质，得到了 n c 3 的一个必要条件( 定理1 3 ) 和两个容易计算的充分条件( 定理1 4 和定理 1 5 、吼 一2 四川大学博士学位论文 定理1 5 设n 是一个合数，n = q 兀a ，这里g ，p i ，i = 1 ，s 是不同的素 数，如果qel ( m o d 3 ) ，p il ( m o d l 2 ) 或p ii7 ( r o o d l 2 ) ，且满足以下条件： t ) q 3 1 | n 3 一l ： 2 ) p l 一1l 舻一1 ，i = 1 ，s ， 贝0n c a 利用定理1 5 我们得到了q 鐾c 3 、c 2 霆国，部分回答了【”中提出的一个 问题，对于3 阶c a r m i c h a e l 数，我们提出了三个未解决的问题 众所周知，素数地产生与判定在密码学中有很重要的应用前景，许多密码算 法的实现首先就需要选择大素数( 如r s a 公钥密码体制中素数p ，q 的选取) ，大 约公元前2 5 0 年，古希腊数学家( e r a t o s t h e n e s ) 首先提出了一种判断一个数是否 素数的简单方法，后来人们把它称为厄拉多塞筛法但随着数字的增大，使用这 种方法所需的时间成指数增长近几十年来，数学家们一直试图寻找一种“多项 式时间”算法，以便在合理时间里解决问题在a k s 算法出现以前的素数判定， 从试除法到概率性素数产生法，均不完善，前者不能在多项式时间内完成，而后 者又是一种非确定性的算法目前在密码算法实现中所采用的素数判定法f 如 m i l l e r - r a b i n 测试) 均为概率算法，虽然快捷，但毕竟不是百分之百的可靠 直到2 0 0 2 年，a g r a w a l 、k a y a l 和s a x e n a 【1 】成功地解决了多项式时间判别 素数这一著名的世界难题，在文 1 中给出了这一著名算法( 简称a k s 算法) ，该 算法对输入整数是素数还是合数进行判断，它是一个确定的多项式时间算法，所 需时间为6 0 0 9 ”n ) 1 7 1 有关a k s 算法对现代密码学的影响见 i s , j9 1 后来许 多科学家对该算法进行了改进( l e n s t r a2 0 0 2 2 0 l ，p o m e r a n c e2 0 0 2 口”，b e r r i z b e i t i a 2 0 0 31 2 2 ，c h e n g2 0 0 31 2 3 1 ，b e m s t e i n2 0 0 3 a b 2 4 t 2 5 3 ，l e n s t r aa n dp o m e r a n c e2 0 0 31 2 6 ) 我们在第二章中主要以a k s 算法和b e m s t e i n 算法为中心，首先讨论a k s 算法 和b e r n s t e i n 算法的正确性，然后详细分析了这两种算法，对它们的每一步实现 给出了相应的算法，我们分别用c 语言【2 7 】和汇编语言【2 8 】实现，由此可看出 b e m s t e i n 算法比a k s 算法要好，并对算法的实现提出一些改进 我们在第三章中对z 。上椭圆曲线晶( o ，b ) 的基本性质进行了深入的 婴型盔堂堡主堂垡堡茎 讨论，在我们给出的运算定义下，b ( 。，6 ) 虽不构成群，但具有类似于有限 群的性质，可应用到密码算法中去我们给出了b ( o ，上存在阶为眠= 2 c m 社岛( d ，6 ) ，# e q ( a ，6 ) ) 的点g 的一个充分必要条件，并给出一个例子，其中 日( 。，b ) 为循环群，e q ( a ，b ) 为非循环群，且对应的b ( n ，b ) 上有阶为呱的点g ， 设 马( 。，6 ) 掣z n - z n ：，其中“2 i “1 ，”2 i 一 f o o 5 1 e q ( 口，b ) 型z m l z m 2 ，其中m 2 i m l ，m 2 i ( g 一1 ) 、 。 定理3 8 1 4 1 1 设不( 8 ，b ) 为环z 。上盼椭圆曲线，( 4 8 3 + 2 7 b 2 ，n ) = 1 ，= p q ， p ，q 均为大于3 的素数，岛( o ，b ) 和局( n ，b ) 满足( o 0 5 ) 式，则e 。( 8 ，b ) 上存在阶 为尬。的点g 的充分必要条件是l c m n l ，m 1 = l c m n l n 2 ，m 1 m 2 ) 关于基于环z 。上椭圆曲线的数字签名方案和密钥交换协议的研究，1 9 9 2 年 k k o y a m a ，u ，m a u r e r , t o k a m o t o ，s v a n s t o n e p 9 j 提出了基于环z 。上的椭圆曲线 的数字签名方案( 简称k m o v 方案) 2 0 0 0 年，m i n g h u aq u 和sv a n s t o n e 4 3 3 又推 出一个没有同态特性的基于环z 。上的椭圆曲线的数字签名方案( 简称q v 方 案) 1 9 9 9 年，h s a k a z a k i ，e o k a m o t o ，m m a m b o 4 6 1 提出了基于环z 。上的椭圆曲 线上的密钥交换协议( 简称s o m 协议) 2 0 0 1 年，m i n g h u aq u d o u gs t m s o n ，s c o t t v a n s t o n e 4 7 1 证明了s o m 协议中有类似同态特性的性质，说明了该协议不安全， 并在 4 3 1 中提出了一个不具有同态特性的改进协议( 简称q v 协议) 然而，q v 方 案、s o m 协议和e v 协议均选取江( qb ) 上的阶为! c m 舟易( n ，6 ) ：孝蜀( 。，6 ) 的点g 作为公钥，并且限定其对应的马( 口，b ) 和蜀( o ，b ) 均为循环群，这就使得 选择用来构作数字签名方案和密钥交换协议的上的椭圆曲线风( o ，b ) 十分有 限我们通过选取z k ( o ，b ) 上阶为l c m n 1 ，m 1 ) 的点作为基点，这里n 1 ，m 1 分别 为己( ，和蜀( 。，b ) 的最大循环子群的阶得到了一个基于环z 。上的椭圆曲 线的一个新的数字签名方案和一个新的密钥交换协议( 包括将两方之间的密钥 交换协议扩展到三方) ，新的数字签名方案是对k m o v 方案和q v 方案的改进； 新的密钥交换协议是对s o m 协议与q v 协议的改进 四川大学博士学位论文 1 1 引言 第一章广义c a r m i c h a e l 数 2 0 0 2 年a g r a w a l 、k a y a l 和s a x e n a 1 1 成功地解决了多项式时间判别素数这 一著名的世界难题在【1 】中他们给出了判定输入整数是素数还是合数的确定 多项式时间算法在研究这一问题的进程中，文献 2 1 和【3 】起了重要的作用。文 3 1 主要讨论k 阶广义c a r m i c h a e l 数集g ( 简称阶c a r m i c h a e l 数集q ) 的若干 性质，其中关于g 的定义为：设n 是一个合数，z 。表示模n 的剩余类环，r ( z ) 是z 。上一个k ( k 0 ) 次不可约多项式，且对上任意的次数不大于k l 的 多项式，( 。) ，( z ) 妒一；l ( m o d n ，r 缸) ) ( 即在陋】( r ( z ) ) 上，( z ) 妒_ 1 = 1 ) ，则 n g ( 即称n 是一个k 阶c a r m i c h a e l 数) 在上述定义中，总假定 0 ，此外，环z 。上的多项式的带余除法仅当除式 是首一多项式时，其商和余式才是唯一的( 见 3 1 中2 1 节) ，所以定义中的r ( z ) 总 假定为首一次不可约多项式众所周知，z 。上首一k 次不可约多项式的个数经 常大于1 ，文 3 1 对k 阶c a r m i c h a e l 数集g 的刻划不够清楚我们在文f 4 】中通过 引入n 是一个k 阶模r ( z ) 的c a r m i c h a e l 数的定义，将给出吼一个清楚的刻划 定义设n 是一个合数，玖表示模竹的剩余类环，r ( ) 致 瑚是一个首一 的k ( k 0 ) 次不可约多项式，如果对v ，( z ) z 。m ，有 ，( z ) “。，( z ) ( r o o dr ( 。) )( 1 11 ) 则称n 是一个k 阶模t ( x ) 的c a r m i c h a e l 数，全体这样的数记为瓯，显然 c 1 ，即为通常的c a r m i c h a e l 数之集，记为c 1 设 q = u c k ，( 。) fr ( z ) 过全体z 。上的首一角次不可约多项式 ，( 1 1 2 ) g 称为女阶c a r m i c h a e l 数集 一5 四川大学博士学位论文 容易看出，本文通过引入数集g m 1 ( 它显然是伉的一个子集) 来定义数集 q ，与【，】中所定义的g 是相同的，但更为合理，刻划仉也更清楚，同时能够清 楚刻划n c k 的充分必要条件文 3 1 在研究q 性质的同时，提出了有关瓯的 一些未解决的问题，其中两个问题是： 1 ) g c k + 1 是否成立? 2 ) 是否对于某些k ，i g i 0 ) 次不可 约多项式，则n 吼，( 。) 当且仅当 1 ) n = p l p 2 p t ，其中t 2 ，p 为不同的素数，( i = 1 ，- - ，t ) ；( 1 2 1 ) 2 ) 对礼的每一个素因子p ，有 p 忆1i 矿一l ，j = l ， o = k ， ( 1 2 2 ) j = l 6 四川大学博士学位论文 这里r ( z ) = r l ( x ) h ( z ) 是r ( z ) 在f v x 】上的分解式，q ( 。) 是f p 叫中首一的 不可约多项式，且两两不同，d 。g ( z ) ) = ，j = 1 ，s 证明先证必要性设n g ，( 。) ，则对v ，( z ) z 。h ，有 ，( z ) ”= ，( z ) ( r o o dr ( z ) ) 反设1 ) 不成立，即n 不是无平方因子整数，则存在素数p ，有p 2 n ，于是取 ，如) = ；n ，在z 。中( ；) 2 = 参礼= 0 ，所以( ；) ”= o ；，与定义矛盾于是 1 1 成立， 对任意的pt t ，则( 1 1 1 ) 在f p 上也是成立的，即对v f ( x ) f p m ，有 ，( 。) 一if ( x ) ( r o o dr ( z ) ) 设r ( z ) 在f p h 上可分解成s 个不可约多项式之积，即r ( z ) = r 。( 。) n ( 。) ，其 中q ( z ) 是f ，嘲中首一的不可约多项式，且d e g ( r j ( x ) ) = l ，j = l ，s 。我 们首先证明r j ( 。) 是互不相同的反之设r l ( z ) = r 2 ( z ) ，于是有，( 。) 7 + ；，( z ) ( m o dr l ( 。) 2 ) 成立，但是若取，( z ) = r - ( z ) ，则该式不成立，这就得到矛盾结果所 以r j ( x ) 两两不同，j = l ，8 所以对v f ( z ) b h 有 ，( z ) ”i ，( 。) ( m o d q ( z ) ) ，j = 1 ，s 在f r 旧中取阶为砂一l 的多项式，( 嚣) ，则由( 1 2 3 ) 得砂一li , r b k _ 1 即2 1 成立 再证充分性设n = p l p 2 p 满足i ) ，由( 1 2 ，1 ) 式可褥 ，( z ) “i ，( z ) ( m o d0 ( z ) ) ，对v ，( z ) f ，旧 一7 一 ( 12 3 ) j = 1 ，s ， 四川大学博士学位论文 和 ，( z ) “；，( z ) ( r o o dr ( z ) ) ，对v ，( z ) f p x 设f ( x ) z 。i x ，对坳ln ，同余式 ，( z ) e ，。( 。) ( r o o dp ) ，。( z ) f p x 表示f ( x ) 和，【，( z ) 次数相同的项其对应的系数模p 同余设映射 妒：。 x 】xf p 。hx ( f ( m ( z ) ，f ( p ：( z ) ， 由孙子定理知砂是一个双射故 xf p 。 ，( z ) ) 一z 。陋 一，) ，( 。) 一，( z ) ( r o o dr ( 。) ) 对v f ( z ) z 。陋 所以n 吼、，口 推论i i1 4 1 设n 是一个合数，则n eq 的充分必要条件是存在一个z 。上 的首一k 次不可约多项式r ( z ) ，使得n q 咖1 该推论由a 的定义和定理1 1 立得 推论1 2 4 1 设札= 3 n 笔l n ，其中p 。兰1 ( r o o d4 ) ，f 兰1 为整数，p i 为互不 相同的素数且鼽一ii 舻一l ，i = 1 ，f ，则n c 2 。+ 1 证明当p il ( r o o d4 ) 时，l e g e n d r e 符号( 寻) = 1 ，( 见1 6 1 ，9 7 页) ，故x 2 + l 在f m 上可约，i = 1 ，f ；又z 2 + 1 在f 3 h 上是不可约的，且n 2i1 ( m o d8 1 以及由假设p i 一1 n 2 1 ，i = 1 ，f ，故n 和z 。旧上的不可约多项式。2 + 1 满足( 1 22 ) ，所以n g ，一+ l 口 例1 1 由推论1 2 知n = 1 5 ，2 5 5 ，4 3 5 时，n 巴 推论1 3 设n = 5 兀：= 1 p e ，其中p 。in ，p t = 7 ( r o o d1 2 ) 或巩11 8 婴查鲎竖主堂垡堡奎一 f m 。d1 2 ) ，f l 为整数，a 为互不相同的素数且肌一1l n 2 1 ，i = 1 ，l ，则 ne g 、护+ 3 证明当p i 兰7 ( r o o d , 挖) 或p 。i1 ( r o o d1 2 ) 时，l e g e n d r e 符号( 音) = 1 ， ( 见鸭1 0 5 页) ，故。2 + 3 在f “h 上可约，i = l ，f ：又z 2 + 3 在f 5 h 上是不可 约的，且当3 n 时，5 2 - - l = 3 - 8 lt 2 - - 1 ，以及由假设条件p i - - 1 1 2 - 1 ，i = 1 ， 故n 和z 。m 上的不可约多项式x 2 + 3 满足( 1 2 2 ) ，所以礼q 口 例1 2 由推论1 3 知礼= 3 5 ，6 5 ，4 5 5 时，n 岛 类似可证 推论1 4设n = 7 n 名1 p 。，p ；in ，p l 三1 ( r o o d8 ) 或p li5 ( m o d8 ) ，f 1 为整数，且p t i5 ( r o o d8 ) 的个数为偶，p 。为互不相同的素数且p ，一1n 2 1 ，i ； l ，- ，f ，贝u 礼g 。2 + 1 例1 3由推论1 ，4 知扎= 1 1 9 时，n e 岛 定理1 2 1 4 1 设礼是一个合数，则n 岛的充要条件是： 1 ) n 无平方因子； 2 ) 对坳h 均有p 一1 胪一l ； 3 ) 至少存在个p ，p l n ，使得p 2 1 | n 2 一1 证明先证充分性，由于n 无平方因子，且对坳ln ，均有p ln 2 一l 以 及至少存在一个p ，p 使得p 2 1i 扎2 1 ，可设q 为n 的一个素因子，且 矿一li 珏2 一l ，取口。使得( 等) = 一1 ，若p q ，取唧使得( 誓) = l ，由孙子定理， 存在n ( r o o dn ) ，使得 a 三a 口( i n o dp ) ，p in 由于茁2 一。( r o o dq ) 不可约，故茁2 一o ( r o o dn ) 不可约。且对铷 n ，p q 时，由 ( ；) = ( 詈) = 1 ，故。2 一o ( r o o dp ) 可约，于是由口2 一l n 2 1 和对v pn ，p q 时，p 一1n 2 1 ，由定理1 1 知n 岛。再由推论1 1 即得n g 再t j d g , 要性，当n q 时，则由推论1 1 知存在z 。m 上的2 次首一不可约 多项式r ( z ) ，使得n q ，f 。) ，由定理1 i 知，1 ) 、2 ) 成立，由于r ( z ) 的次数为2 ， 9 四川大学| 尊士学位论文 故存在p in ，使r ( x ) ( r o o d p ) 不可约，即知3 ) 成立 口 推论1 5 有无穷多个2 阶c a m a i c h a e l 数 证明存在无穷多个l 阶c a r m i c h a e l 数n 满足p l n 和p 2 1l n 2 一l ( 7 】i4 3 页和叩，再由n c l 知，仡是无平方因子的合数，且p 一11 n l ( ( 6 】 1 6 3 页) ，即 得p 一1i n 2 一l ，由定理1 2 知这些1 阶c a r m i c h a e l 数也包含在g 中，这就证明 了f 岛j = o o 口 显然有 推论1 6 设n c 1 ，且对n 的任何素因子p ，均有p 2 1 不整除n 2 1 ，则 n 硭岛 下面我们根据推论1 6 给出一个算法，找出许多n q 但n 隹g ，由此证明 了q 垡g 该算法还用到以下命题： 命题1 1 9 1 m 为含有三个素因子的1 阶c a r m i c h a e l 数的充要条件是， m = ( k r i + 1 ) ( k r 2 + 1 ) ( 强+ 1 ) ，其中n + i 为素数，i = l ，2 ，3 且( r i ，您) = ( t 1 ，n ) = ( r 2 ，r 3 ) = l ，且七三一( r l + r 2 + r 3 ) ( r l r 2 + r l r 3 + r 2 r 3 ) 。( m o d l - 1 r 2 r 3 ) 其 中。= ( r 1 ) 曲( r 2 ) 毋( n ) 一l ，为欧拉函数， 由此命题可得： i ) 若取r l = 1 ，t 2 = 2 ，7 3 = 3 时，这时k10 ( r o o d6 ) ，k = 6 t ，p l = 6 t + 1 ， p 2 = 1 2 t + l ，p 3 = 1 8 t + l ，t z ，m = p l p 2 p 3 ，于是可得出当p l ，p 2 ，p 3 为素数时， m c 1 2 ) 若取7 1 = 1 ，r 2 = 2 ，t 3 = 5 时，这时ae6 ( r o o di o ) ，女：l o t + 6 p l = 1 0 t + 7 ，p 2 = 2 0 t + 1 3 ，p 3 = 5 0 t + 3 1 ，t z ，m p i p 2 p 3 ，于是可得出当p 1 ， p 2 ，p 3 为素数时，m c 1 算法： ( 1 ) f o r t = 0 到某一上界： ( 2 ) 计算p l ，p 2 ，p 3 ，其中p l ，p 2 ，p 3 为满足1 ) 或2 ) 型的数： ( 3 ) i f 1 ，p 2 ，p 3 均为素数) ； ( 4 ) 计算= p l p 2 p 3 ； 1 0 四川大学博士学位论文 ( 5 ) i f ( p ? 一1 不整除舻一1 ，i = l ，2 ，3 ) ； ( 6 ) 输出n ，贝9n 仨c t 利用此算法我们算出了： 例1 4 1 ) 型中n l = 3 7 7 3 1 0 9 = 2 9 4 4 0 9 ，n 2 = 2 1 1 4 2 16 3 1 = 5 6 0 5 2 3 6 1 7 2 - 3 = 2 7 1 5 4 t 8 1 1 = 1 1 8 9 0 1 5 2 1 均属于q ，但不属于岛 2 ) 型中“1 = 7 1 3 3 1 = 2 8 2 1 ，n 2 = 3 7 7 3 1 8 1 = 4 8 8 8 8 1 ，“3 = 3 0 76 1 3 1 5 3 1 = 2 8 8 1 2 0 4 2 1 ，礼4 = 3 6 7 - 7 3 31 8 3 1 = 4 9 2 5 5 9 1 4 1 均属于q ，但不属于q 于是得到 推论1 7g 垡伤 1 33 阶c a r m i c h a e i 数 定理1 3 i s , 1 0 1 设是一个合数，礼c 3 ，则n 满足下面的条件： l 犰无平方因子； 2 ) 对坳f n ，均有p 一1 n 3 一l ； 3 ) 至少存在一个p ，p n ，使得p 3 1 n 3 一1 这里p 是素数 证明由推论1 1 给出的n 瓯的充分必要条件知，当n c 3 时，存在 z 。h 上一个3 次首一不可约多项式r ( 。) ，使得n c a ，( 。) ，再由( 12 1 ) 和( 1 ，2 2 ) 知1 ) 和2 ) 成立现在，我们来证明存在素数ph ，使得r ( z ) ( m o d p ) 不可约，如果 对每一个素数pi n ，都有r 扣) ( m o d p ) 可约，由于r ( 。) 的次数是3 ，可设对却 n ， 都有 r ( x ) i ( z + a p ) ( 护4 - b p x + c ，) ( m o d p ) ，a p ，c p f p ， 由孙子定理，存在整数a ，b ，c ( m o d n ) ，对v ph 分别满足 a a ，, ( m o d p ) ，b 三b , ( m o d p ) ，cic ，( m o d p ) 四川大学博士学位论文 此与r ( z ) 在z 。