请输入您要查询的字词:

 

单词 Pollardsrho
释义

Pollard’s ρ


Pollard’s ρ method is an algorithm for factoring numbers, better than trial and error for larger numbers.

Let n a non prime numberMathworldPlanetmath and d a non trivial factor. The actual value of the factors are unknown at this stage, and Pollard’s ρ provides a way to find them. We do know, however, than d is not larger than n. In fact, we know at least one of the factors must hold dn, so we assume this condition.

So, how does this help? If you start picking numbers at random(keeping your numbers greater or equal to zero and strictly lessthan n), then the only time you will get abmodn iswhen a and b are identical. However, since d is smaller thann, there is a good chance that abmodd sometimes whenab.

Well, if abmodd, that means that (a-b) is a multipleMathworldPlanetmath ofd. Since n is also a multiple of d, the greatest commondivisorMathworldPlanetmathPlanetmath of (a-b) and n is a positive, integer multiple of d.We can keep picking numbers randomly until the greatest commondivisor of n and the differencePlanetmathPlanetmath of two of our random numbers isgreater than one. Then, we can divide n by whatever this greatestcommon divisor turned out to be. In doing so, we have broken downn into two factors. If we suspect that the factors may becomposite, we can continue trying to break them down further bydoing the algorithm again on each half.

The amazing thing here is that through all of this, we just knewthere had to be some divisorMathworldPlanetmath of n. We were able to use propertiesof that divisor to our advantage before we even knew what thedivisor was!

This is at the heart of Pollard’s rho method. Pick a random numbera. Pick another random number b. See if the greatest commondivisor of (a-b) and n is greater than one. If not, pickanother random number c. Now, check the greatest common divisorof (c-b) and n. If that is not greater than one, check thegreatest common divisor of (c-a) and n. If that doesn’t work,pick another random number d. Check (d-c), (d-b), and (d-a).Continue in this way until you find a factor.

As you can see from the above paragraph, this could get quitecumbersome quite quickly. By the k-th iteration, you will haveto do (k-1) greatest common divisor checks. Fortunately, thereis way around that. By structuring the way in which you pick“random” numbers, you can avoid this buildup.

We use an appropiate polynomialPlanetmathPlanetmath f(x) to generate pseudorandom numbers. Because we’re only concerned with numbers fromzero up to (but not including) n, we will take all of the valuesof f(x) modulo n. We start with some x1. We then pick ournumbers by taking xk+1=(f(xk)modn).

Now, say for example we get to some point k where xkxjmodd with k<j. Then, because of the way that moduloarithmeticPlanetmathPlanetmath works, f(xk) will be congruentMathworldPlanetmath to f(xj) modulod. So, once we hit upon xk and xj, then each element inthe sequenceMathworldPlanetmathPlanetmath starting with xk will be congruent modulo d tothe corresponding element in the sequence starting at xj. Thus,once the sequence gets to xk it has looped back upon itself tomatch up with xj (when considering them modulo d).

This looping is what gives the ρ method its name. If you go backthrough (once you determine d) and look at the sequence of randomnumbers that you used (looking at them modulo d), you will seethat they start off just going along by themselves for a bit.Then, they start to come back upon themselves. They don’t typicallyloop the whole way back to the first number of your sequence. So,they have a bit of a tail and a loop—just like the Greek letterrho (ρ).

Before we see why that looping helps, we will first speak to whyit has to happen. When we consider a number modulo d, we areonly considering the numbers greater than or equal to zero andstrictly less than d. This is a very finite setMathworldPlanetmath of numbers.Your random sequence cannot possibly go on for more than d numberswithout having some number repeat modulo d. And, if the functionf(x) is well-chosen, you can probably loop back a great dealsooner.

The looping helps because it means that we can get away withoutaccumulating the number of greatest common divisor steps we needto perform with each new random number. In fact, it makes it sothat we only need to do one greatest common divisor check for everysecond random number that we pick.

Now, why is that? Let’s assume that the loop is of length t andstarts at the j-th random number. Say that we are on the k-thelement of our random sequence. Furthermore, say that k isgreater than or equal to j and t divides k. Because k isgreater than j we know it is inside the looping part of theρ. We also know that if t divides k, then t also divides2k. What this means is that x2k and xk will be congruentmodulo d because they correspond to the same point on the loop.Because they are congruent modulo d, their difference is a multipleof d. So, if we check the greatest common divisor of (xk-xk/2)with n every time we get to an even k, we will find some factorof n without having to do k-1 greatest common divisor calculationsevery time we come up with a new random number. Instead, we onlyhave to do one greatest common divisor calculation for every secondrandom number.

The only open question is what to use for a polynomialf(x) to get some random numbers which don’t have toomany choices modulo d. Since we don’t usually knowmuch about d, we really can’t tailor the polynomialtoo much. A typical choice of polynomial is

f(x)=x2+a

where a issome constant which isn’t congruent to 0 or -2modulo n. If you don’t place those restrictionsPlanetmathPlanetmath ona, then you will end up degenerating into the sequence{1,1,1,1,} as soon as you hit upon some xwhich is congruent to either 1 or -1 modulon.

Let’s use the algorithm now to factor our number 16843009. Wewill use the sequence x1=1 with xn+1=(1024xn2+32767modn). [ I also tried it with the very basic polynomial f(x)=x2+1, but that one went 80 rounds before stopping so I didn’tinclude the table here.]

and so we have discovered the factor 257.

Let’s try to factor again with a different random number schema.We will use the sequence x1=1 with xn+1=(2048xn2+32767modn).

Again, the factor 257 shows up.

Pollard’s ρ can also be applied to other finite groups besides integers, providing one of the best known methods to computing discrete logarithmsMathworldPlanetmath on arbitrary groups.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 3:46:40