Algorithm to find $ab = N$ with $a$ and $b$ as close as possible

Question

Given a number $N$ I would like to factor it as $N=ab$ where $a$ and $b$ are as close as possible; say when $|b-a|$ is minimal. For certain $N$ this is trivial: when $N$ is prime, a product of two primes, a perfect square, or one less than a perfect square, for example.

But in general it seems tricky. A lot of obvious first steps don't work. For example, it is tempting to guess that when $N=k^2M$, we can find $a_M\cdot b_M = M$, and the optimal solution for $N$ will be $ka_M\cdot kb_M$. But this is quite wrong; a counterexample is $N=20$. Are there any divide-and-conquer tactics of this sort that do work?

An obvious algorithm to find the optimal $a$ and $b$ might begin by calculating $s=\left\lfloor\sqrt N\right\rfloor$, which can be done efficiently, and then by working its way down from $s$ looking for a factor of $N$ by trial division, which is slow. Is there a more efficient algorithm?

It seems to me that even if the complete factorization of $N$ is known, partitioning the factors into two sets whose products are as close as possible will be NP-complete; it looks similar to the subset-sum problem, for example.

Answer 1

You are right it is the knapsack problem. If you factor $N=\prod_i p_i^{a_i}$ and take the log, you get $\log N = \sum_i a_i \log p_i$. Now you are looking to fill a knapsack of size $\frac 12 \log N$ as full as possible with things of size $\log p_i$ (and a limit of the quantity of each) without going over.

Answer 2

This is a hard problem in general since factoring is already a hard problem. Though perhaps you are assuming that $N$'s factorization is already known? It seems not, since you give an algorithm that does not use its factorization.

Given $N=p_1^{a_1}p_2^{a^2}\cdots p_k^{a^k}$ where the $p_i$ are prime, you want to partition this multiset into multisets $S$ and $T$ such that their respective products are as close as possible. I'm going to guess this is NP-Hard since it's pretty similar to the knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem)

Answer 3

There are some modest improvements one can make over trial division, at least when $N$ is odd. Certainly not enough to make this competitive with modern factoring methods and knapsack algorithms in most cases, but still better than trial division.

See the sections "Fermat's and trial division" and "Sieve improvement" in the Wikipedia article on Fermat factorization; in the case of odd $N$, $N = ab$ with $a$ and $b$ close together is equivalent to $N=A^2 -B^2$ with $B$ as small as possible.