Williams' 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: :V_0=2, V_1=A, V_j=AV_-V_ where all operations are performed modulo ''N''. Then any odd prime ''p'' divides \gcd(N,V_M-2) whenever ''M'' is a multiple of p-(D/p), where D=A^2-4 and (D/p) is the Jacobi symbol. We require that (D/p)=-1, 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 ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]