Welcome to MathOverflow

Question

1

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$?

flag	asked Oct 27 2011 at 22:19 AG 11●1

4

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.). – Noam D. Elkies Oct 28 2011 at 4:22

msg555 · Answer 1 · 2011-12-23 03:34:13Z UTC

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}$.

psd · Answer 2 · 2011-10-27 22:57:07Z UTC

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.

Finding the greatest (smallest) factor of a number smaller (greater) than another number

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.