Instead of iterating through all the possible numbers, is there a better way to find the greatest factor of a number $n$, such that it is less than $m$ ($m$ < $n$). Similarly how does one find the smallest factor of $n$ that is greater than $m$?
$\begingroup$
$\endgroup$
1
-
5$\begingroup$ This can be hard even if $n$ is squarefree with known but numerous prime factors, because it reduces to a knapsack problem (given items of size $c_i$, find $s$ large enough to approximate $\exp sc_i$ sufficiently well by primes $p_i$, and take $n = \prod_i \phantom. p_i$, etc.). $\endgroup$– Noam D. ElkiesCommented Oct 28, 2011 at 4:22
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
You can certainly use Pollard's Rho algorithm to probabalistically compute the greatest factor of $n$ smaller than $m$ in $O(min(n^\frac{1}{4}, m^\frac{1}{2}) polylog(n))$ time. Your other question is actually the same as the first. That is $k>m$ is a factor of $n$ iff $\frac{n}{k}$ is a factor of $n$ and smaller than $\frac{n}{m}$.
$\begingroup$
$\endgroup$
Here's a way to find small factors. I think that finding large factors (up to the square root of $n$) is as hard as factoring in general.
Edit: Maybe the method in the paper I linked is not so great because it looks for small factors in a set of number. But it may cite more relevant papers.
$\begingroup$
$\endgroup$
I think this may be an NP-hard problem similar to knapsack problem. It's straightforward to translate it into an instance of knapsack problem: let the knapsack size be $\log m$ and the items be $\log p_i$, where $p_i$ are prime factors of $n$. In order to prove NP-hardness one has to translate a general knapsack problem instance to this one though.
