Newton-Raphson For Integer Factorization

Question

Per my earlier question on Naive Grouping for factorization here, below is the modified Newton-Raphson method (integers only) for the polynomial $N -x^2 - yx - x = 0$.

Newton <- function(f, x0=1,N=20) {
  i <- 1
  x1 <- x0

  while (i<=N) {
     df.dx <- (f(x0+1)-f(x0))
     x1<- as.integer(x0 - (f(x0)/df.dx))
     if(f(x1)==0) return(x1)
     if((x1)==(x0)) break 

     x0 <- x1

     }
}

And here is the routine for checking values of y for the root

NewtonFactor <- function(number){

  rr <- as.integer(sqrt(number))
  l <- as.integer(log2(number))

  i<- 1
  while(i<number){

    Seed_Group = i

    fun <- function (x) {number - x^2 -Seed_Group*x - x}

    root <- Newton(fun, x0 = rr, N=l)

    if(length(root)>0) return(c(Factor=c(root,number/root)))

    i=i+2L      }
} 

Using $\sqrt n$ as the initial guess $X_0$ instead of 1 yields considerable efficiency. I would like to know more about the actual steps vs. trial division for larger N, and if the need to check all y-coordinates nullifies any benefits. Furthermore, the y-coordinates are inversely related to distance of the factors. N=(101*103), y=1 N=(3*103), y=99

Also, if there is any related literature on hyperbola lattice points I'd appreciate suggestions to further reading.

Answer 1

If I understand correctly, you're looking for factorizations of $N$ of the form $N=x(x+y+1)$ and searching for values of $y$ that make this work. Note that you might as well set $z=y+1$ and search for factorizations of the form $N=x(x+z)$; this shouldn't have any impact on the algorithms, and it saves you a bit of trouble in evaluation.

In any case, you don't need to use N-R methods to solve this equation - you can just use the quadratic formula! Since you have $N=x(x+z)=x^2+zx$ or $x^2+zx-N=0$, you can solve to get $x=\frac12(-z\pm\sqrt{z^2+4N})$. You might think that taking the square root would be more painful than N-R, but note that if $x$ is to be an integer then $\sqrt{z^2+4N}$ must be too, and computing integer square roots can be done efficiently - a form of binary search is fast enough and yields $O(n)$ operations to compute the square root of a $n$-digit number (and confirm that that number is in fact a square).

Unfortunately, that won't end up helping you much here, because the difference between roots is actually going to be larger than the smallest prime factor of $N$ (i.e., the number of iterations needed for a semi-naive trial division algorithm) on average. For $N=pq$ the product of two prime numbers (which we may as well take as the canonical case here just for convenience of analysis), the smallest prime factor is always going to be $O(\sqrt{N})$ and it will 'usually' be $o(\sqrt{n})$ - for any given ratio $r$ you can show that the number of $N$ with $\frac qp\lt r$ (assuming of course that $q$ is the larger prime factor) — in other words, the number of $N$ where $q-p\in\Theta(p)$ — is vanishingly small asymptotically. Worse, your version of this method doesn't have any immediately obvious way of winnowing out $y$s (or equivalently $z$s) other than to assume that $p,q$ are odd and therefore $z$ is even. By contrast, trial division can 'sieve out' small primes so that the actual number of trial divisors is reduced by a fairly large constant amount.

Methods loosely similar to what you're suggesting have been used in the past, though: Fermat's factorization method works by writing $N=x^2-y^2=(x-y)(x+y)$ (in other words, as the product of two numbers with difference $2y$, symmetric) and then uses sieves of quadratic residues to eliminate many possible values of $x$ and $y$. Generalizations of this idea then start to lead to algorithms that actually are more efficient than trial division (e.g., the quadratic sieve); the Wikipedia link or vol. 2 of Knuth's Art of Computer Programming will have many more details if you're interested.