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

1、初等数论,黎琳 2015.03.11,授课教师：黎琳 E-mail：， 办公地点：九教北310， 电话：51688637 课件： 思源教学平台 教务处课程平台,教材 闵嗣鹤，严士健，初等数论（第三版），高等教育出版社. 参考教材 1潘承洞，潘承彪，初等数论（第三版），北京大学出版社. 2罗森（KennethH.Rosen）,初等数论及其应用(Elementary Number Theory(6th Edition).机械工业出版社. 3科布茨，数论与密码学教程（第2版），世界图书出版社.,课程设置,整数的可除性 * 6学时 不定方程 2学时 同余 * 6学时 同余式 * 4学时 二次同余式与平

2、方剩余 * 6学时 原根与指标 * 4学时 连分数 2学时,考核方式,成绩评定主要包括平时成绩（含考勤、 作业、随堂测试）占50%，期末考试成绩占50%； 期末采取闭卷笔试,序言,数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即质数）分布 以及数论函数等内容，统称初等数论（elementary number theory）。 初等数论是数论中不求助于其他数学学科的帮助，只依靠初等的方法来研究整数性质的分支。 初等数论是信息安全专业的必修课，是密码学等课的基础,发展历史,初等数论的大部份内容早在古希腊欧几里德的几何原本（

3、公元前3世纪）中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。,欧几里得前330年 前275年，欧氏几何学的开创者 ，古希腊数学家，以其所著的 几何原本闻名于世,我国古代在数论方面亦有杰出之贡献，现在一般数论书中的“中国剩余定理”，正是我国古代孙子算经中的下卷第26题，我国称之为孙子定理。,约成书于四、五世纪，作者生平和编写年代都不清楚。现在传本的孙子算经共三卷。卷下第31题，可谓是后世“鸡兔同笼”题的始祖，后来传到日本，变成“鹤龟算”。,近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。,高斯17771855，德国数学

4、家、物理学家、天文学家、大地测量学家。 1801年，著有算术探究，开始了现代数论的新纪元。高斯还提出：“数学是科学之王，数论是数学之王”。,费马 法1601-1665，是数学史上 最伟大的业余数学家，提出了费马 大、小定理；在坐标几何，无穷小， 概率论等方面有巨大贡献。,哥德巴赫 1690-1764， 德国数学家；曾担任中学 教师，1725年到俄国， 被选为彼得堡科学院院士.,勒让德法17521833，在分 析学、数论、初等几何与天体 力学，取得了许多成果，是椭 圆积分理论奠基人之一。对数 论的主要贡献是二次互反律， 还是解析数论的先驱者之一.,雅可比德18041851，在偏 微分方程中，引进

5、了“雅可比 行列式。对行列式理论作了奠 基性的工作，在代数学、变分 法、复变函数论、分析力学 、 动力学及数学物理方面也有贡献,欧拉17071783，瑞士数学家， 自然科学家。是数学史上最多产 的数学家，每年写出八百多页 的论文，无穷小分析引论、 微分学原理、积分学原理 等都成为数学中的经典著作。,希尔伯特德18621943， 他领导的数学学派是19世纪 末20世纪初数学界的一面旗 帜，希尔伯特被称为“数学 界的无冕之王”。著数论 报告等,由于自20世纪以来引进了抽象数学和高等分析的 巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。 近年来初

6、等数论在计算机科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时也促进着数论的发展。,华罗庚19101985，是中国解析 数论、矩阵几何学、典型群、自 安函数论等多方面研究的创始人 和开拓者。以华氏命名的数学科 研成果很多。被列为芝加哥科学 技术博物馆中当今世界88位数学 伟人之一。,陈景润19331996，主要研究 解析数论，他研究哥德巴赫猜 想和其他数论问题的成就，至 今仍然在世界上遥遥领先。其 成果也被称之为陈氏定理。,王元193050年代至60年代初，首先在中国将筛法用于哥德巴赫猜想研究，并证明了命题3+4，1957年又证明2+3，这是中国学者首次在此研究领

7、域跃居世界领先地位.,潘承洞，在解析数论研究方面有突出贡献。主要成就涉及算术数列中的最小素数、哥德巴赫猜想研究，以及小区间上的素变数三角和估计等领域。,几个著名数论难题,初等数论是研究整数性质的一门学科，历史上遗留 下来没有解决的大多数数论难题其问题本身容易搞懂，容易引起人的兴趣，但是解决它们却非常困难。,其中，非常著名的问题有：哥德巴赫猜想 ；费尔马大 定理 ；孪生素数问题 ；完全数问题等。,1742年,由德国中学教师哥德巴赫在教学中首先发现的。1742年6月7日，哥德巴赫写信给当时的大数学家欧拉,正式提出了以下的猜想： 一个大于6的偶数可以表示为不同的两个质数之和。 陈景润在1966年证明

8、了“哥德巴赫猜想”的“一个大偶数可以表示为一个素数和一个不超过两个素数的乘积之和”所谓的1+2，是筛法的光辉顶点，至今仍是“哥德巴赫猜想”的最好结果。,1、哥德巴赫猜想：,2、费尔马大定理：,费马是十七世纪最卓越的数学家之一，他在数学 许多领域中都有极大的贡献，因为他的本行是专业的 律师，世人冠以“业余王子”之美称。在三百七十多 年前的某一天，费马正在阅读一本古希腊数学家戴奥 芬多斯的数学书时，突然心血来潮在书页的空白处， 写下一个看起来很简单的定理。,经过8年的努力，英国数学家 安德鲁怀尔斯 终于在1995年完成了该定理的证明。,在密码学中应用,古典密码体制：代换密码 定义代换如下: a b

9、 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 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 凯撒密码如下: C = Ek (m) = (m + k) mod (26) m = Dk(C) = (C k) mod (26),公钥密

10、码体制： RSA算法：加解密、数字签名 基于离散对数问题的公钥密码算法 背包密码体制 素性检测,第一章 整数的可除性,整数的基本知识 （I）整数集合中可以做加法运算“+“，满足以下 性质：,（i） 结合律 （ii）交换律 （iii）相消律 (iv) (v) 对任意的,整数的基本知识 （II）整数集合中可以做乘法运算“”，满足以下性质：,（i） 结合律 （ii）交换律 （iii）相消律 (iv) (v) (vi) 分配律,整数的基本知识 （III）整数集合中有大小关系“”，满足以下性质：,（i） 对任意的 （ii）自反性 （iii）反对称性 (iv) 传递性 (v) 对任意的,1 整除的概念.带余数除法,举例：,注意：整除和除法的区别,证明思路,带余