大数据

当前位置:首页 > 大数据

《算法导论》第三十一章

第三十一章  数论算法

数论曾经被视为一种虽然优美但却没什么用处的纯数学学科。如今,数论算法已经得到了广泛的使用。这很大程度上要归功于人们发明了基于大素数的加密方法。快速计算大素数的算法使得高效加密成为可能,而目前其安全性的保证则依赖于缺少高效将合数分解为大素数之积(或求解相关问题,如计算离散对数)方法的现状。本章介绍一些数论知识以及相关的算法,它们是上文这类应用的基础。

31.1节介绍数论的一些基本概念,例如,整除性、等模和唯一因子分解。31.2 节研究世界上最古老算法之一的欧几里得算法,它用于计算两个整数的最大公约数。31.3 节回顾模运算的概念。31.4 节研究整数a的倍数模n的结果集合,并阐释用欧几里得算法求等式ax= b(mod n)的全部解的方法。31. 5节介绍中国余数定理。31.6 节考察整数a的幂模n所得的结果集合,描述反复平方算法,用于在已知a、b和n的情况下,高效计算abmod n的结果。这一运算是进行高效素数检测和许多现代密码学内容的核心部分。在此之后,31.7节描述RSA公钥加密系统。31.8节讨论一种随机性素数测试方法。该方法可用来高效地查找大素数,这正是为RSA加密系统创建密钥所必需的。最后,31.9 节回顾一个简单而有效的小整数因子分解启发式算法。有趣的是,由于RSA的安全性依赖于大整数因子分解的难度,人们恐怕更希望因子分解是一个无多项式解法的难题。

输入规模和算术计算的代价

由于我们将处理的对象是大整数,本章需要调整对于输入规模大小和基本算术运算代价的理解。

在本章中,“大输入”通常指包含“大整数”的输入,而不是包含“很多整数”的输入(像排序问题中那样)。因此,我们利用输入所需的位数来度量输入的大小,而不仅仅是输入中整数的数目。给定k个整数输入a1,a2,...,ak,如果算法可以在关于lga1,lga2,...,lgak 的多项式时间内完成,即算法在关于二进制编码后的输入长度的多项式时间内完成,则该算法称为多项式时间算法。

在本书的大部分章节中,将基本算术运算(乘法、除法或者计算余数)视为只耗费单位时间的原语操作是非常方便的。通过计算算法中包含的这类算术运算的数目,可以为合理评估算法在,计算机上的实际运算时间提供基准。然而,当输入很大时,基本运算也会变得耗时。因此,用数论算法所需的位运算数目作为基准来衡量算法的时间代价更为方便且合适。在此模型中,将两个β位整数用常规方法相乘需要θ(β2)次位运算。同样,用最朴素的方法计算一个β位整数除以另一个较短整数的商或余数需要耗时θ2)。(见练习31.1-12。)如今,人们已经有了更快的计算方法。例如,一个简单的分治算法可以在两个β位整数相乘的问题上达到θlg3)的运行时间。而已知最快的算法则只需要θ(βlg βlglg β)的运行时间。然而在实际问题中,θ2 )的算法往往效果最好。我们也将以该界作为算法分析的基准。

本章将既使用算法所需的算术运算的数目,也使用其所需位运算的数目来分析算法。


31.1 基础数论概念

本节将简单回顾基础数论中关于整数集Z={...,-2,-1,0,1,2}和自然数集N={0,1,2,...]的一些概念。

整除性与约数

一个整数可以被另外一个整数整除是数论中的一个关键概念。符号d|a(读作“d整除a")的含义是,存在某个整数k,使得a=kd。任何整数均可整除0。如果a>0且d|a,那么|d|≤|a|。如果d|a,则称a是d的倍数。如果d不能整除a,则写作QQ截图20220623144715.jpg

如果d|a且d≥0,则称d是a的约数。注意,d|a 当且仅当-d|a,即a的任何约数的负数同样可以整除a。因此,不失一般性,可规定约数为非负数。非零整数a的约数应至少为1,且不会大于|a|。例如,24的约数是1, 2, 3,4, 6, 8, 12和24。

任何正整数a均可被平凡约数1和其自身a所整除。整数a的非平凡约数称为a的因子。例如,20的因子是2,4,5和10。

素数与合数

如果一个整数a>1且只能被平凡约数1和它自身所整除,则这个数是素数。素数有许多特殊的性质。它在数论中也扮演着十分重要的角色。前20个素数按序排列如下:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71

练习31. 1-2要求读者证明存在无穷多个素数。如果一个整数a>1且不是素数,则称之为合数。例如,39 是一个合数,因为3|39。称整数1为基本单位,并且它既不是素数也不是合数。同样,整数0和所有负整数既不是素数也不是合数。

除法定理、余数和等模

给定一个整数n,我们可以将整数集划分为n的倍数和非n倍数两部分。通过计算非n倍数除以n的余数可以对非n倍数进行有效分类。而许多数论理论正是通过这种分类来改进对n的倍数和非n倍数的划分。下面的定理给出该改进的理论基础。这里,我们忽略了其证明(证明参见Niven和Zuckerman[ 265]等)。

定理31.1(除法定理)对于任何整数a和任何正整数n,存在唯一整数q和r,满足0≤r<n且a=qn十r。

称q=[a/n]为除法的商,值r=a mod n为除法的余数。n|a 当且仅当a modn=0。

根据整数模n的余数,我们可以将所有整数划分成n个等价类。包含整数a的模n等价类为

QQ截图20220623145310.jpg

例如,[3]7={...,-11, -4,3, 10,17, ...},这个集合同时也可以表示为[-4]7和[10]7。a∈[b]n和a=b(mod n)是等价的。所有这类等价类的集合是

QQ截图20220623145544.jpg

当读者看到

QQ截图20220623145645.jpg

这个定义时,按照式(31. 1)理解即可:0代表[0]n, 1代表[1]n,等等,即用每个等价类最小的非负元素来表示该等价类。然而,我们应该记着相应的等价类。例如,在我们说-1是Zn的一个元素时,实际上指的是[n-1]n,因为-1=n- 1(mod n)。

公约数与最大公约数

如果d是a的约数并且d也是b的约数,则d是a与b的公约数。例如,30 的约数包括1、2、3、5、6、10、15和30,因此24与30的公约数为1、2、3和6。需要注意的是,1是任意两个整数的公约数。

公约数的一条重要性质是:

QQ截图20220623150041.jpg

更一般地,对任意整数x和y,有

QQ截图20220623150148.jpg

并且,如果a|b,那么|a|≤|b|,或者b=0,而这说明

QQ截图20220623150232.jpg

两个不同时为0的整数a与b的公约数中最大的称为其最大公约数,记作gcd(a, b)。 例如,gcd(24, 30)=6,gcd(5, 7)=1, gcd(0, 9)=9。如果a与b不同时为0,则gcd(a, b)是一个在1与min(|a|, |b|)之间的整数。定义gcd(0, 0)=0,该定义是使gcd函数的基本性质(如下面

的等式(31.9))普遍成立所必不可少的。

下列性质是gcd函数的基本性质:

QQ截图20220623150652.jpg

下面的定理给出了gcd(a, b)的另外一个有用特征。

定理31.2  如果任意整数a和b不都为0,则gcd(a, b)是a与b的线性组合集{ax+by: x,y∈Z}中的最小正元素。

证明  设s是a与b的线性组合集中的最小正元素,并且对某个x,y∈Z,有s=ax+by。设q=[a/s],则式(3. 8)说明

QQ截图20220623151119.jpg

因此,a mod s也是a与b的一个线性组合。s是这个线性组合中的最小正数,由于0≤a mod s<s,故有a mod s=0。因此有s|a,类似地,可得到s|b。因此,s是a与b的公约数,所以gcd(a, b)≥s。因为gcd(a, b) 能同时被a与b整除,并且s是a与b的一个线性组合,所以由式(31.4)可知gcd(a, b)|s。 但由于gcd(a, b)|s和s>0,因此gcd(a, b)≤s。将上面已证明的gcd(a, b)≥s与gcd(a, b)≤s结合起来,得到gcd(a, b)=s,因此证明了s是a与b的最大公约数。

推论31.3  对任意整数a 与b,如果d|a且d|b,则d|gcd(a, b)。

证明  根据定理 31.2, gcd(a, b)是a与b的一个线性组合,所以由式(31. 4)可知,该推论成立。

推论31.4  对所有整数a和b以及任意非负整数n,有

QQ截图20220623151547.jpg

证明  如果n=0, 该推论显然成立。如果n>0,则gcd(an, bn)是集合{anx+ bny: x,y∈Z}中的最小正元素,即集合{ax+by: x,y∈Z}中最小正元素的n倍。

推论31.5  对于任意正整数n、a和b,如果n|ab且gcd(a, n)=1,则n|b。

证明  证明过程留作练习31.1-5。

互质数

如果两个整数a与b只有公约数1,即gcd(a, b)=1,则a与b称为互质数。例如,8和15是互质数,因为8的约数为1、2、4、8,而15的约数为1、3、5、15。下面的定理说明如果两个整数分别与一个整数p为互质数,则其积与p互质。

定理31.6  对任意整数a、 b和p,如果gcd(a, p)=1且gcd(b, p)=1,则gcd(ab,p)=1。

证明  由定理 31.2可知,存在整数x、y、x'和y'满足

QQ截图20220623162844.jpg

把上面两个等式两边分别相乘,经过整理得

QQ截图20220623163015.jpg

因为1是ab与p的一个正线性组合,所以应用定理31. 2就可以证明结论。

对于整数n1,n2,...,nk, 如果对任何i≠j都有gcd(ni, nj)=1,则称整数n1,n2,..., nk两两互质。

唯一因子分解定理

下面的结论说明关于素数整除性的一个基本而重要的事实。

定理31.7  对所有素数p和所有整数a, b, 如果p|ab,则p|a或p|b(或两者都成立)。

证明  采用反证法, 假设p|ab,但QQ截图20220623163315.jpg并且QQ截图20220623163346.jpg。因此,gcd(a, p)=1且gcd(b, p)=1,这是因为p的约数只有1和p,又因为假设a和b都不能被p整除。由定理31.6可知,gcd(ab,p)=1;由假设p|ab可知gcd(ab, p)=p,于是产生矛盾,从而证明定理成立。

从定理31.7可知,任意一个合数的素因子分解式是唯一的。

定理31.8  (唯一因子分解定理)  合数a仅能以一种方式写成如下乘积形式:

QQ截图20220623163531.jpg

其中pi为素数,p1<p2<...<pr,且ei为正整数。

证明  证明过程留作练习31.1-11。

例如,数6000可以唯一地分解为24 ·3·53


练习

31.1-1  证明:若a>b>c,且c=a+b,则c mod a=b。

31.1-2  证明有无穷多个素数。 (提示:证明素数p1,p2,...,pk都不能整除(p1p2...pk)+1)。)

31.1-3  证明:如果a|b且b|c,则a|c。

31.1-4  证明:如果p是素数并且0<k<p,则gcd(k, p)=1。

31.1-5  证明推论31. 5。

31.1-6  证明:如果p是素数且0<k<p,则QQ截图20220623164030.jpg。证明对所有整数a、b和素数p,有

QQ截图20220623164109.jpg

31.1-7  证明: 如果a和b是任意正整数,且满足a|b,则对任意x,

QQ截图20220623164157.jpg

在相同的假设下,证明对任意整数x和y,如果x=y(mod b),则x=y(mod a)。

31.1-8  对任意整数 k>0,如果存在一个整数a,满足ak=n,则称整数n是一个k次幂。如果对于某个整数k>1,n>1是一个k次幂,则称n是非平凡幂。说明如何在关于β的多项式时间内判定一个β位整数n是否是非平凡幂。

31.1-9  证明等式(31. 6)~(31.10)。

31.1-10  证明:最大公约数运算满足结合律,即证明对所有整数a、b和c,

QQ截图20220623164526.jpg

31.1-11  证明定理31.8。

31.1-12  试写出计算β位整数除以短整数的高效算法,以及计算β位整数除以短整数的余数的高效算法。所给出的算法的运行时间应为Θ(β2)。

31.1-13  写出一个高效算法,用于将β位二进制整数转化为相应的十进制表示。证明:如果长度至多为β的整数的乘法或除法运算所需时间为M(β),则执行二进制到十进制转换所需的时间为Θ(M(β)lgβ)。(提示:应用分治法,分别使用独立的递归计算结果的前段和后段。)

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~