大数据

当前位置:首页 > 大数据

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

*31.9 整数的因子分解

假设希望将一个整数n进行因子分解,也就是分解为素数的积。通过上一节所讨论的素数测试,可以知道n是否是合数,但它并不能指出n的素数因子。对一个大整数n进行因子分解,似乎要比仅确定n是素数还是合数困难得多。即使用当今的超级计算机和现行的最佳算法,要对任意一个1024位的数进行因子分解也还是不可行的。

Pollard的rho启发式方法

对小于R的所有整数进行试除,保证完全获得小于R2的任意数的因子分解。下列过程用相同的工作量,就能对小于R4的任意数进行因子分解(除非运气不佳)。由于该过程仅仅是一种启发性方法,因此既不能保证其运行时间也不能保证其运行成功,尽管该过程在实际应用中非常有效。POLLARD-RHO过程的另一个优点是,它只使用固定量的存储空间。(如果愿意,可以很容易地在一个可编程的掌上计算器上实现POLLARD-RHO,来找出小数的因子。) 

QQ截图20220628100113.jpg

QQ截图20220628100126.jpg

其执行过程如下。第1~2行把i初始化为1,把x1初始化为Zn中一个随机选取的值。第5行开始的while循环将一直进行迭代,来搜索n的因子。在while循环的每一次迭代中,第7行运用递归式

QQ截图20220628100712.jpg

计算无穷序列

QQ截图20220628100746.jpg

中xi的下一个值,其中i的值在第6行中进行相应的增加。为了清楚,伪代码中使用了下标变量xi,但即使去掉所有的下标,程序也以同样的方式执行,因为仅需要保留最近计算出的xi值。经过这个修改,此过程只使用了一个常量的存储空间。

程序不时地把最近计算出的xi的值存入变量y中。具体来说,存储的值是那些下标为2的幂的变量:

QQ截图20220628100939.jpg

第3行保存值x1,每当i=k时,第12行就保存值xk。第4行将变量k初始化为2,并且每当第12行更新y,第13行就将k的值加倍。因此,k值的序列为1, 2,4,8,...,并且总是给出要存入y的下一个值的xi的下标。

第8~10行尝试用存入y的值和xi的当前值找出n的一个因子。特别地,第8行计算出最大公约数d= gcd(y- xi,n)。如果第9行中发现了d是n的非平凡约数,则第10行输出d的值。

最初,这一寻找因子分解的过程似乎有点神秘。但是注意,POLLARD-RHO 绝不会输出错误的答案;它输出的任何数都是n的非平凡约数。尽管POLLARD-RHO可能不输出任何信息,也没有保证它能输出约数。不过,我们将看到,我们有充分的理由预计,POLLARD-RHO在while循环大约执行Θ(√p)次迭代后,会输出一个n的因子p。因此,如果p是合数,则在大约经过n1/4次的更新后,可以预计该过程已经找到足够多的约数,这是由于除了可能有的最大的一个素因子外,n的每一个素因子p均小于√n。

分析一下要经过多久,模n的随机序列中才会重复出现一个值,就可以了解这个过程的性能。由于Zn是有限的,并且序列(31.44)中的每一个值仅仅取决于前一个值,所以序列(31. 44)最终将产生自身重复。一旦运算到达一个xi,使得对某个j<i有xi=xj,则我们处在一个回路中,因为xi+1=xj+1,xi+2=xj+2, 等等。该过程取名为“rho启发式方法”的原因就在于(如图31-7所示)序列x1,x2,...,xj-1可以画成rho(ρ)的“尾”,而回路xj,xj+1, ...,xi可以画成rho的“体”。

下面考虑一个问题:xi的序列发生重复需要多久?实际上,这个问题的答案并不是我们恰好需要的,但我们将会看到如何修改这个论点。为了进行估算,假定函数

QQ截图20220628101832.jpg

像一个“随机”函数那样进行计算。当然,它并不是一个真正的随机函数,但由这个假设所得的结论,与我们对POLLARD-RHO行为的观察是一致的。因而,可以把每个xi视为按在Zn上均匀分布的方式从Zn中独立选取的。根据5.4.1节中对生日悖论的分析,在序列出现回路之前预计要执行的步数为Θ(√n)。

QQ截图20220628102035.jpg

图31-7 Pollard的rho启发式方法。(a) 由递归式xi+1=(xi2 - 1) mod 1387所产生的值,从x1=2开始。1387的素数因子分解是19·73。粗箭头指出在因子19被发现之前所执行的迭代步骤。细箭头指出在迭代中未到达的值,来画出“rho”的形状,阴影数值是由POLLARD-RHO保存的y的值。因子19是在到达x7=177时被发现的,此时计算gcd(63- 177,1387)=19。 第一个要重复的x数值是1186,但是因子19是在这个数值重复之前被发现的。(b) 相同递归式产生的值,

模19。(a)给出的每个值xi对模19来说等于这里显示的xi'。例如,x4=63和x7=177都等于6,模19。(c)相同递归式产生的值,模73。(a)给出的每个值xi,对模73来说等于这里显示的xi''。由中国余数定理,(a)中 每个结点对应于一对结点,即(b)中和(c)中的一个

现在根据要求进行适当修改。令p是满足gcd(p, n/p)=1 的n的一个非平凡因子。例如,如果n的因子分解为n=p1e1p2e2...prer,则可以取p的值为p1e1。(如果e1=1,则p就是n的最小素数因子,这是一个可以牢记的好例子。)

序列<xi>包含一个相应的对模p的序列<xi'>,其中对所有i,有

QQ截图20220628102809.jpg

更进一步,因为fn是仅使用算术操作(平方和减法)对模n定义的,所以将看到可以用xi'来计算xi'+1;序列从模p的角度看是从模n的角度看的一个较小版本:

QQ截图20220628103014.jpg

因此,虽然没有显式地计算序列<xi'>,但这个序列是良定义的,而且与序列<xi>有相同的递归式。

像之前一样进行推论,可以发现在序列<xi'>重复出现之前,预计执行的步数是Θ(√p)。如果和n相比,p是一个小数,则序列<xi'>的重复可能比序列<xi>的重复要快得多。事实上,只要序列<xi>中的两个元素仅对模p等价,而不对模n等价,序列<xi'>就发生重复。图31-7(b)和(c)说明了这一点。

令t表示<xi'>序列中第一个重复出现的值的下标,并且u>0表示这样产生的循环回路的长度。也就是说,t和u>0是对所有i≥0,满足条件x't+i=x't+u+i的最小值。根据上面的论证,t和u的期望值都是Θ(√p)。注意,如果x't+i=x't+u+i,则p|(xt+u+i一xt+i)。 因此,

QQ截图20220628103626.jpg

因此,只要POLLARD-RHO把使得k≥t的任何值xk存入变量y,则y mod p总在对模力的回路中(如果把一个新值存为y,则该值也在对模p的回路中。)最终,k将被赋予一个大于u的值,然后过程就在不改变y值的情况下,沿着模为p的回路完成整个一次循环。当xi“遇到”之前存储的对模p的y值时,即xi=y(mod p)时,就发现了n的一个因子。

假定发现的因子是因子p,但偶尔也可能是p的倍数。由于t和u的期望值都是Θ(√p),所以产生因子p所要求的期望执行步数为Θ(√p)。

该算法不会如期执行,原因有两条。第一,对于运行时间的启发式分析并不严格,对模p的值的回路有可能要比√p大得多。在这种情况下,虽然算法的执行正确,但其执行速度要比期望低得多。在实际应用中,这似乎还可以讨论。第二,这一算法得出n的约数可能总是平凡因子1或n。例如,假设n=pq,这里p和q为素数。可能会发生如下情况:关于p的t和u的值与关于q的t和u的值相等,所以因子p和因子q总是在相同的gcd运算中被呈现。由于两个因子同时被呈现,因此也就呈现出无用的平凡因子pq=n。这在实际应用中似乎没意义。如果需要,可以用一个不同形式的递归式xi+1 =(xi2 -c) mod n来重新开始运行该启发式过程。(值c=0和c=2应该被避免,其原因这里不作说明,但对其他值没有问题。)

当然,上述分析过程是启发式的,而不是严格的,因为递归式并不真是“随机的”。然而,这个过程可以在实际应用中良好地运行,并且似乎和我们在上面的启发式分析中所说明的一样有效。它是一种找出大整数的小素数因子的可供选择的方法。为了对一个β位合数n完全分解因子,仅需找出所有小于[n1/2] 的素数因子就可以了,因此,可以期望POLLARD-RHO需执行的算术运算至多为n1/4=2β/4次,位操作至多为n1/4β2= 2β/4β2。POLLARD-RHO最具吸引力的特点就是它可以在期望的Θ(√p)次算术运算内,找出n的一个小因子p。


练习

31.9-1  在图 31-7(a)所示的执行过程中,过程POLLARD-RHO在何时输出1387的因子73?

31.9-2  假设给定函数 f:Zn→Zn和一个初值x0∈Zn。定义xi=f(xi-1),i=1,2,...。令t和u>0是满足xt+i=xt+u+i(i=0,1, ...)的最小值。在Pollard的rho算法的术语中,t为rho的尾的长度,u是rho的回路的长度。试写出一个计算t和u的值的有效算法,并分析其运行时间。

31.9-3  为了发现形如pe的数(其中p是素数,e>1)的一个因子,POLLARD-RHO要执行多少步?

31.9-4  POLLARD-RHO的缺点之一是,在其递归过程的每一步,都要计算一个gcd。然而,可以对gcd的计算进行批处理:通过累计一行中数个连续的xi的积,然后在gcd计算中使用该积而不是xi。请详细描述如何实现这一思想,为什么它是可行的,以及在处理一个β位数n时,所选取的最有效的批处理规模是多大?


思考题

33-1   (二进制的 gcd算法)与计算余数的执行速度相比,大多数计算机执行减法运算、测试一个二进制整数的奇偶性运算以及折半运算的执行速度都要更快些。本题所讨论的二进制gcd算法中避免了欧几里得算法中对余数的计算过程。

  1. 证明:如果a和b都是偶数,则gcd(a, b)=2·gcd(a/2, b/2)。

  2. 证明:如果a是奇数,b是偶数,则gcd(a, b)= gcd(a, b/2)。

  3. 证明:如果a和b都是奇数,则gcd(a, b)=gcd((a-b)/2, b)。

  4. 设计一个有效的二进制gcd算法,输入整数为a和b(a≥b),并且算法的运行时间为O(lg a)。假定每个减法运算、测试奇偶性运算以及折半运算都能在单位时间内执行。

31-2   (对欧几里得算法中位操作的分析)

  1. 考虑用普通的“纸和笔”算法来实现长除法的运算:用a除以b,得到商q和余数r。证明:这种算法需要执行0((1+lg q)lg b)次位操作。

  2. 定义μ(a, b)=(1+lg a)(1+lg b)。 证明:过程EUCLID在把计算gcd(a, b)的问题转化为计算gcd(b, a mod b)的问题时,所执行的位操作次数至多为c(μ(a, b) 一μ(b, a mod b)),其中c>0为某一个足够大的常数。

  3. 证明:EUCLID(a, b)通常需要执行O(μ(a, b))次位操作;当其输入为两个β位数时,需要执行的位操作次数为O(β2)。

31-3   (关于斐波那契数的三个算法)在已知 n的情况下,本题对计算第n个斐波那契数F,的三种算法的效率进行了比较。

假定两个数的加法、减法和乘法的代价都是O(1),与数的大小无关。

  1. 证明:基于递归式(3. 22)计算Fn的直接递归方法的运行时间为n的幂。(例如,27.1节的FIB程序。)

  2. 试说明如何运用记忆法在O(n)的时间内计算Fn

  3. 试说明如何仅用整数加法和乘法运算,就可以在O(lg n)的时间内计算Fn。(提示:考虑矩阵QQ截图20220628105747.jpg和它的幂。)

  4. 现在假设对两个β位数相加需要Θ(β)时间,对两个β位数相乘需要Θ2)时间。如果这样更合理地估计基本算术运算的代价,这三种方法的运行时间又是多少?

31-4   (二次余数) 设 p是一个奇素数。如果关于未知量x的方程x2=a(mod p)有解,则数a∈Zp*就是一个二次余数。

a.证明:对模p,恰有(p-1)/2个二次余数。

b.如果p是素数,对a∈Zp*,定义勒让德符号QQ截图20220628110145.jpg若a是对模p的二次余数,则它等于1;否则它等于-1。证明:如果a∈Zp*,则

QQ截图20220628110248.jpg

给出一个有效的算法,使其能确定一个给定的数a是否是对模p的二次余数。分析所给算法的效率。

c.证明:如果p是形如4k+3的素数,且a是Zp*中一个二次余数,则ak+1 mod p是对模p的a的平方根。找出一个以p为模的二次余数a的平方根需要多长时间?

d.试描述一个有效的随机算法,找出一个以任意素数p为模的非二次余数,也就是指Zp*中不是二次余数的成员。所给出的算法平均需要执行多少次算术运算?

相关内容

文章评论

表情

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