大数据

当前位置:首页 > 大数据

《算法导论》第三十一章 续5

*31.8 素数的测试

在本节中,我们要考虑寻找大素数的问题。首先讨论素数的密度,接着讨论一种似乎可行,但不完全可行的测试素数的方法,然后介绍一种由Miller和Rabin发现的有效的随机素数测试算法。

素数的密度

在很多应用领域,如密码学中,需要找出大的“随机”素数。幸运的是,大素数并不少,因此测试适当的随机整数,直至找到素数的过程是可行的。素数分布函数π(n)描述了小于或等于n的素数的数目。例如π(10)=4,因为小于或等于10的素数有4个,分别为2,3,5,7。素数定理给出了π(n)的一个有用近似。

定理31. 37(素数定理)

QQ截图20220627163230.jpg

即使对于较小的n,近似计算式n/lnn也可以相当精确地给出π(n)的估计值。例如,当n=109时,其误差不超过6%,这里π(n)=50847534,且n/ lnn≈482 549 42。(对数论研究者来说,109是一个小数字。)

我们可以把随机选取一个整数n,并判断它是否为素数这一过程视为伯努利试验(见C.4节)。通过素数定理,成功(即一个随机选取的整数n是素数)的概率为1/ lnn。这种几何分布说明,为了获得一次成功需要多少次试验,而由于等式(C.32),试验的期望值近似为Inn。因此,为了找出一个长度与n相同的素数,要检查在n附近随机选取的大约Inn个整数。例如,为了找出一个1024位长的素数,大约需要测试ln21024≈710个随机选取的1024位长的整数的素性。(当然,通过只选择奇数,就可以把这个数字减少一半。)

在本节的余下部分,将要考虑确定一个大的奇数n是否为素数的问题。为了表示上的方便,假定n具有下列素数分解因子:

QQ截图20220627163500.jpg

这里r≥1,p1,p2,...,pr是n的素数因子,且e1,e2,...,er是正整数。当且仅当r=1并且e1=1时,n是素数。

解决这个素数测试问题的一种简便方法是试除。试着用每个整数2, 3,...,[√n]分别去除n。(大于2的偶数可以跳过。)很容易看出,n是素数当且仅当没有一个试除数能整除n。假定每次试除需要常数时间,则最坏情况运行时间是Θ(√n),这是n的长度的指数。(回顾一下,如果n表示成β位的二进制数,则β=「lg(n+1)],因此√n=Θ(22)。)因此,只有当n很小或n恰好有小素数因子时,试除法才能较好地执行。当试除法可以执行时,它的优点是不仅能确定n是素数还是合数,而且当n是合数时,它能确定出n的一个素数因子。

在本节中,我们所感兴趣的仅仅是确定一个指定的数n是否是素数;如果n是一个合数,将不考虑找出其素数因子。正如将在31.9节中看到的那样,计算一个数的素数因子分解的计算开销是很高的。令人惊讶的是,确定一个数是否是素数,要比确定一个合数的素因子分解容易得多。

伪素数测试过程

现在来考察一种“几乎可行”的素数测试方法,事实上,对于很多实际应用,这种方法已经足够好了。后面还将改进这种方法,以消除其中的小缺陷。令Zn+表示Zn中的非零元素:

QQ截图20220627164212.jpg

如果n是素数,则Zn+=Zn*。

如果n是一个合数,且

QQ截图20220627164223.jpg

则称n是一个基为a的伪素数。费马定理(定理31. 31)意味着如果n是素数,则对Zn+中的每一个a,n都满足等式(31.40),因此,如果能找出任意的a∈zn+,使得n不满足等式(31.40),那么n就当然是合数。令人惊讶的是,它的逆命题也几乎成立,因此,对于素数测试,这一标准几乎是完美的。对a=2,测试看n是否满足等式(31.40)。如果不满足,则通过返回COMPOSITE声明n是合数。否则,返回PRIME,猜测n是素数(实际上,此时我们所知道的只是n或者是素数,或者是基于2的伪素数)。

下列过程就是用这种方法测试n的素性过程。它使用了31.6 节中的MODULAR-EXPONENTIATION过程。假设输入n是一个大于2的整数。

QQ截图20220627165005.jpg

这个过程可能会产生错误,但是只有一种类型。也就是说,如果它判定n是合数,那么结果总是正确的。然而,如果它判定n是素数,那么只有当n是基于2的伪素数时过程才会出错。

这个过程出错的概率有多大?机会非常少。在小于10000的n值中,只有在其中22个值上会产生错误。最靠前的四个这样的值分别为341,561,645 和1105。我们不证明它,然而当β→∞时,该过程对随机选取的β位数进行测试,错误的概率趋于0。如果像Pomerance[279]那样,能更精确地估计给定规模的基于2的伪素数的个数,就可以得到被上述过程判定为素数的一个随机选取的512位数,是基于2的伪素数的概率不到1/1020,而被上述过程判定为素数的一个随机选取的1024位数,是基于2的伪素数的概率不到1/1041。因此,如果只是尝试为某个应用找到一个大素数,可以通过随机选取大的数字,直到它们其中之一使得PSEUDOPRIME返回PRIME,这在所有实际使用中几乎永远不会出错。但是当测试素数的数字不是随机选取时,就需要一个更好的方法来进行素数测试。后面将会看到,如果稍微巧妙一点,再加上一些随机性,

就会得到一个在所有输入情况下都工作良好的素数测试程序。

遗憾的是,我们不能完全通过选取另外一个基数(例如a=3)检查等式(31.40)的方法,来消除所有的错误,因为对所有a∈Zn*,总存在满足等式(31.40)的合数n,它们被称为Carmichael数。(注意到当gcd(a, n)>1(也就是当a∉Zn*)时,等式(31. 40)不成立,然而如果n只有大素数因子,很难通过寻找这样的a来说明n是合数。)前三个Carmichael数是561,1105 和1729。Carmichael数极少;例如,在小于100 000 000的数中,只有255个Carmichael数。练习31. 8-2解释了这种数很少的原因。

下一步来说明如何对素数测试方法进行改进,使得测试过程不会把Carmichael数当成素数。

Miller- Rabin随机性素数测试方法

Miller- Rabin素数测试方法对简单测试过程PSFUDOPRIME做了两点改进,克服了其中存在的问题:

  • 它试验了多个随机选取的基值n,而非仅仅一个基值。

  • 当计算每个模取幂的值时,在最后一组平方里,寻找一个以n为模的1的非平凡平方根。如果发现一个,终止执行并输出结果COMPOSITE。31.6 节的推论31. 35证明了用这种方法检测合数的正确性。

下面是Miller- Rabin素数测试的伪代码。输入n>2是一个等待素性测试的奇数,s是从Zn+中随机选取的要进行试验的基值的个数。代码运用随机数生成程序RANDOM:RANDOM(1,n-1)返回一个满足1≤a≤n-1的随机选取的整数a。代码中还使用一个辅助过程WITNESS,当且仅当a为合数n的“证据”时(即用a来证明(其证明方法将在后面给出)n为合数是可能的),WITNESS(a, n)为TRUE。测试WITNESS(a, n) 是一个对作为过程PSEUDOPRIME基础(用a=2)的测试

QQ截图20220627170133.jpg

的扩展,但是更加有效。首先要介绍并证明WITNESS的构造过程,然后展示如何把它应用于Miller- Rabin素数测试过程。令n- 1=2tu,其中t≥1且u是奇数;即n-1的二进制表示是奇数u的二进制表示后面跟上恰好t个零。因此,an-1=(au)2 '(mod n),所以可以通过先计算au mod n,然后对结果连续平方t次来计算an-1 mod n。

QQ截图20220627170406.jpg

这个WITNESS的伪代码通过首先在第2行计算值x0=au mod n,然后在第3~6行的for 循环的一行中对结果平方t次,来计算an-1 mod n。通过在i上归纳,计算的序列x0,x1,...,xt的值满足等式xi=a2'u(mod n)(i=0,1,...,t),所以特别地,xt=an-1(modn)。然而,每当在第4行后执行一个平方步骤,如果第5~6行检测到1的一个非平凡平方根是刚被发现的,则循环可能提前结束。如果这样,则算法终止并返回TRUE。如果xt=an-1 (mod n)所计算的值不等于1,则第7~8行返回TRUE,就像在这个情况中PSEUDOPRIME返回COMPOSITE。如果在第6行或第8行没有返回TRUE,则第9行返回FALSE。

现在来论证如果WITNESS(a, n) 返回TRUE,则可以用a作为证据构造出n是合数的证明。

如果WITNESS从第8行返回TRUE,则它已经发现xt=an-1 mod n≠1。然而,如果n是素数,则根据费马定理(定理31.31),对任何a∈Zn+,an-1=1(mod n) 成立。因此,n不可能为素数,并且等式an-1 mod n≠1证明了这一事实。

如果WITNESS从第6行返回TRUE,则它已经发现xi-1是一个以n为模的1的非平凡平方根,因为xi-1≠土1(mod n),但xi=x2i-1=1(mod n)。 推论31. 35说明仅当n是合数时,才可能存在以n为模的1的非平凡平方根,因此说明xi-1是以n为模的1的非平凡平方根,也就证明了n是合数。

这样就完成了有关WITNESS正确性的证明。如果调用WITNESS(a,n)返回TRUE,则n必为合数,并且根据证据a以及程序返回值为TRUE的原因(从第6行还是第8行返回),可以很容易确定n是合数。

在这里,我们以序列X=<x0,x1,...,xt)的函数形式简短地展示WITNESS的行为的另一种描述,稍后在分析Miller-Rabin素数测试的效率时,会发现它很有用。注意,如果对某个0≤i<有xi=1,则WITNESS可能不会计算序列的余下部分。然而如果计算,则xi+1,xi+2,...,xt的值都将是1,并且我们考虑序列X中的这些位置都是1。有四种情况:

1.X=..., d),其中d≠1:序列X不是以1结尾。从第8行返回TRUE; a是n为合数的证据(由费马定理)。

2.X=<1,1,...,1>:序列X全都是1。返回FALSE,a不是n为合数的证据。

3.X-=...,-1,1,...,1>:序列X以1结尾,而且最后一个非1的数等于一1。返回FALSE,a不是n为合数的证据。

4.X-=<...,d,1,...,1>,其中d≠士1:序列X以1结尾,但最后一个非1的数不是-1。

从第6行返回TRUE;a是n为合数的证据,因为d是一个1的非平凡平方根。

现在检查利用WITNESS的MILLE- RABIN素数测试过程。再一次,假设n是一个大于2的奇数。

QQ截图20220627172423.jpg

过程MILLE- RABIN是为了证明n是合数所进行的概率性搜索。主循环(从第1行开始)从Zn+中挑选s个a的随机值(第2行)。如果所挑选的一个a值是n为合数的证据,则过程MILLE-RABIN在第4行返回COMPOSITE。这样的结果总是正确的,由WITNESS的正确性证明可以看出。如果在s次试验中没有发现证据,则MILLERABIN假定这是因为证据不存在,因此假

设n为素数。我们将看到如果s足够大,则这个输出结果很可能是正确的,但也存在这样一种微小的可能性,即过程在选择a时运气不佳,因为过程虽然没有发现证据,但证据却确实存在。

为了说明MILLE- RABIN的操作过程,令n为Carmichael数561,使得n-1=560=24·35,t=4,u=35。假定过程选择a=7作为基,31.6 节的图31-4说明WITNESS计算x0=a35=241(mod 561),因此计算序列X=<241,298, 166, 67, 1>。所以,在最后一次平方步骤中发现了一个 1的非平凡平方根,因为a280=67(mod n), a560=1(mod n)。 因此,a=7是n为合数的证据,WITNESS(7,n)返回TRUE,因而MILLE- RABIN返回COMPOSITE。

如果n是一个β位数,则MILLE- RABIN需要执行O(sβ)次算术运算和O(sβ3)次位操作,因为从渐近意义上说,它需要执行的工作仅是s次模取幂运算。

MILLE-RABIN素数测试的出错率

如果MILLE- RABIN返回PRIME,则它仍有一种很小的可能性会产生错误。然而,不像PSEUDOPRIME,出错的可能性并不依赖于n;对该过程也不存在坏的输入。相反,它取决于s的大小和在选取基值a时“抽签的运气”。另外,由于每次测试都比简单地检查等式(31.40)更严格,因此从总的原则上,对随机选取的整数n,其出错率应该是很小的。下列定理阐述了一个更精确的论点。

定理31.38    如果 n是一个奇合数,则n为合数的证据的数目至少为(n- 1)/2。

证明    证明过程说明了非证据的个数最多为(n- 1)/2,意味着定理成立。

首先,我们断言任何非证据都必须是Zn*的一个成员。为什么呢?考虑任意的非证据a。它必须满足an-1=1(mod n),或者等价地,a·an-2=1(mod n)。因此,方程ax=1(mod n)有一个解,即an-2。由推论31.21可知,gcd(a, n)|1, 这反过来意味着gcd(a, n)=1。因此,a是Zn*的一个成员,所有的非证据都属于Zn*。

为了完成证明,要说明不只是所有的非证据都包含在Zn*内,而且它们都包含在Zn*的一个真子群B中(回顾一下,如果B是Zn*的一个子群但B不等于Zn*,则B是Zn*的一个真子群)。根据推论31.16,有|B|≤|Zn*|/2。因为|Zn*|≤n-1,所以得到|B|≤(n- 1)/2。 因此,非证据的个数至多是(n- 1)/2, 所以证据的数目必须至少有(n- 1)/2。

下面说明如何找出一个Zn*的包含所有非证据的真子群B。具体分两种情况。

情况1:存在一个x∈Zn*,使得

QQ截图20220628085547.jpg

换句话说,n不是一个Crmichael数。如我们先前所注意到的,因为Carmichael数极少,情况1是由“实际”所产生的主要情况(例如,这里n已经被随机选取,而且被测试其素数性)。

令B={b∈Zn*:bn-1=1(mod n)}。 显然,B是非空的,因为1∈B。因为B在模n的乘法下是封闭的,所以由定理31.14,B是Zn*的一个子群。注意,每个非证据都属于B,因为一个非证据a满足an-1=1(mod n)。因为x∈Zn*-B,所以B是Zn*的一个真子群。

情况2:对所有的z∈Zn*,

QQ截图20220628090310.jpg

换句话说,n是一个Carmichael 数。这个情况实际上非常少。然而,正如现在要说明的,MILLE- RABIN测试(不同于伪素数测试)可以有效地确定Carmichael数的合数性。

在这种情况下,n不可能是一个素数幂。为搞清楚为什么,反之我们假设n=pe,其中p是一个素数,e>1。按如下方式推导出矛盾。因为n假设是奇数,故p也必须是奇数。定理31. 32意味着Zn*是一个循环群:它包含一个生成元g,使得ordn(g)=|Zn*| =Φ(n)=pe(1- 1/p)=(p- 1)pe-1(Φ(n)的公式来自等式(31.20))。根据式(31.41),有gn-1=1(mod n)。则离散对数定理(定理31.33,取y=0)意味着n-1=0(mod Φ(n)),或者

QQ截图20220628090945.jpg

这对e>1是一个矛盾,因为(p- 1)pe-1可以被素数p整除,但是pe-1不能。因此,n不是一个素数幂。

因为奇合数n不是一个素数幂,我们把它分解成一个积n1n2,其中n1和n2都是大于1的奇数且互质。(有多种方法来做这个分解,选择哪一种并没有关系。例如,如果n=p1e1p2e2...prer则可以选择n1=p1e1,而n2=p2e2 p3e3...prer)

回顾一下,定义t和u使得n-1=2tu,其中t≥1,u是奇数,且对于输入a,过程WITNESS计算序列

QQ截图20220628091616.jpg

(所有的计算都是根据模n计算的)。

如果v∈Zn*,j∈{0, 1,...,t}且v2ju=-1(mod n),则称整数对(v, j)为可接受的。可接受的对是肯定存在的,因为u是奇数;可以选择v=n-1和j=0,使得(n-1, 0)是一个可接受对。现在挑选最大可能的j,使得存在一个可接受对(v, j),调整v使得(v,j)是一个可接受对,令

QQ截图20220628091831.jpg

因为B在模n的乘法下是封闭的,故它是Zn*的一个子群。因此,由定理31.15,|B|整除 |zn*|。每一个非证据都必定是B的成员,因为由一个非证据产生的序列X必须或者全部为1,或者在第j个位置之前,包含一个-1(根据 j 的最大性)。(如果(a, j')是可接受的,其中a是一个非证据,则根据我们选择j的方式,必有j'≤j。)

现在,利用v的存在性说明存在一个w∈Zn*- B,且因此B是Zn*的一个子群。因为v2'u= - 1(mod n),根据中国余数定理的推论31. 29,有v2'u=-1(mod n)。根据推论31.28,存在一个w,同时满足

QQ截图20220628092420.jpg

因此

QQ截图20220628092448.jpg

由推论31. 29,w2ju ≠1(mod n1)意味着w2ju≠1(mod n),而且w2ju≠-1(mod n2)意味着w2ju≠-1(mod n)。因此,得出w2ju≠士1(mod n),所以w∉B。

接下来还要证明w∈Zn*。首先分别对模n1和模n2进行处理。对模n1,注意到由于v∈Zn*,有gcd(v, n)=1,所以有gcd(v, n1)=1;如果v与n没有任何公约数,它当然不会与n有任何公约数。因为w=v(mod n1),所以gcd(w,n1)=1。 对模n2观察到w=1(mod n2)意味着gcd(w,n2)=1。 结合这些结果,利用推论31.6,它意味着gcd(w,n1n2)=gcd(w,n)=1。也就是w∈Zn*。

因此,w∈Zn*-B,而且以B是Zn*的一个真子群的结论完成情况2。

在两种情况中的任何一个,我们看出n为合数的证据的数目都至少为(n-1)/2。

定理31.39    对于任意奇数n>2 和正整数s,MILLER- RABIN(n, s)出错的概率至多为2-s

证明    利用定理 31.38,可以看到如果n是合数,则每次执行第1~4行的for循环,发现n为合数的证据x的概率至少为1/2。只有当MILLER-RABIN运气太差,在主循环总共s次迭代中,每一次都没能发现n为合数的证据时,过程才会出错。而这种每次都错过发现证据的概率至多为2-s

如果n是素数,MILLER-RABIN总是输出PRIME,而如果n是合数,MILLER- RABIN输出PRIME的概率至多为2-s

然而,当对一个大随机整数n应用MILLER- RABIN时,为了正确地解释MILLER- RABIN的结果,我们需要考虑n是素数的优先概率。假设固定了一个长度位数β,并且随机选择了一个长度为β位的整数来检测优先级。令A表示n是素数的事件。由素数定理(定理31.37),n是素数的概率接近

QQ截图20220628094206.jpg

令B表示MILLER- RABIN返回PRIME的事件,我们有Pr{QQ截图20220628094257.jpg|A}=0(或者等价地,Pr{B|A})和Pr{B|QQ截图20220628094315.jpg}≤2-s(或者等价地,Pr{QQ截图20220628094257.jpg|QQ截图20220628094315.jpg}>1-2-s)。

然而在MILLER- RABIN返回PRIME的情况下,n是素数的概率Pr{A|B}的值是多少呢?通过贝叶斯定理的变形(等式(C.18)),有

QQ截图20220628094504.jpg

在s超过lg( lnn- 1)之前,这个概率不超过1/2。直观上,为了得到信心(由于不能找到n是合数的证据),来克服对于n是合数的优先偏好,需要很多原始测试。对于一个有β=1024位的数,原始测试大约需要

QQ截图20220628094620.jpg

次。在任何情况下,对几乎所有可以想象到的应用,选取s=50应该是足够的。

事实上情况要更好。如果通过对随机选取的大奇整数应用MILLER-RABIN来找出大素数,则选取较小的s值(如3)也未必导致错误的结论(在此不做证明)。因为对一个随机选取的奇合数n,n为合数的非证据的预计数目可能要比(n-1)/2少得多。

然而,如果整数n不是随机选取的,则运用改进过的定理31. 38,所能证明的最佳结论是非证据数目至多为(n-1)/4。并且,确实存在整数n,使得非证据的数目就是(n-1)/4。

练习

31.8-1  证明:如果一个奇整数n>1不是素数或素数的幂,则存在一个以n为模的1的非平凡平方根。

31.8-2  可以把欧拉定理稍微加强为如下形式:对所有a∈Zn*,

QQ截图20220628094843.jpg

其中n=p1e1p2e2...prer,且λ(n)定义为

QQ截图20220628095102.jpg

证明λ(n) |Φ(n)。如果λ(n)|n-1,则合数n为Carmichael数。最小的Carmichael数为561=3·11·17;这里,λ(n)=1cm(2,10,16)=80,它可以整除560。证明Carmichael数必须既是“无平方数”(不能被任何素数的平方所整除),又是至少三个素数的积。(因此,Carmichael 数不是很常见。)

31.8-3  证明:如果x是以n为模的1的非平凡平方根,则gcd(x- 1, n)和gcd(x+1, n)都是n的非平凡约数。


相关内容

文章评论

表情

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