整数分解算法外文翻译资料

 2021-12-23 10:12

英语原文共 19 页

  • 整数分解算法

康纳利·巴恩斯 俄勒冈州立大学物理系

2004年12月7日

内容

一、介绍

1.术语

2.算术基本定理

3.实际的动机

二、算法

1.算法:试除法

2.伪代码:试用版

3.算法:费马因子分解

4.伪代码:费马因子分解

5.算法:波拉德 rho分解

6.伪代码:波拉德 rho 分解

7.算法:布伦特分解法

8.伪代码:布伦特因子分解方法

9.算法:Pollard p-1因式分解

10.伪代码:Pollard p-1分解

三、时间复杂度

  1. 时间复杂度:试运行
  2. 时间复杂度:费马分解
  3. 时间复杂度:实证结果

四、算法的失败概率

五、结论

附录A. Maple仿真源代码

附录b .引用

一.介绍

本文简要介绍了整数因子分解算法。我们为大整数的因式分解提供了几种动机。然后解释了许多分解算法，并给出了每种算法的伪代码。对总是成功的算法，给出了运行时间的界，对概率算法给出了失败情况。最后，绘制了所有算法的运行时间，并进行了比较。

  1. 术语

大O符号：

函数f(x)等于O（g(x)）当x-gt;infin;时当且仅有正的实常数c,k使对于每个xgt;k,都有0le;f(n)le;c*g(n).例如：当x-gt;infin;，在c=3，k=0的条件下f(x)=2xsup2; x 1的时间复杂度为O(xsup2;).

当大O符号应用于一个算法的运行时间和存储需求,你可以写简单的O(g(x)),并假设x - gt;infin;。如果存在多个变量，则表示趋于无穷。考虑到O(g(x))的定义部分, 当x - gt;infin;时、算法必须考虑所有可能的执行情况。

平凡的因子:

一个正整数N其平凡因子为s = 1或s = N。

非平凡的因子:

一个正整数N其非平凡的因子1lt;slt;N。

质数:一个大于1的正整数，除1和它自身外，不能被任何正整数整除。

2. 算术基本定理

算术基本定理指出，当乘积中的素数以非递减顺序表示时，每个正整数都可以唯一地写成素数的乘积。

3.实际的动机

算术基本定理意味着任何组合整数都可以被分解。鉴于数量N = 21,容易找到N的因素:21=7·3。现在考虑一个更大的合数:

N=25195908475657893494027183240048398571429282126204 03202777713783604366202070759555626401852588078440 69182906412495150821892985591491761845028084891200 72844992687392807287776735971418347270261896375014 97182469116507761337985909570009733045974880842840 17974291006424586918171951187461215151726546322822 16869987549182422433637259085141865462043576798423 38718477444792073993423658482382428119816381501067 48104516603773060562016196762561338441436038339044 14952634432190114657544454178424020924616515723350 77870774981712577246796292638635637328991215483143 81678998850404453640235273819513786365643912120103 97122822120720357.

这个整数称为RSA-2048。1991年3月，RSA实验室宣布了一项20万美元的奖金，奖励成功分解这个数字。截至2004年11月，这个数字还没有被分解为[1]。如果一个有两个大质数，有快速的算法把它们相乘。然而，如果已知两个大素数的乘积，则很难找到素数因子。已知的最快的通用分解算法是通用数字字段筛选算法(General Number Field Sieve, GNFS)，在渐进表示法中，它采取步骤分解一个有n位小数的整数。

算法的运行时间以n的多项式函数为界，以n[2]的指数函数为界。分解大整数的明显困难是一些现代密码算法的基础。RSA加密算法[3]和Blum Blum Shub加密伪随机数生成器[4]都依赖于分解大整数的难度。如果能够快速分解大素数的乘积，这些算法将是不安全的。在万维网上用于TCP/IP连接的SSL加密依赖于RSA算法[5]的安全性。因此，如果可以快速分解大整数，“安全的”Internet站点将不再安全。最后,在计算复杂性理论,未知是否保理是复杂性类P技术而言,这意味着没有已知的算法回答这个问题“整数N有因子小于整数年代?”在许多步骤))((N阿宝,在N,其中N是数字的位数和P (N)是一个多项式函数。此外，还没有人证明这种算法存在或不存在。用外行的话来说，我们可以简单地问这样一个问题:“分解大数的最快算法是什么?”这是数学[6]中一个重要的开放性问题.

二.算法

1. 算法:试除法

试除法是分解整数最简单的算法。假设s和t是N的重要因子,所以st=N并且sle;t。执行试除法算法,只是检查是否一个S是否能被N整除s = 2,hellip;, lfloor;radic;nrfloor;。当找到这样一个因子s, t = N / s也是一个因子，上界 sle;lfloor;radic;nrfloor;是由以下定理决定的:

定理：如果N有重要的因数s,t、有st=N、sle;t, 则sle;radic;n。证明.
假设s gt; N,tge;s大于radic;N,并且stgt; N,这与假设st= N相悖，所以 sle;radic;N。

2．伪代码: 试除法

function trialDivision(N)

for s from 2 to floor(sqrt(N))

if s divides N then

return s, N/s

end if

end for end function

如果这个算法给定复数N，那么它返回一对非平凡因子s, t并且sle;t。声明s|N相当于sequiv;0(mod N),因此它可以在大多数语言中通过模运算实现。

3.算法:费马分解

这个算法是数学家皮埃尔·德·费马在17世纪发现的。Fermat因子分解将合数N改写为平方和差:

N = xsup2;- ysup2;

这个平方的差值直接推导出N的因式分解:

N =(x y)(x - y)

假设s和t是N重要的奇因数，且st = N,、sle;t。我们可以发现x和y, s = (x-y)和t = (x y)。解这个方程,我们发现x = (s t) / 2, y = (t - s) / 2。这里x和y是整数，因为任意两个奇数的差都是偶数，而偶数能被2整除。在sgt;1和tge;s的条件发,我们发现xge;1,yge;0。为特定的x, y满足s = (x,-y)和t = (x y),因此我们i道,x =radic;N ysup2;,因此xge;radic;N。另外,Xle;(s t)/ 2le;2 t / 2le;N。对于一个算法,我们选择x1=lceil;radic;Nrceil;,并且xi 1=xi 1。对于每一个i,我们检查是否yt=radic;xisup2;-N是一个整数,是否 (xi yi)(xi-yi)是重要的因素,如果这两个条件,我们返回的重要因素。否则，我们继续到下一个i，一旦xi= N则退出。

  • 4. 伪代码:费马分解

function fermatFactor(N)

for x from ceil(sqrt(N)) to N

ySquared := x * x - N

if isSquare(ySquared) then

y := sqrt(ySquared)

s := (x - y)

t := (x y)

if s lt;gt; 1 and s lt;gt; N then

return s, t

end if

end if

end for end function

如果z是一个平方数，则isSquare(z)函数为真，否则为假。构造isSquare函数很简单，方法是取平方根，将答案四舍五入到整数，对结果求平方，并检查是否再现了原始数字

5. 算法:波拉德分解

波拉德的rho方法是一种通过迭代多项式模N分解合数N的概率方法。该方法由J.M.波拉德于1975年发表。假设我们构造序列:

X0=2（mod N）

Xn 1equiv;xn2 1(mod N)

这个序列最终会变成周期性的。可以通过反证法证明循环的长度小于或等于N:假设周期的长度大于N,然而我们只有xn值的周期长度Lgt;N,所以必须存在两个全等xn值,这些可以确定为“起点”的周期长度小于或等于N .概率参数表明,预计这个时间序列(mod N)落入一个循环周期的长度和预期都是ꇌN成正比,几乎所有N [8]。其他初值和迭代函数在迭代过程中通常具有类似的行为，但是函数f(n)=xn2 1在实际分解中被发现效果良好。假定 s和t是N的非平凡因子st=N且sle;t，在假设我们已经发现非负整数i,j、xiequiv;xj(mod s)但xi与xj除以N的余数不相等。因为s|(xi-xj)且s|N，所以我们推导出s|gcd(xi-xj,N)。假设sge;2,因此gcd(xi-xj,N)ge;2.通过定义我们知道gcd(xi-xj,N)|N。然而,我们有N| gcd(xi-xj)则N| gcd(xi-xj,N).所以我们推导出N| gcd(xi-xj，N)， gcd(xi-xj，N)gt;1、且gcd(xi-xj，N)|N。因此gcd(xi-xj，N) 是N的一个非平凡因子。

现在我们必须找到这样的i,j、xiequiv;xj(mod s)和xi与xj除以N的余数不相等。观察序列Xn(mod s)的周期与ꇌs周期的长度成正比。Pollard建议Xn对于n = 1, 2, 3，hellip;与X2n相比较。对于每个n,我们检查是否gcd(xn-x2n,N)是N的一个非平凡因子。如果gcd(xn-x2n,N)是n的一个平凡因子,我们重复的迭代过程,直到找到一个因素。如果没有找到因子，则该算法不会终止。

6. 伪代码:波拉德分解

function pollardRho(N)

# Initial values x(i) and x(2*i) for i = 0.

xi := 2

x2i := 2

do

# Find x(i 1) and x(2*(i 1))

xiPrime := xi ^ 2

资料编号：[3812]

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章