Factoring Algorithm Based on Parameterized Newton Method
Given a non-square n = p q, since p, q are two roots of x2−θx+n = 0, where θ = p + q is unknown, one can pick the initial values l, r and use Newton method to construct A(θ, l, k), B(θ, r, k) approximating to p, q, respectively, where k is the iteration depth. Solve A(θ, l, k)B(θ, r, k) = n ∧ θ > 2 √ n ∧ l < A(θ, l, k) < √ n < B(θ, r, k) < r to obtain the approximations of θ. Accumulate and sort the approximations for different initial values. Then pivot these approximations to search for the target θ such that θ2 − 4n is a square. The success probability of this algorithm depends on the choice of initial values, the iteration depth, and the search scope around the pivots. The algorithm can be easily parallelized, and its complexity can be restricted to O(log n).