《数论基础算法》由会员分享，可在线阅读，更多相关《数论基础算法（22页珍藏版）》请在金锄头文库上搜索。
1、数论基础算法数论基础算法原创：怒火之袍 2003 年 7 月 24 日 一、引言一、引言数论数论曾经被视为数学领域中华而不实的一个分支，然而现在它已经得到了广泛的应用， 这其中的部分原因应归结为以大素数为基础的密码体系的建立。这种体系的可行性在 于我们可以轻松地找到一些大素数，而体系的安全性则在于将大素数的乘积重新分解 因数往往十分困难。本文将介绍数论中比较基本的一些算法，面向的读者应具有代数 结构的基础知识。二、求最大公约数二、求最大公约数我们首先要介绍的是能够有效计算两个整数的最大公约数的欧几里得算法欧几里得算法（Euclids algorithm，又称辗转相除法）（下文中用 gcd(a,
2、b)来表示整数 a 与 b 的最大公约数，由 于 gcd(a,b)=gcd(|a|,|b|)，我们将参数的范围限定在非负整数的范围内）。将 a、b 分别分解质因数后即可求得二者的最大公约数，然而即使是最好的算法也不能 使位操作意义下的时间复杂度达到多项式级（数论算法的时间复杂度分析常常指在位 操作的意义下）。高校的欧几里德算法是建立在下面的定理上的：对于任何的非负整数 a 和正整数 b,有 gcd(a,b)=gcd(b,a mod b)。欧几里得算法的流程为：EUCLID(a,b)if b=0then return aelse return EUCLID(b,a mod b)比如我们要求 31
3、 和 20 的最大公约数,则 EUCLID 的运行过程为：EUCLID(30,21)=EUCLID(21,9)=EUCLID(9,3)=EUCLID(3,0)=3。关于该算法的效率分析，有如下定理阐述：对任何对任何 k=1，若，若 ab=1 且且 b2 有 Fk+1 mod Fk=Fk-1，所以 gcd(Fk+1,Fk)=gcd(Fk,(Fk+1 mod Fk)=gcd(Fk,Fk-1)，而 CLID(F3,F2)=EUCLID(2,1)的计算是需要进行一次递归调用的。现在我们来改写欧几里得算法以计算附加的有用信息，使得我们可以在算法结束时获 得两个整数（可能为 0 或负数）x、y 使等式 d
4、=gcd(a,b)=ax+by 成立。如下所示的 EXTENDED-EUCLID 过程接收一对非负整数，返回满足上述等式的三元组(d,x,y)：EXTENDED-EUCLID(a,b)if b=0then return (a,1,0)(d,x,y)EXTEND-EUCLID(b,a mod b)(d,x,y)=(d,y,x-floor(a/b)*y)return (d,x,y)EXTENDED-EUCLID 过程与 EUCLID 过程的时间复杂度在渐近意义下相同，差别仅在 于常数因子，而由此得出的 x、y 却对解决一些问题十分有用。三、求解同余线性方程三、求解同余线性方程在一些重要的应用中常会
5、涉及到求解如下同余线性方程的问题：a*x 模 n 余 b，求 x。 这个问题有解的条件是 d=gcd(a,n)|b，在已知有解 x0 的情况下，可以推出其在模 n 意 义下的全部解,即 xi=x0+i*(n/d)(i=0,1.d-1)，具体过程如下：MODULAR-LINEAR-EQUATION-SOLVER(a,b,n)(d,x,y)EXTENDED-EUCLID(a,n)if d|bthen x0x(b/d) mod nfor i0 to d-1do print (x0+i(n/d) mod nelse print “no solutions“四、中国剩余定理四、中国剩余定理中国有一本数学
6、古书孙子算经有这样的记载：今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？ 答曰：二十三 术曰：三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之 剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之 剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五， 即得。孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后， 以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广 及其解法，被称为中国剩余定理。中国剩余定理（Chinese Remainder Theorem）在近代 抽象代数学中占有
7、一席非常重要的地位。它揭示了这样两个系统的一致性：一是模两 两互质的一组数的同余方程组，二是模它们的乘积的方程。中国剩余定理的内容如下：令 n=n1n2.nk，其中 ni 是两两互质的数，则对 0是整数 b 的二进制表示（即 b 的二进制有 k+1 位，bk是 最高位），下列过程随着 c 的值从 0 到 b 成倍增加，最终计算出 ac mod nModular-Exponentiation(a, b, n)c 0d 1设设是是 b 的二进制表示的二进制表示for ik downto 0do c 2cd (d*d) mod nif bi = 1 then c c + 1d (d*a) mod n
8、return d上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者是前一个幂的两倍再乘 上底数 a。过程依次从右到左逐个读入 b 的二进制表示已控制执行哪一种操作。循环中 的每次迭代都用到了下面的两个恒等式中的一个：a(2c) mod n = (ac mod n)2 a(2c+1) mod n = a * (ac mod n)2用哪一个恒等式取决于 bi=0 还是 1。由于平方在每次迭代中起着关键作用，所以这种 方法叫做“反复平方法(repeated squaring)”。在读入 bi位并进行相应处理后，c 的值 与 b 的二进制表示的前缀的值相同。事实上，算法中并不真正需要 变量 c，只
9、是为了说明算法才设置了变量 c：当 c 成倍增加时，算法保持条件 d = ac mod n 不变，直至 c=b。 如果输入 a,b,n 是 k 位的数，则算法总共需要执行的算术运算次数为 O(k)，总共需要 执行的位操作次数为 O(k3)。六、六、RSA 公钥加密系统公钥加密系统笔者本想在此文中详细介绍一下这部分的内容，但是最近在一些论坛上经常见到一些 传闻说到印度的几个科学家已经发明了在多项式（位操作意义下）时间内分解大合数 的方法，使得基于素数理论的加密体系受到动摇。笔者未能证实消息来源的可靠性， 因此将简要地对这部分的内容做一个概括，有兴趣的读者需要关注一下密码学最新的 动态。在一个公钥
10、加密系统中，每个参与者都拥有一个公钥和密钥，每个人对自己的密钥保 密，而一般将公钥公开，假设基于公钥 PA 的一个函数是 PA(),而基于密钥 SA 的一个 函数是 SA()，那么对于传输的信息 M,一般有M=SA(PA(M)且且 M=PA(SA(M)。因此，设计一个可行的公钥加密系统的最大困难在于解决如何在展示 PA 的同时不使除 自己外的其它人拥有计算 SA 的能力。RSA 公钥加密系统借助了数论中的这样一个事实：寻找大素数很容易而分解两个大素数的乘积则很困难。在 RSA 公钥加密系统中，参与者按照如下的步骤制造商他的公钥与密钥。1.随机选择两个不等素数 p 和 q。2.计算出 n=pq。
11、3.选择一个小奇数 e 使它和(p-1)(q-1)互质。4.计算 e 在模(p-1)(q-1)的逆元 d。5.公开数对(e,n)作为 RSA 公钥。6.保留数对(d,n)作为他的 RSA 密钥。在信息传递的过程中，发送消息者将信息用基于接收者公钥的算法进行加密，因此在 消息传递的过程中即使被窃听者截获，也因为他无法获得接收者的密钥而破解密文； 至于接收者本身则因为持有自己的密钥而可以解读传递过来的信息。除了 RSA 公钥加密系统外，诸如数字签名等一些其他技术也借用了数论中寻找大素数 和分解大合数的这一对矛盾，因此从某种意义上讲，人类可能希望分解大合数的问题 永远不要被解决，这实在是一个有趣的现
12、象。 有关数论的算法-数论的基本知识数论的基本知识 本文将简单地介绍有关整数集合 Z=,-2,-1,0,1,2,和自然数集合 N=0,1,2,的最基本的 数论概念。 可除性与约数 一个整数能被另一个整数整除的概念是数论中的一个中心概念，记号 d|a（读作“d 除 a” ）意味 着对某个整数 k，有 a = kd。0 可被每个整数整除。如果 a0 且 d|a，则|d|a|。如果 d|a，则我 们也可以说 a 是 d 的倍数。如果 a 不能被 d 整除，则写作 dFa。 如果 d|a 并且 d0，则我们说 d 是 a 的约数。注意，d|a 当且仅当(-d)|a，因此定义约数为非负整数 不会失去一般
13、性，只要明白 a 的任何约数的相应负数同样能整除 a。一个整数 a 的约数最小为 1，最 大为|a|。例如，24 的约数有 1，2，3，4，6，8，12 和 24。 每个整数 a 都可以被其平凡约数 1 和 a 整除。a 的非平凡约数也称为 a 的因子。例如， 20 的因子有2， 4，5 和 10。 素数与合数 对于某个整数 a1，如果它仅有平凡约数 1 和 a，则我们称 a 为素数(或质数)。素数具有许多特殊性 质，在数论中举足轻重。按顺序，下列为一个小素数序列: 2，3，5，6，11，13，17，19，23，29，31，37，41，43，47，53，59， 不是素数的整数 a1 称为合数。
14、例如，因为有 3|39，所以 39 是合数。整数 1 被称为基数，它既不是 质数也不是合数。类似地，整数 0 和所有负整数既不是素数也不是合数。 定理 1 素数有无穷个。 证明： 假设素数只有有限的 n 个，从小到大依次排列为 p1,p2,.,pn，则 x = (p1p2.pn)+1 显然是不能被 p1,p2,.,pn 中的任何一个素数整除的，因此 x 也是一个素数，这和只有 n 个素数矛 盾，所以素数是无限多的。 这个证明的最早来自亚里士多德，非常漂亮，是反证法的经典应用，这个证明被欧拉称为“直接来 自上帝的证明” ，历代的数学家也对其评价很高。 除法定理，余数和同模 已知一个整数 n，所有
15、整数都可以分划为是 n 的倍数的整数与不是 n 的倍数的整数。对于不是 n 的倍 数的那些整数，我们又可以根据它们除以 n 所得的余数来进行分类，数论的大部分理论都是基于上 述分划的。下列定理是进行这种分划的基础。 定理 2 (除法定理) 对任意整数 a 和任意正整数 n，存在唯一的整数 q 和 r，满足 0 O，可知 gcd(a,b)s。而上面已证明 gcd (a,b)s，所以得到 gcd(a,b) = s，我们因此可得到 s 是 a 与 b 的最大公约数。 推论 4 对任意整数 a 与 b，如果 d|a 并且 d|b，则 d|gcd(a,b)。 证明： 根据定理 3，gcd(a，b)是 a 与 b 的一个线性组合，所以从式(6)可推得该推论成立。 推论 5 对所有整数 a 和 b 以及任意非负整数 n，gcd(an ,bn)=n gcd(a,b)。 证明： 如果 n = 0，该推论显然成立。如果 n 0，则 gcd(an,bn)是集合anx +
