# 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:

for

where we can choose freely the integer .

If we define , then for any odd prime , divides both gcd(, ) and gcd(, ) whenever is a multiple of where is the Legendre symbol, which is equal to 1 if is a quadratic residue mod and -1 otherwise (we suppose that is not multiple of ).

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

From the formulas above, the values U_{n} are not needed to compute the value of V_{n}, 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 a^{n} (mod N) we compute V_{n} (mod N) and instead of computing gcd(a^{n} - 1, N) we compute gcd(V_{n} - 2, N).

The main computation in step 1 is to find V_{mn} from V_{n} (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:

(duplication formula)

(addition formula)

In order to perform index multiplication by a natural number , 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 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 using the recipe above we will get the sequence: , , , , , .

A problem with this approach is that the formula for addition shown above for needs the value of . This can be overcomed by using another variable. When we compute we will be also computing .

Then if we start with the pair (, ), when the bit equals zero we compute (, ) and when the bit equals one we compute (, ). 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 = V_{n}):

x=B 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 else y=(x*y-B) mod N x=(x^2-2) mod N V=x

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 between the bounds B_{1} and B_{2} and all the other prime factors less than B_{1}.

Using the formula we find that exchanging and and adding two to we get: . From this we get: and then .

Let be the number computed at the end of step 1. Now let be the maximum multiple of 6 less than or equal to B_{1}. The idea is to compute and . Then using the addition formula we can compute .

If the number computed will be equal to and if the number computed will be equal to . Since , we just multiply all and then take the GCD of the product in order to reveal the factor.

### Example

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 = 2^{3} × 3^{2} × 5 × 7

V_{1} = u = 6.

- Duplicate index:
- Duplicate index:
- Duplicate index:
- Multiply index by 3: , so the first pair is . The second pair is
- Multiply index by 3: , so the first pair is . The second pair is
- Multiply index by 5: , so the first pair is . The second pair is . The third pair is .
- Multiply index by 7: , so the first pair is . The second pair is . The third pair is .

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 B_{2} be 50. From the previous paragraph .

Initializing:

Computing all other :