A deterministic algorithm for integer factorization (Q2796032)

This paper proposes a new deterministic method for the factorization of an integer \(n\). It can be viewed as an improvement of the naive trial division method, since it can test the divisibility of \(n\) by all the integers in a short interval in basically one step. In fact the algorithm test the equation \(n/(x+h)\equiv 0 \bmod 1\), with \(h\in [-H,H]\).NEWLINENEWLINEThe Introduction gives a brief summary of the existing deterministic methods of factorization and Section 2 gives the proposed method (Algorithm 1) and its complexity (Theorem 2.1). As many other methods this complexity is \(n^{1/3+ o(1)}\). The author points out that this algorithm is mainly of theoretical interest. There are already probabilistic methods that far outperform it in practice and in ``heuristically subexponential time''.NEWLINENEWLINESection 3 is devoted to the proof of Theorem 2.1 and Section 4 shows an implementation of Algorithm 1 in \texttt{Mathematica} and discusses some computational issues.