5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ By close, I assume $\vert b - a \vert$ is minimized? $\endgroup$
    – user17762
    Jan 19, 2013 at 3:47
  • $\begingroup$ I was not sure whether to minimize $|b-a|$ or $\left|\log \frac ba\right|$. But I think the same factorizations are optimal regardless of which metric one chooses. I have amended the question to commit to minimizing $|b-a|$. $\endgroup$
    – MJD
    Jan 19, 2013 at 3:49
  • $\begingroup$ Peripheral comment: I think I first began to consider this problem when I noticed that $7! = 70\cdot72$. $\endgroup$
    – MJD
    Jan 19, 2013 at 3:54
  • 1
    $\begingroup$ Varients of Fermat's factorization method would be more efficient then your algorithm $\endgroup$
    – Ethan Splaver
    Jan 19, 2013 at 3:54
  • 2
    $\begingroup$ Because of the monotonicity of the log function, minimizing $|b-a|$ or $|\log \frac ba| =| \log b - \log a| amount to the same thing. $\endgroup$
    – Ross Millikan
    Jan 19, 2013 at 3:57

3 Answers 3

Reset to default
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is plausible, but not sufficient to prove it's hard. Knapsack is hard when the sizes are arbitrary numbers, but here the possible sizes are numbers of the form $\log p_i$. When the set of possible sizes is constrained, knapsack may no longer be hard. (For example, when the possible sizes are constrained to be powers of $2$, knapsack is trivially solved in linear time.) $\endgroup$
    – MJD
    Jan 12, 2022 at 8:52
  • $\begingroup$ Dan Brumleve has pointed out that a reduction from Partition can be done in polynomial time, if Cramér's conjecture is correct. $\endgroup$
    – MJD
    Feb 7, 2022 at 18:43
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
5
  • 2
    $\begingroup$ Factoring isn't known to be hard. The hardness comes from the knapsack property. $\endgroup$
    – Josephine Moeller
    Jan 19, 2013 at 4:05
  • $\begingroup$ Factoring is thought to be hard. Knapsack is NP-Hard, and therefore thought to be hard. If $P = NP$ then all of these are poly-time solvable, but that's unlikely. The best known general factoring algorithms are super-polynomial (on a conventional computer; quantum algorithms are polynomial-time). $\endgroup$
    – Fixee
    Jan 19, 2013 at 4:19
  • 1
    $\begingroup$ Factoring is actually thought not to be NP-hard: en.wikipedia.org/wiki/… $\endgroup$
    – Josephine Moeller
    Jan 19, 2013 at 4:22
  • $\begingroup$ Correct, which is why I was careful to not claim that it was. If you know an efficient (meaning poly-time) factoring algorithm, please send me a private note and we'll write a paper. Or start a company. Or be captured/assassinated before we can do either... $\endgroup$
    – Fixee
    Jan 19, 2013 at 4:35
  • 3
    $\begingroup$ There's no need to be snide. My point here is that if you mention "hard" in the context of complexity it's good to be specific about what you mean and avoid the colloquial use of "hard" as something that's merely practically intractable. There are problems in $P$ that are practically "hard." $\endgroup$
    – Josephine Moeller
    Jan 19, 2013 at 4:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .