数论算法
作者： 姜建国 等编著
出版社：西安电子科技大学出版社 2014-5-1
简介： 数论是研究整数性质的一个数学分支，它历史悠久，有着强大的生命力。数论问题叙述简明，“很多数论问题可以从经验中归纳出来，并且仅用三言两语就能向一个行外人解释清楚，但要证明它却远非易事”，因而有人说：“用以发现天才，在初等数学中再也没有比数论更好的课程了”，所以在国内外各级各类的数学竞赛中，数论问题总是占有相当大的比重。 随着科学技术的发展，将经典理论与现代应用相结合已成为发展的一种趋势，故数论的应用领域也逐渐扩展开来，顺应发展趋势，推动数论应用，正是本书的编写目的和出发点。实际上，目前数论的有关理论和方法在计算机、通信等领域有着大量的应用，尤其在信息和网络安全、数字信号处理等方面应用更加广泛，而本书也主要从应用角度出发来研究数论问题，尤其是有关整数运算中实用的方法和具体算法。 本书共分9章，各章的主要内容概括如下： 第1章整数的可除性，主要介绍整除概念及与其相关的问题，如整除的定义及其性质，重点介绍了求最大公因数的有关算法。 第2章数论函数，给出了几种常用数论函数并讨论了其性质，同时介绍了函数的积性和函数的Dirichlet乘积等概念及性质。 第3章同余及其运算，介绍了整数按同余的分类、同余条件下幂函数的快速运算算法，给出了不定方程的解法、矩阵的同余运算和同余在信息安全和随机数生成方面的应用实例。 第4章同余方程，介绍了同余方程的概念，讨论了同余方程的解数及解法，给出了一次同余方程组和素数模的同余方程的求解方法及同余方程在秘密共享和数据加密方面的应用实例。 第5章二次同余方程与平方剩余，主要针对特殊的同余方程（即二次同余方程的求解）给出了问题的分类、化简和转换方法，重点介绍了利用勒让德符号和雅可比符号判断方程的可解性和模数为素数时的求解方法。 第6章原根与离散对数，从整数的阶与原根的定义出发，给出了阶的性质、原根及其判断方法与计算方法、 n次剩余以及利用原根解特殊高次方程的方法，最后给出了原根和离散对数在密钥管理、信息加密和随机数生成等方面的应用。 第7章连分数，介绍了连分数的概念和有关性质，重点介绍了用连分数逼近实数和有理分数的方法。 第8章素性测试和整数分解，主要针对素数的精确判断方法的复杂度问题，介绍了素数的概率测试，以及正整数的分解方法。 第9章有限域，主要讨论与数论相关的群、环、域的概念和性质，重点介绍了同余运算与群、环、域的关系，以及利用同余运算实现有限域的构造等问题。 本书具有如下几个特点： (1) 紧密结合研究生教学实际和教学大纲，在内容编排上力求深入浅出，循序渐进；在讲解理论和原理的同时，给出了大量例题，并在讲解例题时，重视对解题思路的分析，有利于提高读者独立分析问题和解决问题的能力。 (2) 针对工科研究生教学要求，书中除了数论的理论成果外，还结合实际应用，搜集并整理了相关问题的实用算法，尽力做到与时俱进，重在实用。 (3) 注重教学思想方法的渗透和解题水平的提高。拾众家之所长，精选题目，使例题和习题均具有典型性和代表性。 (4) 本书在撰写时，参阅了国内外大量的相关资料，并凝结了作者十多年来从事研究生“数论算法”课程教学的体会，力求内容新颖，取舍得当。 本书是在西安电子科技大学校内教材“数论算法”的基础上，经过多年的试用，并吸取了老师和学生大量的修改意见，不断完善而成的。 西安电子科技大学出版社对本书的出版给予了热情的关怀和支持，尤其是出版社李惠萍老师对书稿严格把关，在内容的叙述方式上提出了很多有益的建议，使作者深受教益，在此表示感谢。 由于作者水平有限，书中不足之处在所难免，恳请读者批评指正，使本书得以不断改进和完善。
