**Factoring Algorithm Based on Parameterized Newton Method**

*Zhengjun Cao and Lihua Liu*

**Abstract: **Given a non-square n=pq, since p, q are two roots of x^2-\theta x+n=0, where \theta=p+q is unknown, one can pick the initial values l, r and use Newton method to construct A(\theta, l, k), B(\theta, r, k) approximating to p, q, respectively, where k is the iteration depth. Solve A(\theta, l, k)B(\theta, r, k)=n && \theta>2\sqrt{n} && l< A(\theta, l, k)<\sqrt{n}< B(\theta, r, k)<r
to obtain the approximations of \theta. Accumulate and sort the approximations for different initial values. Then pivot these approximations to search for the target \theta such that \theta^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^9n).

**Category / Keywords: **foundations / Factorization; Parameterized Newton method

**Date: **received 20 Sep 2020

**Contact author: **caozhj at shu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20200921:082753 (All versions of this report)

**Short URL: **ia.cr/2020/1142

[ Cryptology ePrint archive ]