书名：信息安全数学基础pdf/doc/txt格式电子书下载

推荐语：

作者：李超,付绍静

出版社：电子工业出版社

出版时间：2015-11-01

书籍编号：30468261

ISBN：9787121275050

正文语种：中文

字数：148446

版次：1

所属分类：教材教辅-大学

版权信息

书名：信息安全数学基础

作者：李超　付绍静

ISBN：9787121275050

版权所有 · 侵权必究

编委会名单

“信息化与信息社会”系列从书编委会名单

编委会主任 曲维枝

编委会副主任 周宏仁 张尧学 徐愈

编 委会委贝 何德全 邬贺铨 高新民 高世辑 张复良 刘希俭

刘小英 李国杰 秦海 赵泽良 杜链 朱森第方欣欣 陈国青 李一军 李琪 冯登国

编委会秘书处 廖瑾 刘宪兰 刘博 等

高等校学信息安全专业系列教材编委会名单

专业编委会顾问 以汉字拼音为序）

蔡吉人 方滨兴 何德全 刘小英 宁家骏 曲成义沈昌祥 邬贺拴 熊澄宇 赵泽良

专业编委会主仟 冯登国

专业编委会委员 以汉字拼音为序）

陈克非 封化民 韩臻 胡爱群 黄继武 黄刘生 李超 李建华 刘建伟 陆哲明 马建峰 秦玉海 秦志光 石文昌 王怀民 王清贤 王小云 向宏 谢冬青 杨义先 俞能海 曾庆凯 张宏莉 张焕国 郑东

作者简介

李超 博士，国防科技大学教授、理学院应用数学专业和计算机学院密码学专业的博士生导师，担任中国密码学会理事、湖南省数学会常务理事、湖南省计算数学与应用软件学会理事。在《IEEE Transactions on Information Theory》和《Science in China》等国内外学术刊物上合作发表（录用）论文60余篇，在CRYPT、FSE和SAC等国际会议上合作发表论文20余篇，其中被SCI检索40余篇、被EI检索50余篇，获得2010年澳洲密码年会最佳论文奖、2010年中国密码年会最佳论文奖和2014年中国密码年会最佳论文奖。在Springer出版社、高等教育出版社和科学出版社等出版社合作出版会议录2部、专著2部、教材6部。主持国家自然科学基金和国家密码发展基金等10余项科研任务，获军队科技进步一等奖1项，部委级科技进步二等奖1项、三等奖2项，国家教育部霍英东优秀青年教师奖1项，军队院校育才奖金奖和银奖各1项。

付绍静 博士，国防科技大学计算机学院副教授，日本IEICE学会会员，中国计算机学会会员，中国密码学会会员。在《Designs，Codes and Cryptography》《Information Science》和《中国科学》等国内外学术期刊和学术会议上发表论文30余篇，其中作为第一作者发表SCI收录论文12篇，主持国家自然科学基金和信息安全国家重点实验室开放课题等8项科研任务。作为技术骨干参与了国家自然科学基金、国家863项目、973项目等多项科研任务。担任《IEEE Transactions on Information Theory》《Information Science》《Information Processing Letters》和《IEICE Transactions on Fundamentals》等国际期刊的审稿人，是ICISC 2012 （韩国）、WISA2012（韩国）、ICISC 2013 （韩国）等10多个著名国际会议的程序委员会委员。申请国家发明专利2项。获军队院校育才奖银奖1项。

总序

信息化是世界经济和社会发展的必然趋势。近年来，在党中央、国务院的高度重视和正确领导下，中国信息化建设取得了积极进展，信息技术对提升工业技术水平、创新产业形态、推动经济社会发展发挥了重要作用。信息技术已成为经济增长的“倍增器”、发展方式的“转换器”、产业升级的“助推器”。

作为国家信息化领导小组的决策咨询机构，国家信息化专家咨询委员会按照党中央、国务院领导同志的要求，就中国信息化发展中的前瞻性、全局性和战略性的问题进行了调查研究，提出了政策建议和咨询意见。信息化所具有的知识密集的特点，决定了人力资本将成为国家在信息时代的核心竞争力。大量培养符合中国信息化发展需要的人才是国家信息化发展的一个紧迫需求，也是中国推动经济发展方式转变，提高在信息时代参与国际竞争比较优势的关键。2006年5月，中国公布《2006—2020年国家信息化发展战略》，提出“提高国民信息技术应用能力，造就信息化人才队伍”是国家信息化推进的重点任务之一，并要求构建以学校教育为基础的信息化人才培养体系。

为了促进上述目标的实现，国家信息化专家咨询委员会致力于通过讲座、论坛、出版等各种方式推动信息化知识的宣传、教育和培训工作。2007年，国家信息化专家咨询委员会联合教育部、原国务院信息化工作办公室成立了“信息化与信息社会”系列丛书编委会，共同推动“信息化与信息社会”系列丛书的组织编写工作。编写该系列丛书的目的，是力图结合中国信息化发展的实际和需求，针对国家信息化人才教育和培养工作，有效梳理信息化的基本概念和知识体系，通过高校教师、信息化专家、学者与政府官员之间的相互交流和借鉴，充实中国信息化实践中的成功案例，进一步完善中国信息化教学的框架体系，提高中国信息化图书的理论和实践水平。毫无疑问，从国家信息化长远发展的角度来看，这是一项带有全局性、前瞻性和基础性的工作，是贯彻落实国家信息化发展战略的一个重要举措，对于推动国家的信息化人才教育和培养工作，加强中国信息化人才队伍的建设具有重要意义。

考虑到当时国家信息化人才培养的需求，各个专业和不同教育层次（博士生、硕士生、本科生）的需要，以及教材开发的难度和编写进度时间等问题，“信息化与信息社会”系列丛书编委会采取了集中全国优秀学者和教师，分期分批出版高质量的信息化教育丛书的方式，结合高校专业课程设置情况，在“十一五”期间，先后组织出版了“信息管理与信息系统”、“电子商务”、“信息安全”三套本科专业高等学校系列教材，受到高校相关专业学科以及相关专业师生的热烈欢迎，并得到业内专家和教师的一致好评和高度评价。

但是，随着时间的推移和信息技术的快速发展，上述专业的教育面临着持续更新、不断完善的迫切要求，日新月异的技术发展及应用变迁也不断对新时期的建设和人才培养提出新要求。为此，“信息管理与信息系统”、“电子商务”、“信息安全”三个专业教育需以综合的视角和发展的眼光不断对自身进行调整和丰富，已出版的教材内容也需及时进行更新和调整，以满足需求。

这次，高等学校“信息管理与信息系统”、“电子商务”、“信息安全”三套系列教材的修订是在涵盖第1版主题内容的基础上进行的更新和调整。我们希望在内容构成上，既要保持原第1版教材基础的经典内容，又要介绍主流的知识、方法和工具，以及最新的发展趋势，同时增加部分案例、实例或新的课程教材，使每一本教材都有明确的定位，分别体现“信息管理与信息系统”、“电子商务”、“信息安全”三个专业领域的特征，并在结合中国信息化发展实际特点的同时，选择性地吸收国际上相关教材的成熟内容。

对于这次三套系列教材（以下简称系列教材）的修订，我们仍提出了基本要求，包括信息化的基本概念一定要准确、清晰，既要符合中国国情，又要与国际接轨；教材内容既要符合本科生课程设置的要求，又要紧跟技术发展的前沿，及时地把新技术、新趋势、新成果反映在教材中；教材还必须体现理论与实践的结合，要注意选取具有中国特色的成功案例和信息技术产品的应用实例，突出案例教学，力求生动活泼，达到帮助学生学以致用的目的，等等。

为力争修订教材达到我们一贯秉承的精品要求，“信息化与信息社会”系列丛书编委会采用了多种手段和措施保证系列教材的质量。首先，在确定每本教材的第一作者的过程中引入了竞争机制，通过广泛征集、自我推荐和网上公示等形式，吸收优秀教师、企业人才和知名专家参与写作；其次，将国家信息化专家咨询委员会有关专家纳入各个专业编委会中，通过召开研讨会和广泛征求意见等多种方式，吸纳国家信息化一线专家、工作者的意见和建议；最后，要求各专业编委会对教材大纲、内容等进行严格的审核。

我们衷心期望，系列教材的修订能对中国信息化相应专业领域的教育发展和教学水平的提高有所裨益，对推动中国信息化的人才培养有所贡献。同时，我们也借系列教材修订出版的机会，向所有为系列教材的组织、构思、写作、审核、编辑、出版等做出贡献的专家学者、教师和工作人员表达我们最真诚的谢意！

应该看到，组织高校教师、专家学者、政府官员以及出版部门共同合作，编写尚处于发展动态之中的新兴学科的高等学校教材，有待继续尝试和不断总结经验，也难免会出现这样那样的缺点和问题。我们衷心希望使用该系列教材的教师和学生能够不吝赐教，帮助我们不断地提高系列教材的质量。

2013年11月1日

序言

“十一五”期间，由国家信息化专家咨询委员会牵头，教育部信息安全专业类教学指导委员会有关领导、学者组织，众多信息安全专业著名专家和教师参与开发，并由电子工业出版社出版的“高等学校信息安全专业系列教材”，由于在体系设计上较全面地覆盖了新时期信息安全专业教育的各个知识层面，包括宏观视角上对信息化大环境下信息安全相关知识的综合介绍，对信息安全应用发展前沿的深入剖析，以及对信息安全系统建设各项核心任务的系统讲解和对一些重要信息安全应用形式的讨论，在“高等学校信息安全专业系列教材”面世后，受到高校该专业学科及相关专业师生的热烈欢迎，得到业内专家和教师的好评和高度评价，被誉为该学科专业教材中的精品系列教材。

但是，随着信息技术的快速发展，信息安全专业教育面临着持续更新、不断完善的迫切要求，其日新月异的技术发展及应用变迁也不断对新时期信息安全建设和人才培养提出新的要求。为此，信息安全专业教育需以综合的视角和发展的眼光不断对教学内容进行调整和丰富，已出版的教材内容也需及时进行更新、修改和补充，以满足需求。

这次修订，除对“高等学校信息安全专业系列教材”第1版各册教材的主题内容进行了相应更新和调整外，同时对系列教材的总体架构进行了调整并增加了3个分册，即《信息安全数学基础》、《信息安全实验教程》和《信息隐藏概论》。

调整后的教材在体系架构和内容构成上既保持了基础的经典内容，又介绍了主流的知识、方法和工具，以及最新发展趋势，同时增加了部分案例或实例。使得系列中的每一本教材都有明确的定位，充分体现了国家“信息安全”的领域特征，在结合中国信息安全实际特点的同时，还注重借鉴国际上相关教材中适于作为信息安全本科教育知识的成熟内容。

我们希望这套修订教材能够成为新形势下高等学校信息安全专业的精品教材，成为高等学校信息安全专业学生循序渐进了解和掌握专业知识不可或缺的教科书和知识读本，成为国家信息安全新环境下从业人员及管理者学习信息安全知识的有益参考书。

高等学校信息安全专业系列教材编委会

2013年10月于北京

前言

随着信息技术的不断发展，信息安全的内涵也在不断地延伸。从最初的信息保密性发展到信息的保密性、完整性、可用性和不可否认性，进而发展到网络攻防、安全控制、安全测评和安全管理等多方面的理论与技术。

近半个世纪以来，信息安全有了很大的发展，数学研究对信息安全的发展起了巨大的推动作用。20世纪70年代公开密钥密码体制的提出，是信息安全领域的一场革命。目前采用的两种主要的公开密钥密码体制（RSA密码体制和椭圆曲线密码体制）均源于数论（大整数分解理论和椭圆曲线算术理论）。21世纪初美国公布的高级加密标准（AES算法）是当前信息安全领域的研究热点，该算法的设计采用了有限域上基本代数运算。近年来，人们对于数字签名、身份认证、密钥共享和多方安全计算等问题，均采用了数论工具（指数和估计）和组合工具（组合设计和Matroid理论）。与此同时，信息领域为数学提出了大量的数学问题，也促进了数学的发展，增强了数学研究的活力。

本书主要介绍从事信息安全研究所需要的基本数学知识，包括数论、代数、组合、信息论和计算复杂性等数学理论与方法。与其他同类型的教材相比，本书更加关注知识结构的合理性，更加关注知识结构的系统性，更加关注知识结构的应用性。在知识结构的合理性方面，按照由浅入深、由易入难的理念组织教材内容，编写过程中力求做到叙述自然流畅，文字生动活泼，例题充实新颖；在知识结构的系统性方面，突出数论、代数、组合、信息论和计算复杂性的一体化融合，前后内容相互呼应，相互支撑。在知识结构的应用性方面，突出教材内容在信息安全领域中的应用。数论部分给出了代换密码、RSA算法、Diffie-Hellman协议的数学原理刻画；代数部分给出了AES算法、EIGmal算法、Schnorr算法和DSS算法的数学原理刻画；组合部分给出了Hash函数和Bent函数的设计与分析方面所涉及的组合知识；信息论部分给出了完善保密性的信息论刻画；计算复杂性部分给出了基于计算安全的密码方案分析原理的刻画。

本书是作者长期从事信息安全教学和科研基础上完成的。其研究工作先后得到国家自然科学基金项目（61070215、61103191和61103192）、国家863项目（2011AA7114065和2012AA7114065）、国家973项目（2013CB338002和613203032012）的资助。书中前三章由李超编写，后两章由付绍静编写，全书由李超负责统稿。本教材内容已经在国防科学技术大学计算机学院信息安全本科专业进行了多次教学实践。

由于作者水平所限，书中难免会有不妥和错误之处，恳请读者批评指正。

作者

2014年6月于长沙

第1章 数论基础

数论研究整数环中整数最基本性质，整除理论、同余理论和不定方程求解构成数论的基本内容。随着信息技术的飞速发展，数论所涉及的知识在信息领域特别是信息安全领域具有广泛的应用，公钥密码标准RSA算法是基于大整数分解困难性而设计的，通信系统中广泛使用的Diffie-Hellmen协议与整数的同余和原根密切相关。掌握数论的基本知识，对于从事信息安全理论与应用研究具有重要作用。

1.1 整数的整除

全体整数的集合通常用Z来表示，即

在整数集合Z中，两个整数可以进行加、减、乘三种运算，并且运算后的结果仍为整数。但两个整数进行除法运算后所得的结果未必为整数，比如4除以2所得结果为2，它是一个整数，而4除以3所得结果为，它不是整数。

定义1.1 设a，b是任意两个整数，b≠0，如果存在整数c，使得a=bc，则称b整除a，记做b|a，否则称b不整除a，记做ba。

如果有b|a，称b为a的因数，a为b的倍数。显然±1是任何整数的因数，所有的非零整数均为0的因数。由整除的定义，易知如下性质成立：

（1） 如果c|b，b|a，则c|a；

（2）如果c|b，c|a，则对任意m，n∈Z，均有c|（ma+nb）；

（3）如果b|a，且a≠0，则|b|≤|a|；

（4）如果a|b，b|a，则 a=b，即a=±b。

例1.1 证明：对任意正整数n，均有6|n（n+1）（2n+1）。

证明 当n=1时，n（n+1）（2n+1）=1×2×3=6，它是6的倍数，结论成立。

假设当n=k时，结论成立，即

则当n=k+1时，有

由归纳假设，6|k（k+1）（2k+1），并且6|6（k+1）²，从而根据整除的性质（3），得到

由归纳法原理，6|n（n+1）（2n+1）对任意正整数n成立。

例1.2 如果m，n，r，q∈Z，并且（m-p）|（mn+pq），证明（m-p）|（mq+np）。

证明 由于

上式右边三项都是m-p的倍数，从而有

定理1.1（带余除法） 设a，b∈Z，b≠0，则存在唯一的q，r∈Z，使得a=bq+r，这里0≤r＜|b|。

证明 不妨设b>0。当b<0时，类似可证。

考虑如下整数序列

则对任意a∈Z，必存在q∈Z，使得

令r=a-qb，则0≤r<b，并且a=r+qb，存在性得以证明。

下面讨论q和r的唯一性。

如果a=q₁b+r₁=q₂b+r₂，这里0≤r₁，r₂<b，则

若q₁≠q₂，则|r₂-r₁|≥b，这与0≤r₁，r₂<b矛盾！故q₁=q₂，从而r₁=r₂，唯一性得以证明。□

定义1.2 设a，b∈Z，b≠0，如果a=bq+r，这里0≤r＜|b|，则称q为b除a所得商，r为b除a所得的余数。

利用带余除法容易判定两个整数的整除关系，即定理1.2。

定理1.2 设a，b∈Z，b≠0，则b|a当且仅当b除a所得余数为0。

例1.3 从176～545的所有整数中，13的倍数有多少个？

解 对实数x而言，记［x］为小于或等于x的最大整数。由带余除法，从1～176的所有整数中，13的倍数有个，从1～545的所有整数中，13的倍数有个，从而从176～545的所有整数中，13的倍数有41-13=28个。□

定义1.3 设d，a₁，a₂，…，a_n∈Z，并且a₁，a₂，…，a_n不全为0，如果对每个a_i，均有d|a_i，则称d为a₁，a₂，…，a_n的一个公因数。整数a₁，a₂，…，a_n的所有公因数中最大的正因数称为a₁，a₂，…，a_n的最大公因数，记为（a₁，a₂，…，a_n）。

对于任意一组不全为零的整数a₁，a₂，…，a_n，由于不为零整数的因数只有有限个。从而a₁，a₂，…，a_n的公因数也只有有限个，故其最大公因数一定存在。如何计算最大公因数（a₁，a₂，…，a_n），这是整除理论中一个基本问题。下面介绍求最大公因数的辗转相除法。

定理1.3 设a，b，c∈Z，并且b≠0，如果

则（a，b）=（b，c）。

证明 设（a，b）=d₁，（b，c）=d₂。由于（a，b）=d₁，则d₁|a，d₁|b，又c=a-bq，故d₁|c，从而d₁为b和c的一个公因子，于是d₁≤d₂。同理可证d₂≤d₁，故 （a，b）=（b，c）。□

由定理1.3，可以求两个不全为0的整数的最大公因数。

设a，b∈Z，并且a，b不全为0，不妨设b≠0。由带余除法，必存在正整数n，满足

由定理1.3，得到

上面求两个整数的最大公因数的方法称为辗转相除法，由辗转相除法的推导过程反推回去，便有如下定理1.4。

定理1.4 设a，b∈Z，a，b不全为0，则存在m，n∈Z，使得

一般而言，定理1.4中m，n不一定唯一，比如

由定理1.4可以看出，a和b的任意公因数都是a和b的最大公因数的因数。反过来，a和b的最大公因数的因数也一定是a和b的公因数。这说明两个不全为零的整数的公因数与它们最大公因数的因数一致。

例1.4 计算（2295，4471），并求整数x，y，使得（2295，4471）=2295x+4471y。

于是（2295，4471）=17。利用上述算式可得

故（2295，4471）=4471×（-58）+2295×113。□

用辗转相除法可以求两个整数的最大公因数，而多个整数的最大公因数的求法可以转化为两个整数的最大公因数的求法，即有如下定理1.5。

定理1.5 设a₁，a₂，…，a_n是一组全不为0的整数，并且

则（a₁，a₂，…，a_n）=d_n。

证明 由条件d_n|a_n，d_n|d_n-1，又d_n-1|a_n-1，d_n-1|d_n-2，故d_n|a_n-1，d_n-1|d_n-2。以此类推，最后得到

即d_n为a₁，a₂，…，a_n的一个公因数。

设d为a₁，a₂，…，a_n的任一个公因数，则d|a₁，d|a₂，从而d|d₂。又d|a₃，从而d|a₃，故d|d₃。由此类推，最后得到d|d_n。于是d≤d_n，d_n是a₁，a₂，…，a_n的最大公因数。□

对于一组给定的不全为0的整数a₁，a₂，…，a_n，在求其最大公因数时，考虑到数0是任何非零整数的倍数，不失一般性，我们只需要求那些不为0的整数的最大公因数，并利用定理1.5由辗转相除法求得。

定义1.4 设a，b是两个不为0的整数，如果（a，b）=1，则称a与b互素。

定理1.6 设a，b∈Z，则（a，b）=1当且仅当存在m，n∈Z，使得ma+nb=1。

证明 如果（a，b）=1，由定理1.4可知存在m，n∈Z，使得

反过来，如果ma+nb=1，则对a与b的任意公因子d，均有d|a，d|b，从而d|1，又1显然为a与b的公因子，从而（a，b）=1。□

利用定理1.6，可以推出互素的下述基本性质：

（1） 如果（a，b）=1，（a，c）=1，则（a，bc）=1；

（2） 如果a|bc，并且（a，b）=1，则a|c；

（3） 如果a|c，b|c，并且（a，b）=1，则ab|c。

与公因数与最大公因数相应的，还有公倍数与最小公倍数的概念。

定义1.5 设a₁，a₂，…，a_n，m∈Z，如果对每个a_i，均有a_i|m，则称m为a₁，a₂，…，a_n的公倍数，a₁，a₂，…，a_n的一切公倍数中最小的正整数，叫做a₁，a₂，…，a_n的最小公倍数，记为[a₁，a₂，…，a_n]。

同最大公因数一样，最小公倍数是否存在？如果存在，又怎样求最小公倍数呢？首先，由于最小公倍数只涉及整数的整除性，而整数的整除性与整数的正负号无关，故不妨设所有a_i均为正整数。其次，当a₁，a₂，…，a_n均为正整数时，乘积a₁a₂…a_n显然为a₁，a₂，…，a_n的一个公倍数，从而a₁，a₂，…，a_n的最小公倍数一定存在。

定理1.7 设a，b为两个正整数，则下列结论成立：

（1） a，b的所有公倍数就是［a，b］的所有倍数；

(2).

证明 设m是a，b的任一公倍数，不妨m>0，则存在正整数k和l，使得m=ak=bl。令a=a₁（a，b），b=b₁（a，b），则（a₁，b₁）=1，并且

于是a₁k=b₁l。又由于（a₁，b₁）=1，故根据互素的性质（2）得到b₁|k，不妨设k=b₁t，t∈Z，因此有

从而a，b的公倍数都是的倍数。又是a和b的公倍数，从而其为a，b的最小公倍数，即

多个整数的最小公倍数，可以通过两个整数的最小公倍数求得。从而有如下定理。

定理1.8 设a₁，a₂，…，a_n（n≥2）为正整数，并且［a₁，a₂］=m₂，［m₂，a₃］=m₃，…，［m_n-1，a_n］=m_n，则

证明 由定理1.7，m_i|m_i+1（2≤i≤n-1），a₁|m₂，a_i|m_i（2≤i≤n），故m_n是a₁，a₂，…，a_n的一个公倍数。又设m为a₁，a₂，…，a_n的任意公倍数，则a₁|m，a₂|m，于是m₂|m。再由a₃|m，故m₃|m。以此类推，最后得m_n|m，于是m_n为a₁，a₂，…，a_n最小公倍数。□

例1.5 计算［2295，4471］。

解 由例1.4可知，（2295，4471）=17，故

1.2 算术基本定理

在正整数中，1的正因数只有它本身，任何大于1的整数n都至少有两个正因数，即1和它本身，这两个因子称为n的平凡因子。

定义1.6 一个大于1的整数，如果它的正因数只有1和它本身，则称它为素数（或者质数），否则称它为复合数。

100以内的全部素数为2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，共25个。数论中许多著名问题都与素数有关，比如哥德巴赫猜想和孪生素数问题。

观察发现：6=3+3，8=3+5，10=5+5，12=5+7，14=7+7，16=3+13，18=5+13，20=3+17，22=3+19，24=7+17，…

1742年，德国数学家哥德巴赫提出了“每个大于2的偶数均可以表示为两个素数之和”的著名猜想，两百多年来，数学家们一直试图证明这个猜想。中国数学家陈景润在1966年证明了“每个充分大的偶数都可以表示为一个素数和一个不超过两个素数的乘积之和”，成为至今关于这一猜想的最好结果。

同样，观察发现：（3，5），（5，7），（11，13），（17，19），（29，31），…，（101，103），…，（10 016 957，10 016 959），…，都是差为2的素数对，称为孪生素数。事实上，已知小于100 000的孪生素数有1224对，小于1 000 000的孪生素数有8164对。于是人们猜想孪生素数有无穷对，这是一个至今未能证明的数学难题。可喜的是，中国数学家张益唐在2013年证明了存在无穷多对素数，其差小于7000万。尽管7000万是一个很大的数字，但终于有人正式证明存在无穷多组间距小于定值的素数对，这是孪生素数问题的重大突破。

素数的性质、计数、分布与判定是数论研究中重要问题。素数作为一类特殊的正整数，它具有如下基本性质：

性质1 如果p为素数，则对任意整数n，p|n和（p，n）=1有且仅有一个成立；

性质2 如果p为素数，p|mn，则p|m或者p|n；

性质3 如果n≥2为合数，则必有素数p|n，并且。

关于素数的计数，早在公元前3世纪，古希腊数学家欧几里得（Euclid）就证明了如下定理1.9。

定理1.9 素数有无穷多个。

证明 反证法。假设素数只有有限多个，设p1，p2，…，pm 是全部素数，令n=p1p2…pm+1，则p1，p2，…，pm都不是n的因子，否则某个p

....