《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版

所需积分/C币:50 2019-05-10 20:46:14 22.88MB PDF
收藏 收藏 1
举报

数论基础及其应用 作者:沈忠华 编著 出版时间:2015年版 内容简介   《数论基础及其应用》为数学与密码学交叉学科的特色教材,内容包括整除理论、同余、连分数、同余方程、原根。《数论基础及其应用》以数论知识为主线,有机地融入数论应用(主要是在密码学中的应用)的内容,理论与应用的知识的广度和深度都适度。《数论基础及其应用》可作为数学与应用数学专业、信息与计算科学专业和信息安全专业的本科生基础教材,也可作为密码学与信息安全专业的研究生教材。 目录 前言 第1章整除理论 1.1带余数除法 1.2辗转相除法 1.3最大公约数的性质 1.4最小公倍数 1.5算术基本定理 第2章同余
普通高等教育“十二五”规划教材 数论基础及其应用 沈忠华编著 学出版社 北京 内容简介 本书主要介绍初等数论的基础理论,以及它们在密码学、信息安全等领 域中的应用.全书共分11章,包括整除理论、同余、简单密码、剩余系、不 定方程、同余方程、公钥密码、二次剩余、原根、实数的表示、平方和等内 容.每章末附有习题 本书适合作为普通高等院校数学类、计算机科学类、信息安全或电子与 通信工程类高年级本科生和研究生的教材,也可作为相关领域研究人员的参 考书 图书在版编目(C|P)数据 数论基础及其应用沈忠华编著.一北京:科学出版社,2015.7 普通高等教育“十二五”规划教材 ISBN978-7-03-044295-6 L.数…Ⅱ①沈…Ⅲ.①数论-高等学校-教材Ⅳ.①O156 中国版本图书馆CIP数据核字(2015)第100378号 责任编辑:姚莉丽/责任校对:蒋萍 责任印制:霍兵/封面设计:迷底书装 学出撤出版 北京东黄城根北街16号 邮政编码:100717 http://www.sciencep.com 文林印务有隈公司印刷 科学出版社发行各地新华书店经销 2015年7月第版开本:720×10001/16 2015年7月第一次印刷印张:11314 字数:236000 定价:32.00元 (如有印装质量问题,我社负责调换) 前言 数论是数学的一个历史悠久的分支,主要研究整数的性质和规律.在很长的 个历史时期内,数论被认为是一门没有应用价值的“纯”理论学科.20世纪中期以 来,数论的理论和方法在许多理论学科和应用学科领域中都得到了广泛而深入的应 用,尤其是在密码学中的应用,不仅推动了密码学和信息安全技术的发展,也有力 地促进了数论与密码学、信息安全相关课题的研究,使之增添了新的活力 本书是在我们讲授数学专业“初等数论”和“数论及其应用”课程使用的讲义 的基础上形成的,曾在数学专业和应用数学专业本科生和研究生教学中使用,目的 是使学生在了解和掌握初等数论的基本理论和方法的同时,较多地了解数论在密码 学中的应用,拓宽知识视野,促进跨学科研究能力的养成在编写本书的时候,也考 虑到了其他专业的学生和科技人员对数论知识的需要 逻辑推导是数学研究的一个特点,数论研究尤是如此.培养学生利用逻辑推理, 由浅入深,由此及彼,不断发现新的数学真理的能力,是非常重要的.基于这一认 识,在内容安排上,本书力图让读者从已有的事实出发,去发现新的数学结论.因此, 在内容安排上,我们改变了“结论叙述一证明结论”的模式,尽量采用“已有结论 逻辑推理一新的结论”的模式,使新的数学真理自然地显现出来,让读者自己 推导和发现新的知识.我们的教学实践表明,这有助于培养学生的逻辑推理能力, 也提高了他们的学习兴趣 本书的编写得到了国家“十二五”密码研究规划课题、浙江省自然科学基金项 目、浙江省基础数学重点学科建设项目、浙江省重点建设教材项目和杭州市应用 密码学重点学科建设项目的支持.杭州师范大学理学院对本书的编写提供了有力 支持.杭州师范大学于秀源教授对本书稿提出了许多建设性的建议.借本书出版之 际,在此一并表示衷心的感谢 限于作者水平有限,本书谬误和不妥在所难免,恳切地希望读者和同行批评指 正 沈忠华 2014年11月 目录 前言 第1章整除理论 1.1带余数除法 1.2辗转相除法 1148 1.3最大公约数的性质 14最小公倍数 ………11 1.5算术基本定理 ………………16 第2章同余 21同余的基本性质 ………20 2.2计算星期几……………………………………………24 23循环比赛 …27 第3章简单密码 …………31 31仿射加密 31 32矩阵加密 39 第4章剩余系 ………49 41完全剩余系… 49 4.2简化剩余系 …………54 43 Euler定理, ,Fermat 定理…………………………………59 44数论函数 69 第5章不定方程 …………………70 51一次不定方程 70 5.2方程x2+y2=2… 76 第6章同余方程 ……82 6.1同余方程的基本概念 ………82 6.2孙子定理………………………………………87 6.3模p的同余方程 92 6.4素数模的同余方程 98 第7章公钥密码 103 7.1公钥密码系统 ……103 目录 7.2RSA加密 110 第8章二次剩余 …115 8.1素数模的二次同余方程 115 8.2 Legendre符号,二次互反律 120 83 Jacobi符号 ………………126 第9章原根 132 9.1指数及其基本性质 ·,··············.: ……………132 9.2原根与指标 136 9.3伪素数………………………142 第10章实数的表示 …………148 10.1连分数的基本性质……………148 10.2实数的连分数表示 153 10.3循环连分数 158 104实数的b进制表示 163 第11章平方和 …………169 111二平方之和………………………………………………169 11.2四平方之和 …………174 附录 ……………179 第1章整除理论 1.1带余数除法 在本书中,以Z表示全体整数的集合,N表示全体正整数的集合,除特别声明 外,字母a,b,C,…等均表示整数 设b是一个正整数.那么,互不相交的区间[bg,b(q+1)(q=0.,±1,±2,…)的 和集是实轴,因此,任何整数a必落在唯一的一个区间[bq,b(q+1)中,即存在唯 的整数q,bq≤a<b(q+1),于是a=qb+r,其中r=a-bq是唯一的,并且 0≤r<b.因此,我们有如下结论 定理11.1(带余数除法)设a,b∈Z,b>0,则存在唯一的一对整数q,r,使 得 qb+7,0≤r<b 注1在定理1.1.1中,称q是b除a的商,r是b除a的余数 定义1.1.1设a,b∈Z,b≠0,若|除a的余数是0,则称b整除a(记作 ba),称b是a的约数(因数,或因子),a是b的倍数;否则,称a不被b整除(记 为b和);若ba,1<b<a,则称b是a的真约数 由定义1.11可知,a与-a有相同的约数,±1与±a显然是它们的约数 下面的定理是显然的 定理1.1.2下面的结论成立: (1)若ba,则b除a的商是唯一的 (2)b(≠0)的所有倍数是0,±b,±2b,…; (3)ba,cb→cla; (4)ba,a≠0→|b≤a (5)ba,且|a|<|b→a=0; (6)ba1,ba2,m1,m2∈Z→ba1m1+a2m2 定义1.1.2一个大于1的整数,若除了数1和它自身外,没有另外的约数 则称为素数.除了1和它自身外,还有其他约数的数称为合数 由这个定义我们知道,一个大于1的整数,要么是素数,要么是合数 如果整数a(a≠0,±1)是合数,那么,a的正约数只有有限个,故必有最小的 设为d.若d不是素数,则有真约数d1,d1>1,d1ld,d>d1,而且d1|a.这与d的 2 第1章整除理论 最小性矛盾,故d必是素数.因此,存在整数q,使得a=dq,于是|a≥d2,即 d≤√a.因此,有如下结论 定理11.3任一整数a(a≠0,±1)的大于1的最小约数d是素数;若d≠a 则d≤√a 定理1.1.3告诉我们一个判定整数素性的方法:如果一个整数a不被不超过 √a的素数整除,它一定是素数 例11.1判定97是否是素数 解由于不超过√97的素数2,3,5,7都不能整除97,所以97是素数 利用定理11.2还可以逐个列出素数.这就是 Eratosthenes筛法.下面是一个 具体的例子 例1.12写出不超过100的所有的素数 解将不超过100的正整数排列如下 2345 112134516171929 21222324252627282930 3133363738394 41443445464748495 5345565596 61芻66667686970 71773747767787989 8828384$$687888990 按以下步骤进行: (i)删去1,剩下的后面的第一个数是2,2是素数; (i)删去2后面的被2整除的数,剩下的2后面的第一个数是3,3是素数; (i)再删去3后面的被3整除的数,剩下的3后面的第一个数是5,5是素数 (iv)再删去5后面的被5整除的数,剩下的5后面的第一个数是7,7是素数; 照以上步骤可以依次得到不超过100的所有的素数2,3,5,7,11,…,97 要指出的是, Eratosthenes筛法在理论上是可行的;但在实际应用中,由于需要 大量的计算,是不可取的 定理11.1虽然简单,却是数论的基础.下面我们给出它的一个应用 设b>1是整数.那么,对于任何正整数a,由定理1.1.1,有整数k,使得 a=q1b+a0,0≤a0≤b-1,q≥b, 1.1带余数除法 3 b+ 0≤a1≤b-1,q2≥b, gk-1=qkb+ak-1,0≤ak-1≤b-1,0<gk≤b-1, 其中诸a;与q1都是唯一确定的.记gk=ak,则0<ak≤b-1,并且 a=91b+a0=(92b+a1)b+a0=9262+a1b+ao =(3b+a2)b2+a1b+a0=93b3+a2b2+a1b+a0 akb+ak_1b-1+…+a1b+ 因此,有如下结论 定理1.1.4设b是大于1的整数,则任何正整数a都可以写成 akb+ak=1b-1+…+a1b+ 的形式,其中ak≠0,a1(0≤i≤k)是在0与b-1之间唯一确定的整数 定义1.1.3设b是正整数,n是正整数,并且 +ak-1b--1+…+a1b+ 其中ak≠0,0≤a≤b-1(0≤≤k),则称(ak,ak-1,…,a1,a)b是m的b进制表 示,称n是k+1位b进制数,k+1是n的b进制位数,a2(0≤i≤k)是n的b进 制表示的第a+1个位数码(或第a+1位数) 为了叙述方便,今后,对于十进制表示的数,将仍使用常规的写法 注2以[2表示不超过x的最大整数.若n=(ak,ak-1,…,a1,ao)b,ak≠0, 则 ≤7< k≤ login<(k+1) 即k 例1.1.3若n是整数,则n2被8除的余数只可能是0,1,或4 解整数n只可能是n=8q+r的形式,其中r=0,1,2,…,或7.直接计 算即可得到结论 习题1 1.证明定理11.2的结论(5) 2设p是n的最小素约数,n=p1,n1>1,证明:若p>yn,则n1是素数

...展开详情
试读 127P 《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
上传资源赚积分,得勋章
最新推荐
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版 50积分/C币 立即下载
1/127
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第1页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第2页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第3页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第4页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第5页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第6页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第7页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第8页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第9页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第10页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第11页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第12页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第13页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第14页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第15页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第16页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第17页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第18页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第19页
《数论基础及其应用》作者:沈忠华 编著 出版时间:2015年版第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >