引言、整除的概念、带余数除法.ppt

初等数论 黎琳 2016.03.01 1 n授课教师：黎琳 E-mail：， 办公地点：九教北310， 电话：51688637 n课件： 教务处课程平台/ 2 n教材 闵嗣鹤，严士健，初等数论（第三版），高等教 育出版社. n参考教材 1 潘承洞，潘承彪，初等数论（第三版），北京 大学出版社. 2罗森（KennethH.Rosen）,初等数论及其应用 (Elementary Number Theory(6th Edition).机械 工业出版社. 3科布茨，数论与密码学教程（第2版），世界图 书出版社. 3 课程设置 n整数的可除性 * 6学时 n不定方程 2学时 n同余 * 6学时 n同余式 * 4学时 n二次同余式与平方剩余 * 6学时 n原根与指标 * 4学时 n连分数 2学时 4 考核方式 n成绩评定主要包括平时成绩（含考勤、 作业、随堂测试）占50%，期末考试成绩 占50%； n期末采取闭卷笔试 5 序言 n数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整 除性、不定方程、同余式、连分数、素数（即质 数）分布 以及数论函数等内容，统称初等数论（ elementary number theory）。 n 初等数论是数论中不求助于其他数学学科的帮助 ，只依靠初等的方法来研究整数性质的分支。 n初等数论是信息安全专业的必修课，是密码学等 课的基础 6 发展历史 n初等数论的大部份内容早在古希腊欧几里德的 几何原本（公元前3世纪）中就已出现。欧几里 得证明了素数有无穷多个，他还给出求两个自然 数的最大公约数的方法，即所谓欧几里得算法。 欧几里得前330年 前275年，欧氏几何学 的开创者 ，古希腊数学 家，以其所著的 几何原本闻名于世 7 n我国古代在数论方面亦有杰出之贡献，现在一 般数论书中的“中国剩余定理”，正是我国古代 孙子算经中的下卷第26题，我国称之为孙 子定理。 约成书于四、五世纪 ，作者生平和编写年代 都不清楚。现在传本的 孙子算经共三卷。 卷下第31题，可谓是后 世“鸡兔同笼”题的始祖 ，后来传到日本，变成“ 鹤龟算”。 8 n近代初等数论的发展得益于费马、欧拉、拉格朗 日、勒让德和高斯等人的工作。 高斯17771855，德国 数学家、物理学家、天 文学家、大地测量学家 。 1801年，著有算术 探究，开始了现代数 论的新纪元。高斯还提 出：“数学是科学之王， 数论是数学之王”。 9 费马 法1601-1665，是数学史上 最伟大的业余数学家，提出了费马 大、小定理；在坐标几何，无穷小， 概率论等方面有巨大贡献。 哥德巴赫 1690-1764， 德国数学家；曾担任中学 教师，1725年到俄国， 被选为彼得堡科学院院士. 10 勒让德法17521833，在分 析学、数论、初等几何与天体 力学，取得了许多成果，是椭 圆积分理论奠基人之一。对数 论的主要贡献是二次互反律， 还是解析数论的先驱者之一. 雅可比德18041851，在偏 微分方程中，引进了“雅可比 行列式。对行列式理论作了奠 基性的工作，在代数学、变分 法、复变函数论、分析力学 、 动力学及数学物理方面也有贡献 11 欧拉17071783，瑞士数学家， 自然科学家。是数学史上最多产 的数学家，每年写出八百多页 的论文，无穷小分析引论、 微分学原理、积分学原理 等都成为数学中的经典著作。 希尔伯特德18621943， 他领导的数学学派是19世纪 末20世纪初数学界的一面旗 帜，希尔伯特被称为“数学 界的无冕之王”。著数论 报告等 12 n由于自20世纪以来引进了抽象数学和高等分析的 巧妙工具，数论得到进一步的发展，从而开阔了 新的研究领域，出现了代数数论、解析数论、几 何数论等新分支。 n近年来初等数论在计算机科学、组合数学、密码 学、代数编码、计算方法等领域内更得到了广泛 的应用，无疑同时也促进着数论的发展。 13 华罗庚19101985，是中国解析 数论、矩阵几何学、典型群、自 安函数论等多方面研究的创始人 和开拓者。以华氏命名的数学科 研成果很多。被列为芝加哥科学 技术博物馆中当今世界88位数学 伟人之一。 陈景润19331996，主要研究 解析数论，他研究哥德巴赫猜 想和其他数论问题的成就，至 今仍然在世界上遥遥领先。其 成果也被称之为陈氏定理。 14 王元193050年代至60年代初， 首先在中国将筛法用于哥德巴 赫猜想研究，并证明了命题3+4 ，1957年又证明2+3，这是中国 学者首次在此研究领域跃居世 界领先地位. 潘承洞，在解析数论研究方面 有突出贡献。主要成就涉及算 术数列中的最小素数、哥德巴 赫猜想研究，以及小区间上的 素变数三角和估计等领域。 15 几个著名数论难题 初等数论是研究整数性质的一门学科，历史上遗留 下来没有解决的大多数数论难题其问题本身容易搞懂， 容易引起人的兴趣，但是解决它们却非常困难。 其中，非常著名的问题有：哥德巴赫猜想 ；费尔马大 定理 ；孪生素数问题 ；完全数问题等。 16 1742年,由德国中学教师哥德巴赫在教学中首先发现 的。1742年6月7日，哥德巴赫写信给当时的大数学家 欧拉,正式提出了以下的猜想： 一个大于6的偶数可以表示为不同的两个质数之和。 陈景润在1966年证明了“哥德巴赫猜想”的“一个 大偶数可以表示为一个素数和一个不超过两个素数的 乘积之和”所谓的1+2，是筛法的光辉顶点，至 今仍是“哥德巴赫猜想”的最好结果。 1、哥德巴赫猜想： 17 2、费尔马大定理： 费马是十七世纪最卓越的数学家之一，他在数学 许多领域中都有极大的贡献，因为他的本行是专业的 律师，世人冠以“业余王子”之美称。在三百七十多 年前的某一天，费马正在阅读一本古希腊数学家戴奥 芬多斯的数学书时，突然心血来潮在书页的空白处， 写下一个看起来很简单的定理。 经过8年的努力，英国数学家 安德鲁怀尔斯 终于在 1995年完成了该定理的证明。 18 在密码学中应用 n 古典密码体制：代换密码 定义代换如下: a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 每个字母对应一个数字 a b c d e f g h i j k l m n o p q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 r s t u v w x y Z 17 18 19 20 21 22 23 24 25 凯撒密码(k=3)如下: C = Ek (m) = (m + k) (mod 26) m = Dk(C) = (C k) (mod 26) 19 公钥密码体制： RSA算法：加解密、数字签名 基于离散对数问题的公钥密码算法 背包密码体制 素性检测 20 第一章 整数的可除性 21 n整数的基本知识 （I）整数集合中可以做加法运算“+“，满足以下 性质： （i） 结合律 （ii）交换律 （iii）相消律 (iv) (v) 对任意的 22 n整数的基本知识 （II）整数集合中可以做乘法运算“”，满足以下 性质： （i） 结合律 （ii）交换律 （iii）相消律 (iv) (v) (vi) 分配律 23 n整数的基本知识 （III）整数集合中有大小关系“”，满足以下性质： （i） 对任意的 （ii）自反性 （iii）反对称性 (iv) 传递性 (v) 对任意的 24 1 整除的概念.带余数除法 25 举例： 注意：整除和除法的区别 26 27 28 29 30 31 32 33 证明思路 34 35 36 37 带余数除法的内涵 n它可以看作是整除的推广，也可以用带余除法 定理来定义整除性 n将一个未知的整数表示为小于除数的余数，将 整数进行分类，从而可将无限问题转化为有限 问题 n其他应用：辗转相除法、进制间转换算法 38 带余数除法的应用：整数分类 n整数分类的依据：根据带余数除法可以进一步 根据 r 的取值范围定义 39 40 41 42 43 44 (1864)10=11101001000 45 整数的计算机表示 n在计算机发明之前，数学家是用手或一些机械改备来进 行计算的.而采用这两种方法中的任何一种，都只能处理 不是很大的整数，例如大数分解和素性检验，都需要计 算100位甚至200位的整数. n计算机本质上是使用字节或二进制数来表示数的，对于 可以在机器算法中使用整数大小是有限的.这个上限被称 为字长，用w表示.字长通常是2的幂次. n为实现关于大于字长的整数的算法,必须把每个整数用多 个字来表示.为了存储整数nw,我们把n作基于w的表示 ，并对每个数位用计算机的一个字表示.例如，如果字长 为235,由于