（计算机系统结构专业论文）基于ntl平台的因式分解模块的实现.pdf

! ， 。 j - - 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：丝蹶工楫期z 烙 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：垄挞导师签名：翘一 日期：加厂口年月乡日 j 摘要 摘要 计算在人类社会的发展中发挥着重要的作用，每一项重大科学技术的突破都离 不开计算。最初，计算机能表示的数字范围是有限的，所作的计算都是数值计算， 得到的是近似的结果。但是实际上，在自然科学与工程中，不仅仅需要近似计算， 更多的是要进行公式推导，表达式化简等，需要获取精确的结果，这些计算是一 些符号按照确定的规则进行的推导，即符号计算。 符号计算的主要特点是计算结果准确和计算过程稳定，已广泛运用于需要获 得准确结果的领域，诸如计算机自动推理、可验证计算等。数值计算具有速度快、 能运用浮点运算处理近似问题，得到近似解和解决大规模问题的优势，已广泛应 用于工程技术等领域。但它的主要问题是计算的不稳定性，同时一般只能得到局 部解和部分解，而遗漏某些有意义的解。 多项式因式分解的基本思想是将多元问题转化成一元问题，所以首先要解决的 是一元多项式的因式分解。在此之前，本文首先介绍了多项式因式分解的概念， 代数基本知识，大整数的表示和运算，多项式的表示和运算，用e u c l i d e 锄算法求 最大公因子。重点讨论的是因式分解中经典的符号计算方法h e l l s e l 提升方法，其 基本思想是对于一元多项式f ，通过无平方分解，异次分解，等次分解，求得其在 模素数p 下的初始因式分解，然后提升到模p 的幂次的因式分解。 多项式因式分解是计算机代数系统最基本的功能之一，在符号计算和自动推 理中有重要应用。尽管m a p l e 等计算机代数系统己对多项式因式分解进行了实现， 然而却有很多不足，如软件庞大，效率低，编程语言不统一，可移植性差。n t l 库 是开放源代码的自由软件库，它提供了大整数的运算，一元多项式的运算等，遗 憾的是，它只提供了一元多项式因式分解，没有提供多元多项式因式分解。国内 也有人在n t l 库上对多元多项式因式分解程序进行实现，但是程序不稳定，只能 解决小规模的问题；针对这些不足，作者在n t l 库上设计了多元多项式因式分解 程序，增加了类库，实现了程序，并将程序运行效率与m a p l e 中的因式分解的效 率进行比较，具有更高的效率，能解决大规模的问题。 关键词：符号计算，数值计算，多项式因式分解，n t l 库 -，s， 一 a b s t ra c t a b s t r a c t c a l c u l a t i o np l a y sa i li i i l p o n a n tr o l ei nt l l ed e v e l o p m e n to fh m a i ls o c i e 毗e v e 叮 m a j o rs c i e i l t i f i c 锄dt e c l l i l o l o 百c a lb r ea ：m 鹏u 曲d 印e n do nm ec a l c u l a t i o n a tf i r s t ，m e n 珊曲e rr 趾g ee x p r e s s e db yc o m p u t e ri sl i m i t e d ，m ec a l c u l a t i o n i sn u i i n 耐c a l ，锄dg e t st l l e a p p i o x i m 纳er e s u hf a c t ，i i l 妇1 en a 咖ls c i 吼c ea n de n 西n e 谢n n o to n l ya p p r o x l m a t e c a l c l l l a t i o i l m ef 0 m ：m l ad e r i v 撕o n 锄ds i i i l p l i f - y i i l ge x p f e s s i o n sa r em o r ei n l p o r t a n t ，n e e d t 0o b t a i l la c c u r a t er e s u l t s ，m e s ec a l c u 【l a t i o n sn 锄e ds y i l 曲o l i cc o m p u t a t i o na r cf o m m l a d 舐v a t i o ni na c c o r d a n c cw i me s t a b l i s h e dn 1 1 e s t h em a i l lf e a 臼叮懿o fs y m b o l i cc 0 哪p l n a i o na r ca c c l l r a t er e s u l t sa n ds 劬l ep r o c e s s ， 廿l es y r n b o l i cc o m p u t a j o nh 嬲b e 饥w i d e l yl l s e dw h e r en e e d sa c c u r a t er e s u l t s ，s u c ha st 王l e c o m p u t e ra u t o m a t e dr e a s o 山g 趾d v 嘶f i a b l ec a l c u l a t i o n - n 啪甜c a lc a l 砌a t i o nh 嬲m e a d v a n t a g e sw h i c ha r cl l s i n gn o 撕n g - p o i n tt 0d e a lw i ma p p 哟x i m a t ei s s u e sa i l ds 0 l 啊n g l 硼箩s c a l ep r o b l e m s ，a i l dh a sb e e i l 谢d e l y1 l s e di 1 1e n 百n e 舐n ga r e a s ，b u ti t sc a l c u l a t i o n p f c h 嘲si sn o ts t a b l e ，舡l eg e l l e r a l l y0 n l yg e tp 枷a ls o l u t i o n ，肌dm i s ss o m em e 撕n g 鼬 s o m o n s 1 1 1 eb a s i ci d e ao fp 0 1 y n o m i a lf a c t o r i z a t i o ni st ot r a i l s f 0 i mm 1 椭v a r i a t ep o l y n 锄i a l 缸t o r i z a t i o ni l l t ou i l i v a r i a t ep o l y n o m i a lf 妣r i z a t i o 玛s o ，矗r s t l yu i l i v 撕a t ep o l y l l o m i a l f a c t o r i z a t i o ni n u s tb es o l v e d b u t 面0 rt ot h i s ，w eh a v et 0k n o wm e m eb a s i c 虹o w l e d g c o fa l g e b n l el a r j g ei n t e g e r 喇 r e s e i l 协t i o na n do p 踟缸o n s ，p o l y n o m i a lr e p r e s e n 枷o n 觚d0 p e r a t i o n s ，n l ee u c l i d e a na 1 9 0 r i 吐1 1 1 1 蠡ms e e l ( i n g l eg r e a t e s tc o m m o nf a c t o r n e c l a s s i c a ls y m b o l i c 唧u t a t i o nm e m o dh 肌s e l1 i f t i n gi so l l rf i n a lg o a l ，m eb a s i ci d e ai s t 0 g e tai n i t i a l f 融o r i z a t i o nw h e nm o d u l em ep r i m ep ，b ys q u a r e 仔e e - f a c t o r i z a t i o n d i s t m c t d e g r e ef a c t o r i z a t i o n ，e q u a l d e 蓼e ef a 曲o r i z a t i o i l m e nl 谂i tt oa n e wf a c t o r i z a t i o n 、) l ，_ i l i l em o d u l ep r i m epp o w e r f a c t o r i z a t i o ni sab a u s i cn m c t i o no fac o m p u t e ra l g e b ms y s t e m ，觚di sw i d e l yu s e d i l ls y m b o l i cc o m p u t a i o n 锄da u t o m a t e dr e a s o n i n g 砧t l l o u 曲，m 印1 eh a st h e 如n “o no f p o l ”o m i a lf a c t o r i z a t i o n ，i ts h o w sm a n yd i s a d v a n t a g e s ，f 0 i 。c x a m p l e ，s o 胁a r es y s t e i i l l s t o ol a 玛e ，l o we 伍c i e i l c y ，d i f j e 阳l tp r o 踮吼l a i l g u a g e sb e t w e e i ld i 脓e n tv e r s i o n s ，a 1 1 d p o o rp o r t a b i l i 咄n t li saq m 1 i b r a r ya l l dm es o w c ec 0 d ei so p e i lf o rl l s i tc a n0 p e r a t e i i a b s t r a c t l a 增ei n t e g e r 锄du l l i v 碰a t cp 0 1 y n o i i l i a l s ，u i l l u c k y ，i to n l yh 嬲m el l i l i v 卸r i a t ep 0 1 ) r 1 1 0 m i a l 蝴z a t i o 玛n 0m u l t i v a r i a t ep 0 1 y n o l i l i a lf 她t o r i z a d o n s o m c o n e h 嬲、阳出e d 访吐1 e 阿r l l i b r a 巧t 0i r l l p l e m e mm em n c t i o no fm u l t i v 撕a t ep o l y n o m i a lf a c t o r i z a t i o n ，b u tm e p r o g r a mi sn o ts t a b l e ，c a i lo m yr e s o l v es m a l l - s c a l ep r o b l e m s f o rm c s ed i s a d v 锄t a g e s ， 栅m o ra p p e n dn e wc l 嬲s1 i b r 撕e s ，锄dd e v e l o pm u l t i v 耐a t cp o l y n o m i a lf i a c t o r i z a t i o n p r 0 伊锄o n l en t ll i b r a 巧u s i n gc 卜十1 锄g u a g e ，c o m p a r ci tt 0m 印l e ，i th 硒伊e a t e r e 伍c i c y i ( e y w o r d s ：s y i l l b o l i cc o m p u t a i o n ，n u m e f i c a lc a l c u l a t i o n ，p o l y i l o m i a l 触o d z a t i o n ，n t l “b 删了 i l l 目录 目录 第一章前言1 1 1 计算机代数简介1 1 2 多项式因式分解的发展1 1 3 多项式因式分解的意义3 1 4 本文主要内容及组织结构4 第二章多项式因式分解基础5 2 1 大整数5 2 1 1 大整数的表示5 2 1 2 大整数的基本运算5 2 2 整数的p a d l c 表示7 2 3 多项式7 2 - 3 1 多项式的表示7 2 3 2 多项式的基本运算8 2 4 多项式最大公因子9 2 4 1e u c l i d e a nj 不9 2 4 2 扩展e u c l i d e 趾算法1o 2 4 3 模方法1 l 2 4 4 一元多项式最大公因子12 2 4 5 多元多项式最大公因子1 4 2 5 多项式的i a d i c 表示1 4 2 6 本章小结15 第三章多项式因式分解概述1 6 3 1 一元多项式因式分解1 6 3 1 1 异次分解1 7 f v 目录 3 1 2 等次分解18 3 1 3 完整的因式分解1 9 3 1 4 无平方分解2 0 3 2h e n s e l 提升因子分解2 1 3 2 1 在z x 】和q x 】上的分解2 1 3 2 2h e l l s e l 提升基本思想2 4 3 2 3h e i l s d 提升因式分解2 5 3 3 多元多项式因式分解2 7 3 4 本章小结2 7 第四章多元多项式因式分解程序设计2 8 4 1n t l 算法库介绍2 8 4 2 多项式因式分解算法3 0 4 2 1 一元分解3 0 4 2 2 二元分解。3 5 4 2 3 多元无平方分解3 9 4 2 4 多元中的单变元分解4 2 4 2 5 多元分解算法的构造4 3 4 3 多元分解程序的各个类4 7 4 3 1 多项式类m p o lc l a s s 4 7 4 3 2 类m p o u i s tc l a s s 4 9 4 3 3 类m p o l f a c t o r sc l a s s 5 0 4 3 4 多元映射到一元类m p o l i n a pt ou p o l 5 l 4 3 5 类m p o lu p o l 5 2 4 3 6 类m p o lg c d 5 3 4 3 7 模p 分解类m p o l f a c t o rm o dp 5 5 4 3 8h e 姗e l 提升类m p o l l m 5 6 4 3 9 多元因式分解类m p o l f a c t o r 5 9 4 4 多元分解流程6 0 4 5 整个程序流程6 0 n 目录 4 6 本章小结6 1 第五章试验结果6 2 第六章总结和展望6 4 6 1 总结6 4 6 2 未来发展方向6 4 致谢6 6 参考文献6 7 攻读硕士学位期间取得的研究成果7 0 v i 第一章前言 1 1 计算机代数简介 第一章前言 在自然科学和工程领域中，需要解各种各样的方程，线性方程，多项式方程或 不等式。原则上，有两种方法可以解这些方程，近似方法和精确方法，数值分析 是一种近似方法，它提供了高效的数学方法和计算机软件来计算近似问题。 计算机代数是通过公式推导，表达式的化简来获取解，它是计算机科学中比较 年轻的一门学科，研究的是通过数学工具和计算机软件来获取方程解，它采用的 是符号计算方法，获取的是精确解。 多项式因式分解是计算机代数系统的一项基本功能，在符号计算和自动推理 中有重要应用，另外在多项式化解，形式积分，人工智能，密码学等方面也有重 要应用。多项式因式分解也有符号计算和数值计算两种方法，符号计算过程是精 确的，所以采用符号方法进行多项式因式分解的结果也是精确的。与符号方法相 对应的是因式分解数值方法，是一种近似计算。数值计算速度快，能运用浮点运 算处理近似问题，得到近似解。 符号计算种类很多，实用性很强。但是由于计算机的计算速度，内存大小等 多种因素限制，符号计算软件发展缓慢。近三十年来，符号计算才算得到真正的 发展，一些高效的计算机代数系统软件已经被开发出来，如r e d u c e ，m a p l e 等，可 以在个人计算机及工作站上运行。 1 2 多项式因式分解的发展 多项式因式分解是将一个多项式分解成多个互素因子的乘积，对于比较简单的 多项式，我们可以采用公式法进行分解，但是对于一些系数大，项数多，次数高 的复杂多项式如何分解，这就是本文需要讨论的问题。 一些高效的因式分解算法被发明，使得我们能够有效的计算单变量或多变量多 项式的因子。这些多项式的单项系数是在一个确定的有限域上，是整数，有理数 或者实数。主要有两种因式分解方法，符号计算和数值计算。 就目前而言，符号计算方法主要有两种，b 酣e k 锄叩z a s s e i l l l a u s ( b z a ) 方法l i i ， 电子科技大学硕士学位论文 由b 甜e k a i i l p ，m u s s z a s s e i l l l a l l s ，w 锄g ，w b i n b e 唱e r 等提出，其思想是h e i l s e l 提升， 是目前最成熟的算法；另一种是l l l 方法1 2 j ，由a k l e n s 缸钆h w 【舳s 舰与l l 0 v 蠲z 在八十年提出。 b z a 算法在分解大多数的多项式时，执行时间是线性的，也是普遍使用的方 法。人们也在研究不改变b z a 算法的思想，改进它的中间过程，使得此算法能更 高效的分解复杂多项式。k a l t o f e n & s h o u p 发明了一种叫做b a b ys t 印s 俘a n ts t 印s 的 因式分解方法1 3 l ，他们实现了此方法的单变量因式分解，当多项式次数很大，模大 素数时，效率很高。a 砧o t t 和s h o u p 在论文中也描述了这种思想1 4 1 ，在b z a 算法 中改进最后一个阶段( 查询阶段) ，加快寻找真正因子的速度。论文中阐述的改进方 法在n t l 库中已经实现。 应用b 甜e k 锄叩z a s s e n h a u s 方法进行多项式因式分解，最坏的情况下所需的时 间是指数级的，a k l 饥s t r a ，h w l e i l s t r a 与l l o v a s z 提出了一种整数环上一元多项 式分解的多项式时间算法，l a t t i c eb 嬲i sr e d u 砥o n 方法。同时，e 蹦t o 胁证明了可 以将多元多项式的因式分解问题简化为一元多项式的因式分解问题。对于多项式 的系数是有理数时，仍然可以使用此方法，所需时间仍然是多项式时间的。因式 分解不像交换代数和代数几何中的其他问题，多变量因式分解的时间复杂度是不 确定的。在2 0 0 0 年的时候，m 破v 踟h o e i j 在b 甜e k 锄1 p z a s s e n h a u s 方法中引进了 1 a t t i c eb a s i sr o d u c t i o n 思想1 5 l ，成功的分解了s w i 姐耐o n - d v 盯多项式，其实在九十 年代s a s a k i 已经提到了这种方法1 6 i 。尽管多项式分解取得了很多的成就，但是对于 那些高次数，大系数的多项式，还有很多问题没解决，如计算一个多项式模大素 数的根的是一个n p 问题i 7 1 。 与符号方法相对应的，是采用数值方法进行多项式因式分解，也就是近似多项 式因式分解。给定复数域上的多项式f 【x ，弘z ) ，由于测量或者计算误差，f 在复数域 c 上是不可约的。我们希望在f 的邻域内，找到距离f 最近的可以分解的多项式 f 【m i i l 】，近似多元多项式因式分解可以追溯到文献1 3 i ，文献1 9 i 中提出的方法主要是 基于h e n s d 提升，这些方法适用的前提是在f 很小的邻域内存在可以分解的多项 式。在文献l lo i 中，讨论了将多元多项式的近似因式分解转化成多项式或有理函数 的最优化问题，运用有理系数多项式的平方和来验证近似因式分解问题的全局最 优解。 在因式分解的数值计算方法中，国内的研究人员也取得了喜人的成果。张景 中和冯勇在文献l l l l 中，讨论了如何从近似值得到准确值。即要计算一个有理数砒， 已经知道了该有理数的分母的上界n ，存在一个数值方法可以计算该有理数任意 2 第一章前言 精度的近似值，但不能计算其准确值，文章中给出了计算该近似数的精确值即i 砒 的算法。另外在文蒯1 2 l 中，给出了采用数值方法分解多项式的算法，其中用到了 从近似值获取精确值的算法。采用i n t e 巾o l a t i o n 方法分解多项式，即是采用近似方 法获取多元多项式的精确的因式分解的值。这种方法充分利用了数值方法高效率 的特点，对于分解某些具有低次数因子的多项式，比其他方法更有效。 1 3 多项式因式分解的意义 多项式因式分解是符号计算与计算机自动推理中最基本的算法之一，它在诸如 代数关系式的化简，形式积分以及多项式求解，编码理论及序列密码的研究等许 多问题中都有着十分重要的应用。 数学中，很重要的一门学科就是符号计算，也叫计算机代数，它是数学学科和 计算机学科交叉发展的结果。与数值计算不同的是，符号计算进行的是准确的计 算和公式的推导。计算机代数系统必须要通过计算机软件实现，才能显示出他的 价值。在国外已经有些计算机代数系统，如m a p l e 。对于所有的符号代数系统， 都要提供一个最核心的功能，就是多项式因式分解的功能，因为他在符号计算中 有着很重要的作用，是符号计算和计算机自动推理中最基本的算法之一。目前， 在一些商业计算机代数系统，如m a p l e ，m a t l l e i l l a t i c a ，都有多项式因式分解算法的 实现。但是，还是有些不令人满意的地方，如： ( 1 ) 以m a p l e 为例，软件越来越大，对计算机硬件要求越来越高，内存管理不足， 运行速度变慢。 ( 2 ) 编程语言不一致，各个计算机代数系统都采用自己的编程语言，这些语言之 间的差异很大，不同的代数系统之间没有通用性，甚至在同一计算机代数系统的 不同版本问也不兼容。 ( 3 ) 现在的计算机代数系统采用的是面向过程的编程语言，开发效率不高，对系 统添加新的功能不方便，缺乏面向对象编程语言的特征。在现有计算机代数系统 上编写的程序不能移植到用面向对象语言编写的软件中。 ( 4 ) 可移植性差，大多数计算机代数系统偏向于不同的子方向，对于不同的系统 平台兼容性差。 到目前为止，没有出现一个解决以上问题的符号计算平台。为了弥补这方面 的不足，本人导师有意开发一个高效率的符号计算平台。建立一个属于自己的符 号计算平台，对科学研究来说具有重要的意义。但是建立符号计算平台是一项庞 电子科技大学硕士学位论文 大的工程，本人仅仅完成此平台中的第一步，研究并完成一个多项式因式分解的 模块。 1 4 本文主要内容及组织结构 因式分解的符号算法就是指对因式分解的中间过程全部采用符号来表示。由于 符号计算过程是精确的，所以采用符号计算方法进行多项式因式分解的结果也是 精确的。 本文章最终结果是要设计一个多项式因式分解的模块。我们在n t l 库的基础 上，采用传统的h e i l s e l 提升符号计算方法来实现软件，n t l 算法库是开放源代码 的自由软件，具有专业处理任意精度大整数，实数的计算数论与计算代数的高性 能可移植c + + 库。 本文章各章节的内容安排如下： 第一章：前言。总体上说明了计算机代数系统中因式分解的发展现状，指出了 本文章研究的背景以及意义所在，描述了论文的总体结构。 第二章：多项式因式分解基础。讨论了代数基本知识，大整数的表示，大整数 的基本运算，多项式的表示，多项式的基本运算，多项式的最大公因子，包括单 变量多项式最大公因子和多变量多项式最大公因子。 第三章：多项式因式分解概述。对一元多项式的因式分解作了详细的介绍，包 括，异次分解，等次分解，无平方分解；介绍了h e n s e l 提升分解多项式的思想。 第四章：多元多项式因式分解程序设计。首先简单介绍了n t l 算法库，讨论 了一元多项式h e i l s e l 提升分解算法，并根据一元h e n s e l 提升算法和多元h e i l s e l 提升思想，作者给出了二元和多元多项式因式分解的算法，并对算法的一些细节 进行了讨论。根据多元分解算法设计了多元分解程序，详细描述了多元多项式因 式分解程序的各个类，并给出了多元分解流程图和整个程序的流程图。 第五章：试验结果。将实现程序与m a p l e 的因式分解进行效率比较，发现本程 序比m a p l e 效率略高。 第六章：总结和展望。总结了本文章内容，介绍了未来因式分解的发展方向， 符号计算和数值计算互相结合的混合计算的因式分解的方法。 4 第二章多项式因式分解基础 2 1 大整数 第二章多项式因式分解基础 2 1 1 大整数的表示 计算机代数的基础是数字，而计算机是用来处理数据的；所以在计算机代数 中第一个要解决得问题就是把数据作为数字输入到计算机中去处理1 1 3 。数据是以 字为单位存储在内存中的，现在的计算机使用的是3 2 或6 4 位，假设我们有一个 6 4 位的处理器，则一个机器字包括了个单精度整数n ，o n 2 “1 。 整数环是一个e u d i d 整环，给定2 个整数a 和b ，存在唯一的整数q 和r ，使 得下面的等式成立。a _ q b + f ，o 硒其中r 为余数，q 为商数。 怎样才能表示在范围 o ，26 4 1 ) 之外的数据? 像这样一个多精度的数字，可 以通过一组6 4 位的字来表示，a - ( 一1 ) ：口，2 删( o i n ) 其中，s o ，1 l ，o n + 1 26 3 ，且岛 o ，2 “1 ) 如果我们把2 “用b 来代替，也就是b 为2 “或者2 3 2 ，则任意大整数a 可以表 示成b 进制的数，则表示后的等式如下：a _ 口t b + 口b 扣1 + + 口l x l + 整数a 的这种表示形式是唯一的，并且可以写成如：a - ( 吼，口h ，口o ) 。的形式， 这种表示形式称为a 关于基数b 的展开，也称其为k + 1 位b 进制整数。 2 1 2 大整数的基本运算 大整数的关系运算：如果有2 个大整数a ，b ，他们关于b 展开形式分别是 a = 口f b ( o i m 1 ) ，b = 6 f b ( o i n 1 ) 其中口，包 o ，b 一1 ) 如果a ，b 具有相同的位数，即m = l l ，则从最高位到低位比较，在对应的位数上， 第一次出现数字大的那个数比另一个数大。如果，a ，b 有不同的位数，则位数多的 那个数比另一个数大。 大整数的加减法：考虑2 个数a ，b 的加法整数，假设m 咒，让b ，。= _ b 。= 0 ， 则b 可以写成b = 罗岛b ( o i m 1 ) ，于是a 和b 的和c 在数学上可以表示为 c = ( 口，+ 6 ，) 召( o i m 一1 ) ，但是若c 关于基b 的表示为c = c 声( o i m 1 ) ， 则不一定有c ，= 口，+ 抚，因为当口，+ 色b 时，必须考虑进位的问题。 电子科技大学硕+ 学何论文 算法2 1 大整数加法 输入：大整数a - ( 一1 ) 。口，b ( o i m 1 ) ，b = ( 一1 ) 5 6 f b ( o i m - 1 ) ，s o ，1 ) 输出：大整数c = ( 一1 ) c f b ( o i i n + 1 ) c _ a + b 1 = 0 2 细瑚，md 0 c l = 口f + 岛+ ，+ 1 = o i fc f bm e nq = c f b ，吒+ l = 1 3 c 。+ 1 2 ，肺+ l 咖c = ( 一1 ) 。c f 曰( o i l n + 1 ) 算法2 2 大整数减法 输入：大整数a = ( 一1 ) 口，b ( o i m - 1 ) b = ( 一1 ) 岛曰( o i m - 1 ) ，s o ，1 ) 输出：大整数c = ( 一1 ) 5 c f b ( o i i n + 1 ) c - a b 1 = o 2 f 0 r i - o ，md o 3 s f = 口f 岛+ 砖 i f s f om e i lc f = s f ，七f + i _ o e l s e q = j f + b ，t + l = 1 大整数的乘法：有两个大整数a = 口，b ( o i n 1 1 ) ，b = 6 ，b ( o i n - 1 ) ， 则a b 的积为c = a b ，设i 咖，将上面的乘积展开，b 。乘a 的系数排成第一行，b ，乘 a 的系数排成第二行，并将b 的同一次幂的系数放在同一列，则可以得到一表，然 后利用这些系数的乘积将萨a b 关于b 的展开求出来。 算法2 3 大整数乘法 输入：大整数a _ ( 一1 ) 5 口，b ( o i m 一1 ) ，b = ( 一1 ) 5 岛b ( o i n 1 ) ，s o ，1 ) 输出：大整数c = ( 一1 ) 5 c ，b ( o i m + n - 1 ) 萨a 宰b 1 f o r i ：0 ，m 一1d oc j = o 2 f o r j = o ，p 1 d 0 r = o 3 f o r h = o ，灿- ld 0 # a h b 产ch + j 电 c 川= 册n 化b ) f q u o ( t ，b ) c j + 辨2 r 6 第二章多项式因式分解基础 2 2 整数的p a d ic 表示 如果p 是一个素数，z p = 【0 】， 1 】， p 一1 】，) ，对于任何一个整数a ，我们可 以用下面这种称为整数的p 础c 表示形式来表示1 1 4 l 。 a 寻+ q p + a 2 x + + 口t p ，q z 口 这种表示和整数关于基b 的展开的表示形式有一定的相似性，大整数关于基b 展开后的系数全都是非负的，但整数的p a d i c 表示中系数都是模p 的主余数，有2 种形式，一种是取 0 ，1 ，2 ， p 一1 ) ，这时系数都是非负的，和大整数关于基b 的展 示形式是一致的：另一种是系数取 一q - 1 ) 2 ，1 ，o ，1 ，o - 1 ) 2 ) ，这种表示方法形式称 为p a d i c 方法。当模p 的主余数都是非负时，整数的p a d i c 表示形式和整数关于 基b = p 的表示形式是一致的；但是当模p 的主余数采用的是对称形式时，我们采 用如下定义的对称带余除法来表示： a = q ( 一p 2 唰2 ) ，r 和q 分别记为：r = s r 锄( a p ) ，q = s q 呻( a ，p ) 。 对称带余除法和以前的带余除法具有下面的关系： 如果r 锄( 岛p ) p 陀则溯n ( 岛p ) = 暂e m “p ) p 且s q u o 瓴p ) = q u o “p ) + l ，如果 r 锄( a ，p ) 2 ，p 是大于等 于2 的整数；a 的p _ a d i c 表示具有下面的递推公式：g o = a ，q = s r e l n ( 吼，p ) ， g t + l = s q u o ( g i ，p ) ，k = o ，1 ， 2 3 多项式 2 3 1 多项式的表示 设r 为交换环，x 是一变元，r 【x 表示r 上的一元多项式的全体。多项式的次 数定义为非零系数的下标最大者，记为d e 甙a ) 。因此，每个非零多项式都可以写 成规范的形式： a ( x ) 2 口f x 2 口x 小+ 口m l x “- 1 + + 口l 工1 + 口o a f z ，a m o ，o i m 一个多项式的全部系数都为0 ，称其为零项多项式，也就是o ，零项多项式的 次数为，即d e 甙0 ) = 。如果个多项式的次数为o ，则称其为常数多项式，也 就是一个常数。如果一个多项式中d e g ( a ) = n ，a 中的乘幂的系数为口。，则口。工” 为a 的领式，记为l m ( a ) = 口。石”，口。是多项式a 的领项系数，记为l c ( a ) = 口。，x ”称 为a 的领项，记为l “a ) = ，当l “a ) = 1 时，多项式a 是首一的。 7 电子科技大学硕士学位论文 设d 是一整环，a ( x ) = 吒z d x ( o i k ) ，a 的容度( c o 删定义为其系 数的最大公因子，即c 0 n t ( a ) = g c d ( ao ，吼) ，如果c o n t ( a ) = 1 ，则称a 为本原的 缸砌t i v e ) ，a 的本原部分p p ( a ) ，定义为p p ( a ) ：a 肋1 1 t ( a ) 。 ( g 哪s 引理) ：设d 是u f d ，a ，b d 【x 】，则c o n t ( a ，b ) = c o n t ( a ) c o n t ( b ) ，p p ( a ，b ) = p p ( a ) p p ( b ) ，c o n t ( g c d ( a ，b ) ) = g c d ( c o 删冷) ，c o n t ( b ) ) ，p p ( g c d ( a ，b ) ) = g c d ( p p ( a ) ，p p ( b ) ) 。 2 3 2 多项式的基本运算 多项式a r 【x 】，由一个有限序列( ao ，口。) 构成，a 表示为如下： a j 口f x = 口z ”+ 口肘一l x 肘一1 + + 口l 石1 + 口o ，a ，z ，o i m 对于一个整数r n 1 ( 特殊的r = 2 “或者f 2 3 2 ) ，一个整数a 以r 为基的表示如 下：a _ 口m ，肼+ 口。一l ，”- 1 + + 口l ，1 + 口o = 口，a j o ，r 1 ) ，o i m 可以看出一个多项式的表示和一个整数的表示是如此的相似，如果把多项式放 在模r 的环上i p z ，= o ，r 1 ) 进行加法和模r 的乘法，这种相似性更加明显。在 计算机代数中，这种相似性是非常重要的，许多关于整数的算法，只要做稍许改 动就可以适用于多项式，如乘法，带余除法，最大公约数，中国剩余计算。 a 等口f x ( o i n ) ，b = 岛x ( o i m ) 冬b r 【x 】 c _ a + b ：( 口f + 6 f ) 石c ，x ( o i n ) 加法q = 口，+ 岛在环r 上进行，同整数的加法一样，这里我们假设i i 同。 算法2 4 多项式加法 输入：a = q x 。( o i n ) ，b = 包工( o i m ) 如r x 】 输出：闸+ b = ( 口，+ 6 ，) 工= c j x 1 内i ri = o ，nd o c j = 口i + 饥 2 r 醐】n 1 c = q x ( 0 i n ) 我们考虑2 个多项式a = 4 ，z ( o i n ) ，b = 包z ( o i m ) ，两个的乘积 为萨a b = “z ( o k n 斗姐) ，它的系数是q = 口，乃( o i n ，o j m ，i + j = k ， o k m + n ) 。 算法2 5 多项式乘法 输入：a - 口，z ( o i n ) ，b = 包工( o i m ) 啪r x 】 输出：c = a b 1 f 0 i ri = o ，nd od ，= 口f 石7 b 2 “加mc 。d f ( o i m ) 8 第二章多项式因式分解基础 带余除法：在许多的应用中，模整数的计算扮演着重要的角色，例如在程序测 试，数据库的完整性，编码理论和密码学中都有很重要的应用。对于处理整数问 题，模方法很成功，模方法在求整数最大公因子和因式分解中有着重要作用。模 方法的基本工具是带余除法，考虑整数钆b ，b 不为零，要找出商q ，和余数r ，a - q b + r ， l r i i b i o 算法2 6 多项式的带余除法 输入：a - 口，x ( o i n ) ，b = 缸( o i m ) 所有q ，6 i r ，r 是交换环 输出：q ，r r x ，a = _ q b 竹并且d e g ( r ) ，m 1 r = a 2 f o ri = n - m ，n - m - 1 ，od 0 3 i f d e g ( r ) = n i l e ng f = l c ( r | 6 朋，r = r - g f x 。b e l s e g i ：0 4 r e t 哪 q = g f 工和r