Williams's p + 1 algorithm
In computational number theory, Williams's p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic-group factorisation algorithms.  It was invented by Hugh C. Williams in 1982. 

It works well if the number N to be factored contains one or more prime factors p such that p + 1 is smooth, i.e. p + 1 contains only small factors. It uses Lucas sequences to perform exponentiation in a quadratic field.

It is analogous to Pollard's p − 1 algorithm.

Algorithm
Choose some integer A greater than 2 which characterizes the Lucas sequence:

where all operations are performed modulo N.

Then any odd prime p divides  whenever M is a multiple of , where 
 and 
 is the Jacobi symbol.

We require that , that is, D should be a quadratic non-residue modulo p.  But as we don't know p beforehand, more than one value of A may be required before finding a solution.  If , this algorithm degenerates into a slow version of Pollard's p − 1 algorithm.

So, for different values of M we calculate , and when the result is not equal to 1 or to N, we have found a non-trivial factor of N.

The values of M used are successive factorials, and  is the M-th value of the sequence characterized by .

To find the M-th element V of the sequence characterized by B, we proceed in a manner similar to left-to-right exponentiation:
 x := B           
 y := (B ^ 2 − 2) mod N     
 for each bit of M to the right of the most significant bit do
     if the bit is 1 then
         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

Example
With N=112729 and A=5, successive values of  are:

 V1 of seq(5) = V1! of seq(5) = 5

 V2 of seq(5) = V2! of seq(5) = 23

 V3 of seq(23) = V3! of seq(5) = 12098

 V4 of seq(12098) = V4! of seq(5) = 87680

 V5 of seq(87680) = V5! of seq(5) = 53242

 V6 of seq(53242) = V6! of seq(5) = 27666

 V7 of seq(27666) = V7! of seq(5) = 110229.

At this point, gcd(110229-2,112729) = 139, so 139 is a non-trivial factor of 112729. Notice that p+1 = 140 = 22 × 5 × 7. The number 7! is the lowest factorial which is multiple of 140, so the proper factor 139 is found in this step.

Using another initial value, say A = 9, we get:

 V1 of seq(9) = V1! of seq(9) = 9

 V2 of seq(9) = V2! of seq(9) = 79

 V3 of seq(79) = V3! of seq(9) = 41886

 V4 of seq(41886) = V4! of seq(9) = 79378

 V5 of seq(79378) = V5! of seq(9) = 1934

 V6 of seq(1934) = V6! of seq(9) = 10582

 V7 of seq(10582) = V7! of seq(9) = 84241

 V8 of seq(84241) = V8! of seq(9) = 93973

 V9 of seq(93973) = V9! of seq(9) = 91645.

At this point gcd(91645-2,112729) = 811, so 811 is a non-trivial factor of 112729. Notice that p−1 = 810 = 2 × 5 × 34. The number 9! is the lowest factorial which is multiple of 810, so the proper factor 811 is found in this step. The factor 139 is not found this time because p−1 = 138 = 2 × 3 × 23 which is not a divisor of 9!

As can be seen in these examples we do not know in advance whether the prime that will be found has a smooth p+1 or p−1.

Generalization
Based on Pollard's p − 1 and Williams's p+1 factoring algorithms, Eric Bach and Jeffrey Shallit developed techniques to factor n efficiently provided that it has a prime factor p such that any kth cyclotomic polynomial Φk(p) is smooth.
The first few cyclotomic polynomials are given by the sequence Φ1(p) = p−1, Φ2(p) = p+1, Φ3(p) = p2+p+1, and Φ4(p) = p2+1.

References

External links
 P + 1 factorization method at Prime Wiki

Integer factorization algorithms