P Plus 1 Factorization Method

From Mersennewiki

The title of this page is incorrect due to software limitations. The proper title should be p+1 factorization method.

The p+1 method of factoring integers was discovered by Hugh Williams in 1982 and it is based in the p-1 method.

Instead of using multiplications modulo p, this method uses Lucas sequences. They have very interesting properties that make them useful in the Lucas-Lehmer Test.

Let's define the following Lucas sequence:

\large U_0 = 0\,,\, U_1 = 1\,,\, V_0 = 2\,,\, V_1 = u

\large U_n = uU_{n-1} - U_{n-2}\,,\, V_n = uV_{n-1} - V_{n-2} for n\geq 2

where we can choose freely the integer u.

If we define D = u^2 - 4, then for any odd prime p, p divides both gcd(N, U_M) and gcd(N, V_M - 2) whenever M is a multiple of p - (D/p) where (D/p) is the Legendre symbol, which is equal to 1 if D is a quadratic residue mod p and -1 otherwise (we suppose that D is not multiple of p).

Since we do not know in advance the value of the Legendre symbol (because in order to compute it we need the prime factor p of N which is not known), it is possible that (D/p) = 1 making this method a slow variant of p-1. So when the gcd does not reveal the prime factor of N we retry with a different value of u at least three times in order to have a high probability of selecting (D/p) = -1.

From the formulas above, the values Un are not needed to compute the value of Vn, so they are not used in this algorithm.

Step 1

The step 1 work in the same way as explained in the p-1 article except that instead of computing an (mod N) we compute Vn (mod N) and instead of computing gcd(an - 1, N) we compute gcd(Vn - 2, N).

The main computation in step 1 is to find Vmn from Vn (index multiplication). In order to compute the Lucas sequence for high values of the index, the formulas given at the beginning of this article are not useful. Instead, we will use the two formulas shown below:

\large V_{2n} = V_n^2 - 2 (duplication formula)

\large V_{m+n} = V_m V_n - V_{m-n} (addition formula)

In order to perform index multiplication by a natural number M, there are two approaches using the formulas shown above.

Montgomery's PRAC is an almost optimal algorithm, but this is too complicated to explain it here.

Another algorithm is the same used in exponentiation. We represent the value M in binary form. Then erase the first "1" (all numbers when represented in binary start with the digit "1"). Then for every "1" write the string "DA" and for every "0" write "D".

For example for the number 21 which is 10101 when written in binary, you will have the string DDADDA. The letter D means duplication and A means addition.

So if we have to compute V_{21n} using the recipe above we will get the sequence: V_{2n}, V_{4n}, V_{5n}, V_{10n}, V_{20n}, V_{21n}.

A problem with this approach is that the formula for addition shown above for V_{q+r} needs the value of V_{q-r}. This can be overcomed by using another variable. When we compute V_{kn} we will be also computing V_{(k+1)n}.

Then if we start with the pair (V_{kn}, V_{(k+1)n}), when the bit equals zero we compute (V_{2kn}, V_{(2k+1)n}) and when the bit equals one we compute (V_{(2k+1)n}, V_{2(k+1)n}). In both cases we need one duplication and one addition requiring only two modular multiplications.

The index multiplication explained above can be translated to pseudocode as follows (let B = Vn):

 y=(B^2-2) mod N     
 for each bit of M to the right of the most significant bit
   if the bit is 1
     x=(x*y-B) mod N 
     y=(y^2-2) mod N 
     y=(x*y-B) mod N 
     x=(x^2-2) mod N 

The PRAC algorithm is 30% faster in average than the algorithm shown above to multiply a point by a natural number.

Step 2

The step 2 is useful when p+1 has a prime factor q between the bounds B1 and B2 and all the other prime factors less than B1.

Using the formula V_n = uV_{n-1} - V_{n-2} we find that exchanging V_n and V_{n+2} and adding two to n we get: V_n = uV_{n+1} - V_{n+2}. From this we get: V_{-1} = u = V_1 and then V_{-n} = V_n.

Let V_r be the number computed at the end of step 1. Now let C be the maximum multiple of 6 less than or equal to B1. The idea is to compute V_{Cr} and V_{6r}. Then using the addition formula we can compute V_{(C+6)r},\, V_{(C+12)r},\, V_{(C+18)r},\, ...,\, V_{B_2r}.

If q=C+1+6k the number computed will be equal to V_{-r} and if q=C-1+6k the number computed will be equal to V_r. Since V_r = V_{-r}, we just multiply all V_{(C+6k)r} - V_r\,\pmod N and then take the GCD of the product in order to reveal the factor.


Let's factor N = 451889 with u = 6 and B1 = 10. All congruences below will be modulo N.

As in the example of the p-1 factoring method we get:

E = 23 × 32 × 5 × 7

V1 = u = 6.

  • Duplicate index: 6^2 - 2\eq 34
  • Duplicate index: 34^2 - 2\eq 1154
  • Duplicate index: 1154^2 - 2\eq 427936
  • Multiply index by 3: 427936^2 - 2\eq 299066, so the first pair is (V_n , V_{2n})\eq (427936,\, 299066). The second pair is (V_{3n}, V_{4n})\eq (V_n * V_{2n} - V_n,\, V_{2n}^2 - 2)\eq (292372,\, 342029)
  • Multiply index by 3: 292372^2 - 2\eq 255586, so the first pair is (V_n , V_{2n})\eq (292372,\, 255586). The second pair is (V_{3n}, V_{4n})\eq (V_n * V_{2n} - V_n,\, V_{2n}^2 - 2)\eq (176913,\, 33332)
  • Multiply index by 5: 176913^2 - 2\eq 377427, so the first pair is (V_n , V_{2n})\eq (176913,\, 377427). The second pair is (V_{2n}, V_{3n})\eq (V_n^2 - 2,\, V_n * V_{2n} - V_n)\eq (377427,\, 447298). The third pair is (V_{5n}, V_{6n})\eq (V_{2n} * V_{3n} - V_n,\, V_{3n}^2 - 2)\eq (50045,\, 290385).
  • Multiply index by 7: 50045^2 - 2\eq 133185, so the first pair is (V_n , V_{2n})\eq (50045,\, 133185). The second pair is (V_{3n}, V_{4n})\eq (V_n * V_{2n} - V_n,\, V_{2n}^2 - 2)\eq (282419,\, 245306). The third pair is (V_{7n}, V_{8n})\eq (V_{3n} * V_{4n} - V_n,\, V_{4n}^2 - 2)\eq (374468,\, 138727).

So gcd(374468 - 2, 451889) = 139 which is a proper factor of the original number.

Notice that some values computed above are not really useful if you had to perform the computation by hand, for example the second element of the pair in the last step of the index multiplication. When using a computer, these additional multiplication can be avoided by using conditional sentences.

If instead of u=6 we would have selected u=7, the final gcd would have been: gcd(252303-2, 451889) = 1, so this particular value u=7 is not useful in the p+1 method.

Since u=7 does not factor 451889 in step 1, we have to continue with step 2. Let the upper bound B2 be 50. From the previous paragraph V_r \eq 252303.


C = 18

V_{18r} \eq 392380

V_{24r} \eq 224225

V_{6r} \eq 446313

Computing all other V_{6kr}:

V_{30r} = V_{24r} V_{6r} - V_{18r} \eq 157772

V_{36r} = V_{30r} V_{6r} - V_{24r} \eq 318875

V_{42r} = V_{36r} V_{6r} - V_{30r} \eq 430332

V_{48r} = V_{42r} V_{6r} - V_{36r} \eq 132372

(V_{18r} - V_r)(V_{24r} - V_r)...(V_{48r} - V_r) \eq 421170

\gcd(421170,\, 451889) = 139

Personal tools