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