主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2014 ，USTC 计算数论 主讲人： 吕敏 Email: { lvmin05@ustc.edu.cn } Spring 2014 ，USTC

课程信息 课程名称：计算数论 授课时间：1-18周，二 (6, 7, 8)， 3A319教室 教材信息： 《算法数论》裴定一，祝跃飞编著，科学出版社 《A course in Number Theory and Cryptography 》(2nd Edition), Neal Koblitz, Springer. 《Number Theory for Computing 》(2nd Edition)，Song Y.Yan, Springer, 2002. 《A Friendly Introduction to Number Theory》(《数论概论》)，Joseph H. Silveman, 机械工业出版社。 《A Course in Computational Algebraic Number Theory》, Henri Cohen, Springer-Verlag. 2017/3/9

课程信息 授课形式 课堂讲解：课程作业：每章一次 考核形式 期末考试(闭卷)：70% 课堂作业+出勤+课堂纪律：30% 课程主页 http://staff.ustc.edu.cn/~lvmin05/jssl/ 联系方式 办公室：科研楼601 电 话：3603412（办） Email: lvmin05@ustc.edu.cn 2017/3/9

教学目标 数论是研究整数性质的一门很古老的数学分支。 计算数论是数论和算法复杂性理论的交叉学科，是由于计算机科学和密码学的需求而发展起来的新兴学科。 本课程将讨论计算数论的基本知识，主要包括以下内容： (1) 整数基本性质； (2) 同余 (3) 同余式 (4) Legendre和Jacobi符号 (5) 原根 (6) 素性测试和大数分解 (7) 指数计算和离散对数计算 (8) 其他计算问题。 掌握初等数论内容的基础上，理解各种计算数论的算法和复杂性分析，并能够独立地实现其中的部分算法。 2017/3/9

引言 内容提要： 课程学习背景 课程内容 2017/3/9

学习背景 计算数论不仅是数论理论研究的手段, 而且更重要的是推进了数论在计算机科学、信息安全和通信等领域的应用. 整数分解 和素性测定是计算数论的孪生中心课题, 数学王子高斯在他的天才著怍《数论探讨》一书中就称 其为“重要的有用的.”由于快速计算机的出现和普及和密码学(RSA 公钥密码系统) 等领域的需要, 促进了这个方向的发展, 近三十年来又成为国际数学界和计算机科学界的热点之一. 算法及其复杂度分析和计算机辅助研究数论著名问题，也是计算数论的主要内容. 计算数论的研究特色是既要研究理论, 又要在计算机上进行大量计算. “一个人接受科技教育的最大收获，是那些能够受用一生的通用智能工具”——George Forsythe, What to do till the computer scientist comes, 1968 “科技殿堂里陈列着两颗” 2017/3/9 6 6

数论发展简史 起源于东方，大约有3000年的历史。 我国最早的数学名著《周髀(易)算经》记载了西周人商高知道方程x2+y2=z2的解。 我国古代《孙子算经》（公元4－5世纪）中给出了解一次同余式组的算法，也叫孙子定理。 公元前三世纪，古希腊人Euclid在《几何原本》中证明了素数是无穷多的，特别重要的是给出了求两个正整数的最大公因子的算法；丢番图(Diophantus)（公元3世纪）在《算术》中列举了一次和二次方程的求解问题。 从十七世纪到十九世纪，Fermat、Euler、Legendre、Gauss等人的工作大大丰富和发展了数论…… 这些人的成果大致构成了现在数论的基本内容。

由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等 新分支。 近年来初等数论在计算机科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。

I. 整除理论(古希腊) 数论的研究在内容上是从数的可约性开始的, 整除性理论被称作是数论中最古老的内容也是初等数论的基础, 它是在带余数的除法的基础上建立起来的. 整除理论的中心内容是算术基本理论和最大公约数理论, 反映了近代数学中十分重要的思想, 概念和方法.

I. 整除理论(古希腊) (公元前三世纪) 欧几里德(Euclid)在《几何原本》中给出了最古老的算术基本定理: 任一合数都为某素数整除. 他还证明了素数的个数是无穷的, 并给出了求两个正整数的最大公因数的算法(即现在的Euclid算法). (公元100年) 尼可马修斯的《算术入门》是数学历史上第一部数论典籍, 书中介绍了著名的“厄拉多塞筛法”.

II.中国剩余定理 我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。

II.中国剩余定理 中国剩余定理也称“孙子定理”, 起源于《孙子算经》(约公元400年)中的一个著名的问题: 中国剩余定理也称“孙子定理”, 起源于《孙子算经》(约公元400年)中的一个著名的问题: “今有物未知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?” 该问题涉及到同余理论, 它是由我国最早研究并取得辉煌理论成就的数论课题.

解同余式组 秦九韶在《数书九章》第一章“大衍术”中给出了如何求一次同余式组的方法 “大衍求一术”. (失传达五百年, 由清朝黄宗宪等重新发现) 直到1801年, 高斯(德, Gauss)在《算术研究》才作出了与秦九韶相同的结果.

III. 二次互反律 高斯(德, Gauss)在《算术研究》中证明了二次互反律、原根存在的充要条件等重要结果. 对二次互反律和高次互反律的研究, 促进了代数数论和类域论的发展.

IV. 近代数论的发展 1. 费马与数论 (Fermat, 法国, 16011665) “费马小定理”(1640年): 若p是素数且a与p互素, 则 p︱(ap  a). “费马大定理” (1637年): 设整数n2, 则方程 xn + y n = zn 没有正整数解. 该问题直到1994年9月才由英国数学家怀尔斯(时年41岁)最终完成了证明过程. 17世纪费马(Fermat)提出的一系列猜想 18世纪世界数论中心: 法国, 代表人物: Fermat, Lagrange, Lengendre, Laplace, Euler(英国) 19世纪世界数论中心: 德国, 代表人物: Gauss, Dedekind, Dirichlet, Riemann, Hilbert 高斯的《算术研究》标志着数论成为独立的数学分支 15

2.高斯与数论(Gauss, 德国, 1777  1855) 1801年，高斯(时年24岁) 发表了《算术研究》，这标志着数论成为独立的数学分支.

V.哥德巴赫猜想 哥德巴赫 (Goldbach, 1690-1764), 德国人, 1742年6月7日写信给大数学家欧拉 (Euler), 提出一个猜想 ： 每一个大于2的偶数都可以表示为两个素数的和. (或每一个大于或等于6的偶数都可表示为两个奇素数的和) 同年6月30日欧拉回信表示他虽不能证明此猜想, 但他相信这是完全正确的.

哥德巴赫猜想 “皇冠上的明珠.” (高斯) 1966年, 陈景润证明了每一个充分大的偶数都能够表示为一个素数及不超过两个素数积之和. 该研究成果于1973年正式发表. (1+2) 英国数学家哈伯斯坦（Halberstam）将其结果收入《筛法》(Sieve Methods) 一书中, 并将其命名为“陈氏定理”. 大数学家高斯把数论问题比喻为数学中的皇冠，而又将“哥德巴赫猜想”则比喻为皇冠上的明珠！ 英国数学家哈伯斯坦在给陈景润的信中称赞说：“您移动了群山！” 18

哥德巴赫猜想论证历程 1920 挪威 布朗 9 + 9 1948 匈牙利 瑞尼 1 + c 1958 中国 王元 2 + 3 1920 挪威 布朗 9 + 9 1948 匈牙利 瑞尼 1 + c 1958 中国 王元 2 + 3 1962 中国 潘承洞 1 + 5 1963 中国 王元、潘承洞 1 + 4 1965 前苏联 维诺格拉朵夫 1 + 3 1966 中国 陈景润 1 + 2 每个大偶数都是9个素因子之积加上9个素因子之积。简记作命题〖9+9〗. 19

我国数论的发展史 古代数论成就 现代数论成就 勾股定理( x2 + y2 = z2的正整数解) 中国剩余定理 (孙子定理) 祖冲之的疏率和密率(用有理数22/7和355/113逼近圆周率) 现代数论成就 以陈景润关于歌德巴赫问题的工作为代表

数论的分类 由于研究数论的方法不同，数论包括: 初等数论，代数数论，解析数论， 乘法数论，超越数论，组合数论， 计算数论，堆垒数论， 数的几何及模形式理论等等。 我国数学家陈景润在尝试解决“哥德巴赫猜想”问题中使用的就是解析数论的方法。代数数论研究代数数域上的整除,理想分解等理论. 21

初等数论内容 整除关系(“|”) 同余关系(“”) 连分数 素数和整数的唯一分解定理 中国剩余定理, 同余式的解法 二次剩余, 二次互反律 原根 数论函数 连分数

课程内容 计算数论: 分为初等数论，计算/算法数论，数论在计算和密码学上的应用。 初等数论：指使用不超过高中程度的初等代数处理的数论问题，以整数的整除性为中心，最主要的工具包括整数的整除性与同余，内容包括整除理论，数论函数，素数分布，同余理论，二次互反律，连分数等； 计算/算法数论：借助计算机的算法帮助解决数论问题，例如素性测试算法，整数分解算法，离散对数算法，量子数论算法，其它数论算法； 应用：计算机系统设计（散列，随机数生成等）和密码学与信息安全（DES，RSA等）。

谢谢！ Q & A 2017/3/9