A New Special-Purpose Factorization Algorithm

A new factorization algorithm is presented, which finds a prime factor p of an integer n in time (D log n)O(1), if 4p − 1 = Db2 where D and b are integers.