数论密码

数论密码

数论密码，顾名思义，就是基于数论的密码。密码是相对于明码而言的。这是一个矛盾的两个方面。所谓明码（plaintext），就是人们可以直接识别或使用的代码（也就是人们通常所说的信息，如文字、声像等）；所谓密码（ciphertext），就是将明码经过了一定处理，变换成一种外人（与此无关的人员）无法直接识别或使用的信息。

比如在军事上，上级首脑机关向部下发布军令时，就往往需要将军令的原文（明码）变换成密码之后再发布（比如通过无线电台或计算机网络等向外发布）。这样，即使敌方能够截获到这些密码，也无法直接辨别出这些密码的原意。当然，对于自己的部下而言，由于他们事先已经拥有解开这些密码的钥匙，所以能够正确地将密码再变换回明码，从而可以执行军令。

密码学就是一门研究信息的加密（encryption）与解密（decryption）技术（统称为cryptography），以及密码破译（cryptanalysis）技术的学问。密码学有两个显著特点：一是历史悠久（事实上，密码学的历史几乎与人类文明史一样长），二是数学性强（几乎所有的密码体制都程度不同地使用了数学的方法，尤其是代数、几何与数论的方法）。本文着重介绍基于数论的密码方法。

数论：从纯粹走向应用

数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯就曾说过，数学是科学的皇后，数论是数学的皇后。数论的一个主要任务，就是研究整数（尤其是正整数）的性质（包括代数方程的整数解）。由于在研究这些整数的过程中，人们往往要用到别的数学分支的知识与技巧，这样就诞生出了解析数论、代数数论、组合数论、概率数论、几何数论甚至计算数论等分支学科。

由于整数的性质复杂深刻，难以琢磨，因此数论长期以来一直被认为是一门优美漂亮、纯之又纯的数学学科。美国芝加哥大学著名数学家迪克森（L.E.Dickson）就曾说过：感谢神使得数论没有被任何应用所玷污。20世纪世界级数学大师、剑桥大学的哈代也曾说过：数论是一门与现实、与战争无缘的纯数学学科。哈代本人也则因主要从事数论的研究而被尊称为“纯之又纯的纯粹数学家”。

当然，上述两位大数学家所说的并不完全符合今天的现实。事实上，在计算机科学与电子技术深入发展的今天，数论已经不仅仅是一门纯数学学科，同时也是一门应用性极强的数学学科，比如在今天，数论已经在诸如物理、化学、生物、声学、电子、通讯，尤其是在密码学中有着广泛而深入的应用。

大家知道，密码设计长期以来一直是困扰军方的一个问题。要保证军方的密码不被敌方破译，不是件容易的事情。比如在第二次世界大战期间，德军设计了一种性能优良的编制密码的机器，称之为爱尼格玛（Enigma）机器。德军指挥机关向其部队发布的军令都是通过爱尼格玛机器加密之后再往下发布的。当时英军就想到，要打败德军，就必须要破译德军的密码，掌握德军的军事动向（即所谓的知彼知己）。因此，英军迅速在伦敦北边不到一百公里处征集了一块空旷的土地（该地名为布莱克利公园，后也成了该秘密机构的名字），并在那里集结起一大批杰出的数学家、语言学家和象棋大师等，包括现代计算机科学的开山鼻祖图灵和后来在爱丁堡大学创办世界上第一个人工智能系的米基（D.Michie）。他们专门负责截获、破译爱尼格玛密码。由于这个组的努力，特别是图灵出色的工作，他们掌握了破译该密码的一整套方法，从而了解德军的军事动向，掌握了战争的主动权，为英美联军击败德军作出了突出的贡献。有人估算，如果没有图灵等人的贡献，第二次世界大战至少还要再打十年。

DHM 的提出

目前，由于商用计算机网络的广泛应用，尤其是电子商务的普及与深入，密码设计在民间也大有用武之地。传统的密码体制，称之为“密钥密码体制”，在加密、解密的过程中都采用同一个钥，简称为“密钥”(secret key)。所谓同一个钥，就是说知道了其中的一个钥，另一个钥就可以很容易地计算出来。具体到军用通讯，就是军事指挥机关要事先用密钥把军令加密，之后再下达到部队，与此同时（甚至是事先）还要将密钥也下达到部队，否则其部下解不开其军令。显然，密钥的管理与保护是个问题。一般而言，密钥比密码本身还重要，因为一旦敌方掌握了密钥，那么所有用此密钥加密的密码就成了人所皆知的明码。因此，在军事与外交等部门，都是不惜代价而派专人专管专送密钥。显然，这在电子商务方面是行不通的，因为代价太高。

1976年，美国斯坦福大学教授赫尔曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，以及博士生默克勒(R.C.Merkle)（简称为DHM）首先创立并发表了所谓的“公钥密码体制”（public key cryptography），即加密、解密用两个不同的钥，加密用公钥（public key），即可以公开，不必保密，任何人都可以用；解密用私钥（private key），此钥必须严加管理，不能泄漏。更为称绝的是，他们还发明了所谓的数字签名（digital signatures）技术，即用私钥签名，再用公钥验证。

在一般参考文献中，都认为公钥密码体制是迪菲和赫尔曼发明的[1]，可鲜为人知的是，默克勒甚至在他俩之前的1975年就提出了类似的思想，尽管其文章是于1978年发表的[2]，但投稿比较早。因此，公钥密码体制的创始人应该是DHM三人，这种观点目前已得到了国际上的认同，尤其得到了赫尔曼教授本人的认定。当然，英国军用情报中心也曾宣称他们早在1970年就发明了公钥密码体制，但经仔细分析其资料并与中心有关人员讨论后发现，他们只是提及了公钥密码体制的某种特殊形式。更为重要的是，DHM的公钥密码体制还包含数字签名，而情报中心的资料则是只字未提。注意，美国国家安全局也有过类似的宣称，不过这都是不可信的（至少不可全信）。如要详细了解公钥密码体制的发展史，读者可参考笔者的一本由赫尔曼教授作序的英文专著[3]。

当然，DHM只是提出了一种关于公钥密码体制与数字签名的思想，而没有真正实现。不过，他们确实是实现了一种体现公钥密码体制思想、基于离散对数问题的、在不安全的通道上进行密钥形成与交换的新技术。这里必须先介绍一下什么叫离散对数。

所谓离散对数，就是给定正整数x，y，n，求出正整数k（如果存在的话），使y≡xk(mod n)。就目前而言，人们还没有找到计算离散对数的快速算法（所谓快速算法，是指其计算复杂性在多项式范围内的算法，即O(logn)k，其中k为常数）。虽然有快速计算离散对数的量子算法，其计算复杂性为O(logn)2+?着，但现在并没有量子计算机（实用的量子计算机也许根本就建造不出来）。

现在，说明一下DHM的运作过程（假定A和B两个人要在一个不安全通道如因特网上形成密钥以备日后加密解密所用）。

首先，A、B两人要共同公开约定一个素数q和有限域Fq中的一个生成元g；

A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并将g a(modq)传送给B；

B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并将gb(modq)传送给A；

此时A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由于(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一个公共的密钥g ab(modq)，日后便可以此钥来进行传统的加密解密计算，从而达到在不安全的通道上进行保密通讯的目的。

显然，敌方可以截获到g，q，g a(modq)，g b(modq)。因此，如果敌方有快速的求解离散对数的算法，就能从已截获的上述信息中迅速求出a或b，从而算出g ab(modq)。遗憾的是，目前世界上根本就没有快速的求解离散对数的算法，因此当所选的有限域Fq很大时，a或b就很难算出。值得注意的是，DHM密钥交换体制实际上是一座沟通密钥密码体制与公钥密码体制的桥梁，即用公钥密码体制的思想形成密钥（虽然公钥密码体制计算速度慢，但密钥的长度一般都很短，所以没有关系），再用密钥进行传统的密钥密码体制的加密与解密运算（密钥密码体制的运算速度一般都很快，所以适合于对容量大的信息进行加密解密计算）。在这里，这两种密码体制交叉使用，扬长避短，充分发挥了各自的优越性。

下面给出一个关于具体计算离散对数的实例。

A和B先约定公共的q=2739·（7149-1）/6+1和g=7。

A选随机数a，并计算7a(modq)，且将其送给B（注：a不能向外泄漏）；

B收到

7a=12740218011997394682426924433432284974938204258693162165455773529032291467909599868186097 8813046595166455458144280588076766033781；

B选随机数b，并计算7b(modq)，且将其送给A（注：b不能向外泄漏）；

A收到

7b=18016228528745312444782834836799895015967046695346697313025121734059953772058475958176910 625380692101651848662362137934026803049。

此时A和B都能计算出密钥7ab(modq)，但别人不太容易算出，因为别人不知道a和b。有兴趣的读者不妨将此作为一个练习，试着计算出7ab(modq)的值。

RSA 体制

1978年，仅在DHM发明公钥密码体制的两年后，美国MIT的三位科学家里维斯特(R.L.Rivest)，沙米尔(A.Shamir)和阿德尔曼(L.Adleman)（简称RSA）就提出了一种基于整数分解困难性的实用的公钥密码体制[4]，现通称为RSA体制。

所谓整数分解，可以认为是给定大于1的正整数n，求出正整数a和b，使之满足n=ab，其中a和b可以是素数，也可以是合数。根据算术基本定理，只要能够快速求出a，b，那么就能递归地快速求出n的素数分解式n=p1 p2…pk，其中?琢i为正整数，pi为素数，i=1,2,…,k。现在的问题是，人们根本就没有满意的快速整数分解算法，目前世界上最快的整数分解算法是波拉德（J.Pollard）首创的数域筛法（NFS）。

波拉德是英国的数学奇才，曾在剑桥大学念数学本科，但因毕业考试不及格而肄业，后来因在计算数论中作出突出贡献而被剑桥免试授予博士学位。无独有偶，剑桥出身的另一位著名数学家罗斯（K.Ruth）也是因为在念本科时考试成绩不好而勉强毕业，后来却因在数论研究中取得杰出成就而获得菲尔兹奖，剑桥则因此而授予其名誉博士学位。

数域筛法的计算复杂性为O(exp(c(logn)1/3(loglogn)2/3 ))，其中c为一实常数，1

现在，具体地谈一谈RSA的思想。

加密C≡Me(modn)；

解密M≡Cd(modn)；

其中M为明码，C为密码，(n，e)为公钥（加密钥），d为私钥（解密钥），并且要满足：n=pq，其中p和q为两个至少100位的素数；ed≡1(mod?准(n))，其中?准为欧拉函数，其计算公式为：如果n的标准分解为

n=p ，

则准(n)=n(1-) 。

(e，n)要公开出去，以便别人能用来对信息进行加密，但p和q（当然包括d）必须保护好，不能泄漏。RSA体制之所以能工作，是因为

Cd≡(Me)d≡Med≡M1+k?准(n)

≡M(M?准(n))k≡M(modn)；

对于合法用户而言，因为他知道n=pq，故计算出?准(n)=(p-1)(q-1)，从而算出d≡1/e(mod?准(n))，这样他就可以对信息进行解密计算。上述计算的关键是欧拉函数。

显然，对于非法用户（即敌方）而言，要算出d，他必须先算出?准(n)；而要算出?准(n)，他必须先分解n。如前所述，整数分解是个很困难的问题，事实上，在现有的计算条件下，当n为一个一般的大于200位的整数时，要分解n往往需要数亿年的时间。可以想像，任何一项秘密，过了数亿年的时间，其秘密性已不复存在了。因此，用RSA方法来加密信息还是很安全的（当然在具体实现上，其加密解密过程中的参数的选择还是很有讲究的）。

椭圆曲线密码体制简介

目前，国际上公认的比较安全实用的公钥密码体制是所谓的椭圆曲线密码体制。其思想是在基于有限域的椭圆曲线上对信息进行加密解密。由于有限域上椭圆曲线的离散对数实际上是一般有限域上的离散对数在椭圆曲线上的一种类比物，因此它至少在实用上比一般有限域上的离散对数的计算要困难些，因此其安全性也要强一些，当然目前人们还不能证明这一点。

椭圆曲线上的离散对数，可以认为是：给定有限域Fq（q=pr为素数幂）上的一条椭圆曲线y2=x3+ax+b，并给定这条曲线上的两点P和Q，求出正整数k（如果存在的话），使之满足Q=kP，目前关于椭圆曲线离散对数问题还没有找到一种甚至是子指数（subexponential）复杂性的算法（对于整数分解与离散对数，已有子指数复杂性的算法）。西尔弗曼（J.H.Silverman）等人于2000年提出了一种称之为Xedni Calculus 的计算椭圆曲线离散对数的算法[5]，但该法过于复杂，并用了很多未被证明的数学结果，因此该法一是没

有实用价值，二是连个复杂性的度量都提不出来。故而寻求快速实用的计算椭圆曲线离散对数的算法（哪怕是子指数复杂性的算法）是当前计算数论中的一项刻不容缓的艰巨任务。

下面介绍基于椭圆曲线的ElGamal公钥密码体制（其他的很多公钥密码体制都可以很容易地推广到椭圆曲线上去）。

A和B两人要事先在公开的通道上选定有限域Fq（其中q=pr，p为素数）上的一条椭圆曲线E，以及随机点P∈E（该点要能生成一个很大的子群，这个子群最好和椭圆曲线E本身所构成的群一样大或比较接近）。

A选定一个随机数a∈{1，2，…，q-1}（a可以认为是A之私钥），并计算出aP（aP可以认为是A之公钥），且将其传输给B；

B选定一个随机数b∈{1，2，…，q-1}（b可以认为是B之私钥），并计算出bP（bP可以认为是B之公钥），且将其传输给A；

现假定A要给B传输信息M（明码）。首先A要选定一个随机数k，并利用B的公钥bP计算出密码C=（kP，M+k(bP )），且将其传输给B。

为了能够将C变换回M，B需要对C进行解密计算，但由于B有b，所以他可以很容易地计算出

M=M+k(bP )-b(kP )。

显然，敌方如能计算椭圆曲线上的离散对数，他就能从公开的信息P和bP中确定出b，从而破译C。遗憾的是，求解椭圆曲线上的离散对数比求解一般有限域上的离散对数更困难（前面讲到，求解一般有限域上的离散对数已经是一件很困难的事情了），所以当所选的有限域Fq很大、所选的椭圆曲线以及这条曲线上的点P又很合适时，a或b是很难算出的，因此基于椭圆曲线离散对数的密码体制也就要更安全些（至少比基于整数分解或一般有限域上的离散对数的密码体制要更安全些）。另外，椭圆曲线密码体制与其他公钥密码体制相比，在钥的长度相同的情况下，它的安全性要更高些。正是基于上述这些原因，目前人们才会对椭圆曲线密码体制更感兴趣。

上面介绍的三种具有代表性的现代公钥密码体制，就是基于三种各不相同的数论难题的（即整数分解、离散对数以及椭圆曲线上的离散对数）；目前世界上几乎所有具有实用价值的公钥密码体制，基本上都是基于这三种数论难题的。也就是说，事实上是将密码的加密、解密、破译等问题与数论难题的求解联系在一块了。密码难破译是因为数论问题难解。因此，在这里，不仅数论本身的理论与方法有实用价值，就是数论里的难题也为现实生活提供了应用的场所。也许正因为如此，国际数学大师陈省身先生才会主张把数论作为一门应用数学学科[6]。值得特别一提的是，数论密码是目前密码学中的主流学科，限于篇幅，这里不再对其做深入的介绍[3,7]。

（本文作者为南开大学信息技术科学学院特聘教授。）

不定方程

第六节 不定方程 所谓不定方程，是指未知数的个数多于方程个数，且未知数受到某些（如要求是有理 数、整数或正整数等等）的方程或方程组。不定方程也称为丢番图方程，是数论的重要分支学科，也是历史上最活跃的数学领域之一。不定方程的内容十分丰富，与代数数论、几何数论、集合数论等等都有较为密切的联系。不定方程的重要性在数学竞赛中也得到了充分的体现，每年世界各地的数学竞赛吉，不定方程都占有一席之地；另外它也是培养学生思维能力的好材料，数学竞赛中的不定方程问题，不仅要求学生对初等数论的一般理论、方法有一定的了解，而且更需要讲究思想、方法与技巧，创造性的解决问题。在本节我们来看一看不定方程的基础性的题目。 基础知识 1．不定方程问题的常见类型： （1）求不定方程的解； （2）判定不定方程是否有解； （3）判定不定方程的解的个数（有限个还是无限个）。 2．解不定方程问题常用的解法： （1）代数恒等变形：如因式分解、配方、换元等； （2）不等式估算法：利用不等式等方法，确定出方程中某些变量的范围，进而求解； （3）同余法：对等式两边取特殊的模（如奇偶分析），缩小变量的范围或性质，得出不定方程的整数解或判定其无解； （4）构造法：构造出符合要求的特解，或构造一个求解的递推式，证明方程有无穷多解； （5）无穷递推法。 以下给出几个关于特殊方程的求解定理： （一）二元一次不定方程（组） 定义1.形如c by ax =+(,,,,Z c b a ∈b a ,不同时为零)的方程称为二元一次不定方程。 定理1.方程c by ax =+有解的充要是c b a |),(； 定理2.若1),(=b a ，且00,y x 为c by ax =+的一个解，则方程的一切解都可以表示成 ??? ????-=+=t b a a y y t b a b x x ),(),(00t (为任意整数)。 定理3.n 元一次不定方程c x a x a x a n n =+++ 2211，(N c a a a n ∈,,,,21 )有解的充要条件是c a a a n |),,,(21 . 方法与技巧： 1．解二元一次不定方程通常先判定方程有无解。若有解，可先求c by ax =+一个特解，从而写出通解。当不定方程系数不大时，有时可以通过观察法求得其解，即引入变量，逐渐减

小学奥数 不定方程与不定方程组.教师版

不定方程与不定方程组 教学目标 1.利用整除及奇偶性解不定方程 2.不定方程的试值技巧 3.学会解不定方程的经典例题 知识精讲 一、知识点说明 历史概述 不定方程是数论中最古老的分支之一．古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程．中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志着中国对不定方程理论有了系统研究．宋代数学家秦九韶的大衍求一术将不定方程与同余理论联系起来． 考点说明 在各类竞赛考试中，不定方程经常以应用题的形式出现，除此以外，不定方程还经常作为解题的重要方法贯穿在行程问题、数论问题等压轴大题之中．在以后初高中数学的进一步学习中，不定方程也同样有着重要的地位，所以本讲的着重目的是让学生学会利用不定方程这个工具，并能够在以后的学习中使用这个工具解题。 二、不定方程基本定义 1、定义：不定方程（组）是指未知数的个数多于方程个数的方程（组）。 2、不定方程的解：使不定方程等号两端相等的未知数的值叫不定方程的解，不定方程的解不唯一。

3、研究不定方程要解决三个问题：①判断何时有解；②有解时确定解的个数； ③求出所有的解 三、不定方程的试值技巧 1、奇偶性 2、整除的特点（能被2、 3、5等数字整除的特性） 3、余数性质的应用（和、差、积的性质及同余的性质） 模块一、利用整除性质解不定方程 【例 1】求方程 2x－3y＝8的整数解 【考点】不定方程【难度】2星【题型】解答 【解析】方法一：由原方程，易得 2x＝8＋3y，x＝4＋3 2 y，因此，对y的任意一个值，都有一个x与之对应，并且，此时x与y的值必定满足原方 程，故这样的x与y是原方程的一组解，即原方程的解可表为： 3 4 2 x k y k ? =+ ? ? ?= ? ，其中k为任意数．说明由y取值的任意性，可知上述不定方程有无 穷多组解． 方法二：根据奇偶性知道2x是偶数，8为偶数，所以若想2x－3y＝8 成立，y必为偶数， 当y＝0，x＝4；当y＝2，x＝7；当y＝4，x＝10……，本题有无穷多个解。 【答案】无穷多个解 【巩固】求方程2x＋6y＝9的整数解 【考点】不定方程【难度】2星【题型】解答 【解析】因为2x＋6y＝2(x＋3y)，所以，不论x和y取何整数，都有2|2x＋6y，但29，因此，不论x和y取什么整数，2x＋6y都不可能等于9，即 原方程无整数解． 说明：此题告诉我们并非所有的二元一次方程都有整数解。 【答案】无整数解 【例 2】求方程4x＋10y＝34的正整数解 【考点】不定方程【难度】2星【题型】解答 例题精讲

浅谈数论在密码学上的应用

硕士研究生《应用密码学》课程论文浅谈数论在密码学上的应用 指导教师：王玉柱 专业：计算机应用技术 学号：1010706 姓名：杨玖宏 日期：2011年6月30日

浅谈数论在密码学上的应用 摘要：众所周知．数论是数学中最古老、最纯粹、最优美的一个学科．不过鲜为人知的还是，数论同时也是一门应用性极强的应用数学学科．著名国际数学大师陈省身教授早在1992年精辟地指出：“数学中我愿意把数论看作应用数学。”我想数学中有两个很重要的数学部门，一个是数论，另一个是理论物理。在本文中我将先扼要介绍下数论中的一些基本概念、几个主要难题，紧接着我们要介绍数论在现代密码学与计算机科学中的应用。 关键词：数论；计算数论；密码学； 1 引言 随着现代计算机网络通信的广泛使用，传统密码受到很大挑战，它们已经不能完全适应网络环境下使用密码的需求。于是在上世纪七十年代，提出了公钥密码的概念，并且利用数论方法设计了第一个公钥密码体制（RSA公钥密码），经过二十多年的研究，RSA已得到了广泛的应用。在RSA密码体制中，使用了一个大整数（目前通常取这个数有1024比特长），它是两个素数的乘积，这个大整数是公开的，而它的两个素因子是保密的。如果有人能将这个大整数分解因子而得到它的两个素因子，就能破译这个密码体制，所以RSA的安全性是建立在大整数因子分解问题的基础之上的。这是一个经典的数论问题，RSA的提出大大推动了大整数因子分解算法的研究。在上世纪八十年代，人们又提出了椭圆曲线公钥密码，它应用了更深刻的数论知识，它的安全性也得到了密码界的公认，现在也正逐步推向应用。公钥密码的出现，使数学在密码研究中发挥了更加核心的作用。 2 数论概述 数论，顾名思义，就是关于数的理论，数学，顾名思义，就是关于数的学问．高斯曾说过一句名言：“数学是科学的女王，而数论是数学的女王”。基础数论作为一门古老的数学学科，在很常时间内都属于一种纯数学，随着现代科技的发展，数论在整个科学中的应用非常重要[1]。数论中许多基本内容，如同余理论、中国剩余定理（CRT）、高次剩余理论等，在现代密码体制、密钥分配与管理、数字签名、身份认证等方面有重要的应用。 1 数论概述 1.1 整除理论 1)整除：设 a 和 b 是两个整数，且 b≠0，如果存在一个整数 q，使等式a=bq 成立，那么我们称 a 能被 b 整除或 b 整除 a，记作 b— a，其性质有： (1) 若 b | a，a ≠0，则 | b | ? | a | ； (2) 若 b | a，a | b，a ≠0，则 a=b 或 b=a； (3) 若 c | b，b | a, 则 c | a；（c≠0） (4) 若 b | a，则 cb | ca（c≠0）； (5) 若 c | a，c | b,则 c | ma+nb，m，n∈Z（c≠0）。 2) 整除的基本定理：对于任意整数 a，b(b≠0)存在唯一的一对整数 q，r，

丢番图方程

丢番图方程 丢番图方程又名不定方程、整系数多项式方程，是变量仅容许是整数的多项式等式；即形式如，其中所有的a j、b j和c 均是整数，若其中能找到一组整数解m1,m2...m n者则称之有整数解。 丢番图问题有数条等式，其数目比未知数的数目少；丢番图问题要求找出对所有等式都成立的整数组合。对丢番图问题的数学研究称为丢番图分析。 3世纪希腊数学家亚历山大城的丢番图曾对这些方程进行研究。 丢番图方程的例子有贝祖等式、勾股定理的整数解、四平方和定理和费马最后定理等。 一次不定方程 一次不定方程是形式如a1x1 + a2x2 + ... + a n x n = c的方程，一次不定方程有整数解的充要条件为： (a1,...,a n)须是c的因子，其中(a1,...,a n)表示a1,...,a n 的最大公因子。 若有二元一次不定方程ax+ by= c，且(a,b) | c，则其必有一组整数解x1,y1，并且还有以下关系式： ?x = x1 + [b / (a,b)]t ?y = y1? [a / (a,b)]t t为任意整数，故此一次不定方程有无限多解。请参见贝祖等式。 丢番图分析 经典问题 ?有解答吗？ ?除了一些显然易见的解答外，还有哪些解答？ ?解答的数目是有限还是无限？ ?理论上，所有解答是否都能找到？ ?实际上能否计算出所有解答？ 希尔伯特第十问题

1900年，希尔伯特提出丢番图问题的可解答性为他的23个问题中的第10题。1970年，一个数理逻辑的结果马蒂雅谢维奇定理（Matiyasevich's theorem）说明：一般来说，丢番图问题都是不可解的。更精确的说法是，不可能存在一个算法能够判定任何丢番图方程式否有解，甚至，在任何兼容于 Peano 算数的系统当中，都能具体构造出一个丢番图方程，使得没有任何办法可以判断它是否有解。 现代研究 ?丢番图集是递归可枚举集。 ?常用的方法有无穷递降法和哈赛原理。 ?丢番图逼近研究了变量为整数，但系数可为无理数的不等式。

丢番图方程整数解方法

求不定方程整数解的常用方法 不定方程是指未知数的个数多于方程的个数，且未知数受到某些限制（如要求是有理数，整数或正整数等)的方程或方程组。不定方程也称丢番图方程，是数论的重要分支学科，也是数学上最活跃的数学领域之一。我国对不定方程的研究已延续了数千年，“百钱百鸡问题”等一直流传至今，“物不知其数”的解法被称为中国剩余定理。一般常用的求不定方程整数解的方法包括： (1)分离整数法 此法主要是通过解未知数的系数中绝对值较小的未知数，将其结果中整数部分分离出来，则剩下部分仍为整数，则令其为一个新的整数变量，以此类推，直到能直接观察出特解的不定方程为止，再追根溯源，求出原方程的特解. 例1 求不定方程02 5=-++y x x 的整数解 解 已知方程可化为 2 31232223225++=++++=+++=++=x x x x x x x x y 因为y 是整数，所以2 3+x 也是整数. 由此 x+2=1，-1，3，-3，即 x=-1，-3，1，-5， 相应的.0,2,0,4=y 所以方程的整数解为(-1,4),(-3,0),(1,2),(-5,0). (2)辗转相除法 此法主要借助辗转相除式逆推求特解，具体步骤如下： 第一步，化简方程，尽量化简为简洁形式(便于利用同余、奇偶分析的形式); 第二步，缩小未知数的范围，就是利用限定条件将未知数限定在某一范围内，便于下一步讨论; 第三步，用辗转相除法解不定方程. 例2 求不定方程2510737=+y x 的整数解. 解 因为251)107,37(=,所以原方程有整数解. 用辗转相除法求特解: 18433,413337,33237107+?=+?=+?= 从最后一个式子向上逆推得到 19107)26(37=?+-?

不定方程的解法与应用

摘要 不定方程是初等数论的一个重要内容，在相关学科和实际生活中也有着广泛的应用．本文首先归纳了整数分离法、系数逐渐减小法和辗转相除法等几种常用的二元一次不定方程的解法；其次进一步讨论了求n元一次不定方程和二次不定方程整数解的方法；最后论述了不定方程在中学数学竞赛题、公务员行测试题和其他学科中的应用，并举例说明． 关键词：不定方程；二元一次不定方程；数学竞赛；公务员试题

Abstract The integral solutions of indeterminate equation solving method is an important content of elementary number theory, has been widely used in related disciplines and in real life. This paper summarizes the integer separation method, coefficient decreases and the Euclidean algorithm and several commonly used two element indefinite equation solution, secondly is further discussed. For n linear indeterminate equation and the method of two time indefinite equation integer solution, and finally discusses the indeterminate equation applied in secondary school mathematics, civil servants for test and other subjects, and illustrated with examples. Key words: i ndeterminate equation; two element indefinite equation; Mathematics contest; civil service examination.

丢番图方程整数解方法

求不定方程整数解的常用方法 不定方程是指未知数的个数多于方程的个数，且未知数受到某些限制(如要求是有理数，整数或正整数等) 的方程或方程组。不定方程也称丢番图方程，是数论的重要分支学科，也是数学上最活跃的数学领域之一。我国对不定方程的研究已延续了数千年，“百钱百鸡问题”等一直流传至今，“物不知其数”的解法被称为中国剩余定理。一般常用的求不定方程整数解的方法包括： (1)分离整数法此法主要是通过解未知数的系数中绝对值较小的未知数，将其结果中整数部分分离出来，则剩下部分仍为整数，则令其为一个新的整数变量，以此类推，直到能直接观察出特解的不定方程为止，再追根溯源，求出原方程的特解. 例 1 求不定方程x 5 y 0 的整数解 x2 解已知方程可化为 x 5 x 2 3 x 2 3 3 y1 x 2 x 2 x 2 x 2 x 2 因为y 是整数，所以3也是整数. x2 由此 x+2=1 ，-1，3，-3 ，即 x=-1 ，-3，1，-5 ， 相应的y 4,0,2,0. 所以方程的整数解为(-1,4),(-3,0),(1,2),(-5,0). (2)辗转相除法此法主要借助辗转相除式逆推求特解，具体步骤如下：第一步，化简方程，尽量化简为简洁形式( 便于利用同余、奇偶分析的形式); 第二步，缩小未知数的范围，就是利用限定条件将未知数限定在某一范围内，便于下一步讨论; 第三步，用辗转相除法解不定方程. 例 2 求不定方程37x 107y 25的整数解. 解因为(37,107) 125, 所以原方程有整数解. 用辗转相除法求特解: 107 37 2 33,37 33 1 4,33 4 8 1 从最后一个式子向上逆推得到 37 ( 26) 107 9 1

数论应用

适用专业与学时分配：教学内容与时间安排表 3．课程教学目的与要求： 本课程的教学目的要求是使学生掌握初等数论的基本理论和方法，具备进行数论理论研究的能力，以及将数论应用于其他学科，尤其是信息科学研究的能力。 4．本门课程与其他课程关系： 《初等数论》是本专业的专业必修课，是基础课程，为《数论及其应用》、《密码学基础》、《现代密码学》、《应用密码学》和《密码分析》等课程的前期准备课程。 5．推荐教材及参考书： 推荐教材： 《初等数论》于秀源瞿维建山东教育出版社。 参考书： 《初等数论》潘承洞潘承彪北京大学出版社； 《数论导引》华罗庚科学出版社； 《初等数论》闵嗣鹤严士健高等教育出版社； 《AN INTRODUCTION TO THE THEORY OF NUMBERS》H.Davenport； 《Elementary Methods in Number Theory》 Melvyn B.Nathanson Springer-Verlag； 《ELEMENTARY NUMBER THEORY and its applications》Kenneth H.Rosen 机械 工业出版社。 6．课程教学方法与手段： 整除理论以及简单的不定方程求解问题是初等数论中最基础，也是比较重要的一部分，但这部分内容，学生较为熟悉，因此出个别地方外，学生可以自学。 课堂教学主要是通过大量例题的讲解，使学生加深对定义和定理的理解，学会解题和制设新题的基本技巧，注意对逻辑推理的严密性，数学语言的规范性以及文字叙述准确性的基础训练。同余和同余方程的基础理论、二次剩余、整数的平方

和表示，以及原根和连分数的基础理论，是初等数论中的重要组成部分，是学生深入学习数论的基础，也是将来从事数论理论研究的基础。对这一部分的教学，要着重使学生充分理解概念、定义的内涵、掌握基本方法、了解重要结论以及应用这些知识去解决问题，因此，课堂教学以教师讲解为主，辅以学生的自学。对数论的应用，以及超越数和代数数的基本知识，除个别内容外，自学较为困难，因此因以课堂教学为主。 7．课程考试方法与要求： （1）本课程每学期末应进行考试，成绩占总成绩的７０％左右，期中考核一般占总成绩的２０％左右，平时成绩占总成绩的１０％。 （2）期末考试一律准备Ａ、Ｂ卷（含标准答案和评分标准），平行班考试卷统一。 （3）本课程应建立试卷库，实行考教分离。 8．实践教学内容安排： 无 二、教学内容纲要 第一章 整除理论（14学时） 1．主要内容 第一节 数的整除性 2学时 第二节 带余数除法 2学时 第三节 最大公约数 2学时 第四节 辗转相除法 2学时 第五节 算术基本定理 2学时 第六节 函数 ][x 和}{x 2学时 第七节 素数 2学时 2．基本要求 整除理论是初等数论中最基础，也是比较重要的一部分，要求学生掌握。但这部分内容，学生较为熟悉，因此出个别地方外，学生可以自学。课堂教学主要是通过大量例题的讲解，使学生加深对定义和定理的理解，学会解题和制设新题的基本技巧，注意对逻辑推理的严密性，数学语言的规范性以及文字叙述准确性的基础训练。 第二章 同余（7学时） 1．主要内容 第一节 同余的基本性质 1.5学时 第二节 完全剩余系 1.5学时 第三节 简化剩余系 1.5学时 第四节 Euler 定理 1.5学时

小学奥数-不定方程(教师版)

不定方程 在列方程组解答应用题时，有两个未知数，就需要有两个方程。有三个未知数，就需要有三个方程。当未知数的个数多于方程的个数时，这样的方程称为不定方程，为纪念古希腊数学家丢番图，不定方程也称为丢番图方程。不定方程在小学奥数乃至以后初高中数学的进一步学习中，有着举足轻重的地位。而在小学阶段打下扎实的基础，无疑很重要。 不定方程是由于联立方程的条件“不足”而出现的，从一般情况来说，有无数多个解。不过，我们要注意到它的“预定义”条件，比如未知项是自然数，比如在数位上的数码不仅是自然数，而且是一位数等等，甚至题干中直接给出限制条件，这样，就使得不定方程的解“定”下来了。这种情况也不排除它的取值不止一种。 不定方程解的情况比较复杂，有时无法得出方程的解，有时又会出现多个解。如果考虑到题中以一定条件所限制的范围，会有可能求出唯一的解或几种可能的解（而这类题的限制范围往往与整数的分拆有很大关系）。解答这类方程，必须要对题中明显或隐含的条件加以判断、推理，才能正确求解。 【例1】★求方程2725=+y x 的正整数解。 【解析】因为2y 为偶数，27为奇数，所以5x 为奇数，即x 为奇数 ???==???==???==1 5,63,111y x y x y x 【小试牛刀】求方程4x ＋10y ＝34的正整数解 【解析】因为4与10的最大公约数为2，而2|34，两边约去2后，得 2x ＋5y ＝17，5y 的个位是0或5两种情况，2x 是偶数，要想和为17，5y 的个位只能是5，y 为奇数即可；2x 的个位为2，所以x 的取值为1、6、11、16…… x ＝1时，17－2x ＝15，y ＝3， x ＝6时，17－2x ＝ 5，y ＝1， x ＝11时，17－2x ＝17 －22，无解 所以方程有两组整数解为：16,31 x x y y ==????==?? 【例2】★ 设A ，B 都是正整数，并且满足33 17311=+B A ，求B A +的值。 【解析】33 1733113=+B A 3A+11B=17，因为A 、 B 为正整数，所以A=2，B=1，A+B=3 【例3】★★（北大附中入学考试真题）14个大、中、小号钢珠共重100克，大号钢珠每个重12克，中号每个重8克，小号每个重5克。问：大、中、小号钢珠各多少个 ?

丢番图和不定方程

丢番图和不定方程 ——兼谈中国人在这方面的工作 丢番图的工作 埃及尼罗河的出海口有一个大港叫亚历山大城，它是以希腊大帝亚历山大的名字命名。在两千年前这里曾是地中海文化的一个中心。 亚历山大大帝在公元前330年建立这城市，在公元前323年他去世之后，托勒米（Ptalamy）成为埃及的统治者。他选择这里为他的帝国的国都，并且模仿雅典的吕克昂学院在这里建立了一个博物院（Museum），世界各国的学者被邀请到这里来研究教导。 英国科学史家法灵顿（B．Farrington 1891—1974）在他的书《希腊人的科书》这么描写：“在埃及首都形成这个科学和艺术新中人的心里，存在一种美国式的豪华。” 编写著名的《几何原本》的欧几里得（Euclid）是博物院的第一个希腊数学教授。 在公元250年前后有一位希腊数学家丢番图（Dioplantos公元214－218年）住在亚历山大城里，他作为一个数学教员编写了一部叫《算术》（Arithmetica）的教科书。 这书总共有13卷，可惜在10世纪时只剩下6卷，其余7卷遗失了。在15世纪这书的希腊文手抄本在意大利的威尼斯发现于是广被人注意，以后又有法国数学家巴歇的希腊—拉丁文对照本，以后还有英、德、俄等国的译本，这是一本如《几何原本》般在数学上影响很大的书。 这本书基本上是代数书，有人称他为“代数学之父”，他书中采用符号，研究了一次、二次、三次方程。他是第一个引进符号入希腊数学的人。 如第一卷第27题：“两数之和是20，乘积是96，求这两数。” 第一卷第28题：“两数之和是20，平方和是208，求这两数。” 第六卷第27题：“求直角三角形的三边，已知它的面积加上斜边是一个平方数，而周长是一个立方数。” 写成现代的式子，令a，b，c是直角三角形的三边，则有： a2＋b2＝c2 a＋ b＋ c＝N3 这里就要考虑到三次方程了。

拿破仑定论、勾股定理、数论与密码

一、简述拿破仑定理及其证明方法 拿破仑定理:以任意三角形的三边为边向外作等边三角形，则这三个等边三角形的中心的连线是一个等边三角形。 如图8-27所示。在△ABC的各边上向外各作等边△ABD，等边△ACF，等边△BCE。 求证：这3个等边三角形的中心M、N、P的连线构成一个等边三角形？ 思路：利用已有的三个圆和三个四点共圆来证明。 证明：设等边△ABD的外接圆⊙N，等边△ACF的外接圆⊙M，等边△BCE的外接圆⊙P 相交于O；连AO、CO、BO。 ∵ A、D、B、O四点共圆； A、F、C、O四点共圆 B、E、 C、O四点共圆 ∠AFC=∠ADB=∠BEC=60°； ∴∠AOB=∠AOC=∠BOC=120°； ∵ NP、MP、MN是连心线； BO、CO、AO是公共弦； ∴ BO⊥NP于X； CO⊥MP于Y； CO⊥MP于Z。 ∴ X、P、Y、O四点共圆； Y、M、Z、O四点共圆； Z、N、X、O四点共圆； ∴∠N=∠M=∠P=60°； 即△MNP是等边三角形。 结论：图中本没有圆，为了方便读图，我特地画出了三个等边三角形的外接圆：⊙N、⊙M、⊙P，而且还有三个四点共圆之辅助圆。一共六个圆。这是多么奇妙的构思啊！ 二、美国总统garfield如何证明勾股定理的 以a、b 为直角边，以c为斜边作两个全等的直角三角形，则每个直角三角形的面积相等 . 把这两个直角三角形拼成如图所示形状，使A、E、B三点在一条直线上.

∵ Rt ΔEAD ≌ Rt ΔCBE, ∴ ∠ADE = ∠BEC. ∵ ∠AED + ∠ADE = 90o, ∴ ∠AED + ∠BEC = 90o. ∴ ∠DEC = 180o―90o= 90o. ∴ ΔDEC 是一个等腰直角三角形， 它的面积等于 2 5.0c . 又∵ ∠DAE = 90o, ∠EBC = 90o, ∴ AD ‖BC. ∴ ABCD 是一个直角梯形，它的面积等于2)(5.0b a +. ∴2)(5.0b a + =25.0c . ∴222c b a =+ 三、简介数论与密码 数论密码，顾名思义，就是基于数论的密码。密码是相对于明码而言的。这是一个矛盾的两个方面。所谓明码（plaintext ），就是人们可以直接识别或使用的代码（也就是人们通常所说的信息，如文字、声像等）；所谓密码（ciphertext ），就是将明码经过了一定处理，变换成一种外人（与此无关的人员）无法直接识别或使用的信息。 数论是数学中最古老、最纯粹的一个重要数学分支。素有“数学王子”之称的19世纪德国数学大师高斯就曾说过，数学是科学的皇后，数论是数学的皇后。数论的一个主要任务，就是研究整数（尤其是正整数）的性质（包括代数方程的整数解）。由于在研究这些整数的过程中，人们往往要用到别的数学分支的知识与技巧，这样就诞生出了解析数论、代数数论、组合数论、概率数论、几何数论甚至计算数论等分支学科。 由于整数的性质复杂深刻，难以琢磨，因此数论长期以来一直被认为是一门优美漂亮、纯之又纯的数学学科。美国芝加哥大学著名数学家迪克森（L.E.Dickson ）就曾说过：感谢神使得数论没有被任何应用所玷污。20世纪世界级数学大师、剑桥大学的哈代也曾说过：数论是一门与现实、与战争无缘的纯数学学科。哈代本人也则因主要从事数论的研究而被尊称为“纯之又纯的纯粹数学家”。 当然，上述两位大数学家所说的并不完全符合今天的现实。事实上，在计算机科学与电子技术深入发展的今天，数论已经不仅仅是一门纯数学学科，同时也是一门应用性极强的数学学科，比如在今天，数论已经在诸如物理、化学、生物、声学、电子、通讯，尤其是在密码学中有着广泛而深入的应用。 大家知道，密码设计长期以来一直是困扰军方的一个问题。要保证军方的密码不被敌方破译，不是件容易的事情。 比如在第二次世界大战期间，德军设计了一种性能优良的编制密码的机器，称之为爱尼格玛机器。德军指挥机关向其部队发布的军令都是通过爱尼格玛机器加密之后再往下发布的。当时英军就想到，要打败德军，就必须要破译德军的密码，掌握德军的军事动向（即所谓的知彼知己）。因此，英军迅速在伦敦北边不到一百公里处征集了一块空旷的土地（该地

中南大学 数论与密码实验报告

中南大学《数论及密码应用设计》 学生姓名 学号 专业班级 数学与统计学院 2013年11月

一、选做题：（至少选做两题） 1. 找尽可能大的素数p，使得2x x p -+当x=0,1,…,p-1时都为素数，没有找到也要写出已经找的范围. > 2. 在尽可能大的范围验证在n2和(n+1)2之间至少存在一个素数，进一步，当n>13 时，n和之间至少存在一个素数 > >

> 3. 验证，对于素数p>7，是否存在素数q 作为p 的原根，满足q<(p-1)/2, 又是否存在素数q 作为p 的原根，满足 4. 找尽可能大的n 2+1型的素数. > 5 验证，是否对于任意正整数n,存在素数p,使得1/p 的循环长度为n 6．找满足(mod )m a a m 的合数m 并求1/m 的循环节

二、必做题： 实现一种公钥密码系统 例如上课时讲到的4种中的一种. 目的：利用公钥加密，Alice 要求Bob 把message.txt 中的内容加密传给Alice ， message.txt 中的内容 canyoutellmethat ELG 公钥密码系统的描述 Alice 要求Bob 将信息m 加密送回，Alice 找到大素数p ，p 的原根a ，大整数A X （私钥），计算()A X A h a p ≡，将,,A p a h ，发送给Bob ； Bob 收到后，随机取{}1,2,,1k p ∈-， 计算()(),k A u a p v h m p ≡≡?，将,u v 发送给Alice ； Alice 收到后，计算()A A A A X k X k X k X A v u h m a a m a m p --??-??≡??≡??≡，这样就得到了原信息m 。 1）、密钥生成 选出一个大素数 p 选出 d 作为群G = < Z p *, ? >中的一个成员， 使得 1 ≤ d ≤ p - 2 选出 e 1作为群 G = < Z p *, ? > 中的一个本原根 e 2 ← e 1d mod p C 2 ← (P ? e 2r ) mod p // C 1和C 2是密文 Public_key ← (e 1, e 2, p ) // 公开宣布 Private_key ← d //保密 2）、解密 P ← [C 2 (C 1d ) -1] mod p // P 是明文 3）、证明 [C 2 (C 1d ) -1] mod p =(P ? e 2r ) ? (e 1dr ) -1 mod p = P 代码： 生成ELG 公钥，私钥的代码

小学数学不定方程与不定方程组的解法

不定方程与不定方程组 知识框架 一、知识点说明 历史概述 不定方程是数论中最古老的分支之一．古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程．中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志着中国对不定方程理论有了系统研究．宋代数学家秦九韶的大衍求一术将不定方程与同余理论联系起来． 考点说明 在各类竞赛考试中，不定方程经常以应用题的形式出现，除此以外，不定方程还经常作为解题的重要方法贯穿在行程问题、数论问题等压轴大题之中．在以后初高中数学的进一步学习中，不定方程也同样有着重要的地位，所以本讲的着重目的是让学生学会利用不定方程这个工具，并能够在以后的学习中使用这个工具解题。 二、不定方程基本定义 （1）定义：不定方程（组）是指未知数的个数多于方程个数的方程（组）。 （2）不定方程的解：使不定方程等号两端相等的未知数的值叫不定方程的解，不定方程的解不唯一。（3）研究不定方程要解决三个问题：①判断何时有解；②有解时确定解的个数；③求出所有的解 三、不定方程的试值技巧 （1）奇偶性 （2）整除的特点（能被2、3、5等数字整除的特性） （3）余数性质的应用（和、差、积的性质及同余的性质） 重难点 （1）b利用整除及奇偶性解不定方程 （2）不定方程的试值技巧 （3）学会解不定方程的经典例题

例题精讲 一、利用整除性质解不定方程【例 1】求方程2x－3y＝8的整数解 【考点】不定方程 【解析】方法一：由原方程，易得2x＝8＋3y，x＝4＋3 2 y，因此，对y的任意一个值，都有一个x与之对 应，并且，此时x与y的值必定满足原方程，故这样的x与y是原方程的一组解，即原方程的解 可表为： 3 4 2 x k y k ? =+ ? ? ?= ? ，其中k为任意数．说明由y取值的任意性，可知上述不定方程有无穷多 组解． 方法二：根据奇偶性知道2x是偶数，8为偶数，所以若想2x－3y＝8成立，y必为偶数，当y＝0，x＝4；当y＝2，x＝7；当y＝4，x＝10……，本题有无穷多个解。 【答案】无穷多个解 【巩固】求方程2x＋6y＝9的整数解 【考点】不定方程 【解析】因为2x＋6y＝2(x＋3y)，所以，不论x和y取何整数，都有2|2x＋6y，但29，因此，不论x和y取什么整数，2x＋6y都不可能等于9，即原方程无整数解． 说明：此题告诉我们并非所有的二元一次方程都有整数解。 【答案】无整数解 【例 2】求方程4x＋10y＝34的正整数解 【考点】不定方程 【解析】因为4与10的最大公约数为2，而2|34，两边约去2后，得2x＋5y＝17，5y的个位是0或5两种情况，2x是偶数，要想和为17，5y的个位只能是5，y为奇数即可；2x的个位为2，所以x的取值为1、6、11、16…… x＝1时，17－2x＝15，y＝3， x＝6时，17－2x＝5，y＝1， x＝11时，17－2x＝17 －22，无解

第5讲 高斯记号和不定方程

纵观数学史，最富传奇性的不定方程必然是：x n+y n=z n。 1637 年左右，法国“最伟大业余数学家”费马在研究丢番图《算术》时，在该书的第二卷页边写下了这样一个定理“x n+y n=z n，当n是大于2的整数时，没有正整数解”，单单是如此简洁的一个定理就有足够的吸引了，然而让众多数学家们深陷其中的则是费马接下来的一句话“我已发现了一种美妙的证法，可惜这里的空白太小，写不下”。 这个方程究竟有多传奇？就让我们从证明的历史中感受吧！ 1753 年，欧拉证明了n=3 时成立，不过n还有无限种情况 呢… 1816 年，巴黎科学院说：证明n是质数时成立就行了嘛，于是设了个奖，费马大定理火了。 1847 年，拉梅和柯西说：我证明了！可德国数学家库默尔说：你俩错了。 1850 年，库默尔说：我证明了100 以内除37、59、67 都成立。 1926 年，范狄维尔：库默尔你也不全对，n<211 时都成立。 二十世纪前期，勒贝格说：我证明了！不过很遗憾，发现又错了。 1908 年，沃尔夫斯凯尔奖设立，因为富豪沃尔夫斯凯尔在决意自杀前看到了费马大定理，算着算着就不想自杀了，救命之恩啊有没有！奖金十万马克啊有没有！ 1955 年，谷山-志村猜想提出，等等，这是解决椭圆问题的，和费马大定理有啥关系？ 1984 年，弗雷认为：应该有关系！可惜当时谷山丰没意识到，否则他应该不会自杀吧！ 1986 年，里贝特说：真的有关系！证明谷山---志村猜想就证明了费马大定理。 1993 年，安德鲁·怀尔斯说：我证明了！ 不会再错了吧？严格的审查后确定：真的又错了，有严重漏洞！ 怀尔斯说：知错就改，我再证！怀尔斯修补了漏洞，绝地逢生！大奖和奖金也收获囊中。 至此，费马大定理得到了最终证明！证明过程历时358年，横跨数学多个分支，吸引众多数学大师，其中历经种种艰辛，远不像文中如此轻描淡写，笔者也非常想详细描述，只是… “这里空白太小，写不下” 2011 年，谷歌（Google）纪念费马诞辰450 周年的Logo

数学在密码学中的应用浅析

龙源期刊网 https://www.doczj.com/doc/a95946303.html, 数学在密码学中的应用浅析 作者：黄耀 来源：《现代交际》2017年第22期 摘要：密码学作为一门交叉学科，涉及学科广泛，其中应用数学占很大比例，其地位在 密码学中也越来越重要，本文简单介绍密码学中涉及数学理论和方法计算的各种算法基本理论及应用，并将密码学的发展史分为现代密码学和传统密码学，列举二者具有代表性的明文加密方法，并分别对其中一种方法进行加密思想的概括和阐述。 关键词：密码学应用数学应用 中图分类号：TN918 文献标识码：A 文章编号：1009-5349（2017）22-0196-01 随着信息时代的高速发展，信息的安全越来越重要，小到个人信息，大到国家安全。信息安全主要是将计算机系统和信息交流网络中的各种信息进行数学化的计算和处理，保护信息安全，而密码学在其中正是处于完成这些功能的技术核心。在初期的学习当中，高等数学、线性代数、概率论等都是必须要学习的基础学科，但是涉及密码学的实际操作，数论和近世代数的数学知识仍然会有不同程度的涉及和应用，本文在这一基础上，讨论密码学中一些基本理论的应用。 一、密码学的含义及特点 密码学是由于保密通信所需从而发展起来的一门科学，其保密通讯的接受过程如下：初始发送者将原始信息（明文）进行一定方式转换（加密）然后发送，接受者收到加密信息，进行还原解读（脱密），完成保密传输信息的所有过程，但是由于传输过程是经由有线电或无线电进行信息传输，易被窃取者在信息传输过程中窃取加密信息，在算法未知的情况下恢复信息原文，称为破译。保密信息破译的好坏程度取决于破译者的技术及经验和加密算法的好坏。 实际运用的保密通信由两个重要方面构成：第一是已知明文，对原始信息进行加密处理，达到安全传输性的效果；第二是对截获的加密信息进行信息破译，获取有用信息。二者分别称为密码编码学和密码分析学，二者互逆，互相反映，特性又有所差别。 密码体制在密码发展史上是指加密算法和实现传输的设备，主要有五种典型密码体制，分别为：文学替换密码体制、机械密码体制、序列密码体制、分组密码体制、公开密钥密码体制，其中密码学研究目前较为活跃的是上世纪70年代中期出现的公开密钥密码体制。 二、传统密码应用 密码体制在1949年香农的《保密系统的通信理论》发表之前，密码传输主要通过简单置换和代换字符实现，这样简单的加密形式一般属于传统密码的范畴。置换密码通过改变明文排

丢番图方程整数解方法

. . . .. .. . 求不定方程整数解的常用方法 不定方程是指未知数的个数多于方程的个数，且未知数受到某些限制（如要有理数，整数或正整数等)的方程或方程组。不定方程也称丢番图方程，是数论的重要分支学科，也是数学上最活跃的数学领域之一。我国对不定方程的研究已延续了数千年，“百钱百鸡问题”等一直流传至今，“物不知其数”的解法被称为中国剩余定理。一般常用的求不定方程整数解的方法包括： (1)分离整数法 此法主要是通过解未知数的系数中绝对值较小的未知数，将其结果中整数部分分离出来，则剩下部分仍为整数，则令其为一个新的整数变量，以此类推，直到能直接观察出特解的不定方程为止，再追根溯源，求出原方程的特解. 例1 求不定方程02 5=-++y x x 的整数解 解 已知方程可化为 2 31232223225++=++++=+++=++=x x x x x x x x y 因为y 是整数，所以2 3+x 也是整数. 由此 x+2=1，-1，3，-3，即 x=-1，-3，1，-5， 相应的.0,2,0,4=y 所以方程的整数解为(-1,4),(-3,0),(1,2),(-5,0). (2)辗转相除法 此法主要借助辗转相除式逆推求特解，具体步骤如下： 第一步，化简方程，尽量化简为简洁形式(便于利用同余、奇偶分析的形式); 第二步，缩小未知数的围，就是利用限定条件将未知数限定在某一围，便于下一步讨论; 第三步，用辗转相除法解不定方程. 例2 求不定方程2510737=+y x 的整数解. 解 因为251)107,37(=,所以原方程有整数解. 用辗转相除法求特解: 18433,413337,33237107+?=+?=+?= 从最后一个式子向上逆推得到 19107)26(37=?+-?

小学思维数学：解不定方程-带详解

不定方程与不定方程组 1.利用整除及奇偶性解不定方程 2.不定方程的试值技巧 3.学会解不定方程的经典例题 一、知识点说明 历史概述 不定方程是数论中最古老的分支之一．古希腊的丢番图早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程．中国是研究不定方程最早的国家，公元初的五家共井问题就是一个不定方程组问题，公元5世纪的《张丘建算经》中的百鸡问题标志着中国对不定方程理论有了系统研究．宋代数学家秦九韶的大衍求一术将不定方程与同余理论联系起来． 考点说明 在各类竞赛考试中，不定方程经常以应用题的形式出现，除此以外，不定方程还经常作为解题的重要方法贯穿在行程问题、数论问题等压轴大题之中．在以后初高中数学的进一步学习中，不定方程也同样有着重要的地位，所以本讲的着重目的是让学生学会利用不定方程这个工具，并能够在以后的学习中使用这个工具解题。 二、不定方程基本定义 1、定义：不定方程（组）是指未知数的个数多于方程个数的方程（组）。 2、不定方程的解：使不定方程等号两端相等的未知数的值叫不定方程的解，不定方程的解不唯一。 3、研究不定方程要解决三个问题：①判断何时有解；②有解时确定解的个数；③求出所有的解 三、不定方程的试值技巧 1、奇偶性 2、整除的特点（能被2、 3、5等数字整除的特性） 3、余数性质的应用（和、差、积的性质及同余的性质） 模块一、利用整除性质解不定方程 【例 1】 求方程 2x －3y ＝8的整数解 【考点】不定方程 【难度】2星 【题型】解答 【解析】 方法一：由原方程，易得 2x ＝8＋3y ，x ＝4＋32 y ，因此，对y 的任意一个值，都有一个x 与之对应，并且，此时x 与y 的值必定满足原方程，故这样的x 与y 是原方程的一组解，即原方程的解可表为： 342x k y k ?=+???=?，其中k 为任意数．说明 由y 取值的任意性，可知上述不定方程有无穷多组解． 例题精讲 知识精讲 教学目标

2014数论与密码A

---○---○--- ---○---○--- 学 院 专业班级 学 号 姓 名 … … … … 评卷 密封 线 … … … … …… 密 封线 内不 要 答题 ，密封 线外 不 准 填写 考 生信 息， 违 者 考试 成 绩 按0 分 处理 … … … ……… 评 卷 密封 线 … … … … 中南大学考试试卷 时间100分钟 题 号 一 二 三 四 合 计 得 分 评卷人 复查人 2013~2014学年 二 学期 数论与密码基础 课程期末考试题 48 学时， 3 学分，闭卷，总分100分，占总评成绩 70 % 一. 选择题 (每小题4分, 共16分) 1. 设a,b ,c ∈Z ，下面论断中, 正确的是 ( ) A m|a,m|b ?,p q Z ?∈，m|pa+qb ； B 若 a=bc ，则|a|≤|b| C. a 2|b 2 ==> a |b D. a|bc ==> a |b 或a |c 2. 下列计算中, 结果错误的是 ( ) A. 455478692553*3728743351121=1698363146434284886901913 B. 34556786911112553*3727632621257357=128815006175702410974474606302421 C. 12345678901*3722762111257=45960025650387758488557 D. 4455478696662553*3727874321257351121=16609464622197502168179239973271913 3. 3对模11的指数为 ( ) A. 2 B. 3 C. 5 D. 10 4. 设a 是一个数码，59427673a 能被12整除，则a 为 ( ) A. 6 B. 3 C. 2 D. ABC 都不对 二. 填空题 (每小题5分, 共20分) 1. 设原文为 magic, 密码为cube ，采用维吉尼亚密码系统加密后密文为= ____________。 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 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2. 3关于模13的逆元是________。 3. Alice 要求Bob 将信息m 用RSA 方法加密传送回来, Alice 找到大素数p,q , 令n=pq , 取a 满足 (,())1a n ?=，再找d 使得d 为a 模()n ?的逆元，然后将公钥 发送给Bob 。 得 分 得 分 评卷人