2
$\begingroup$

I'm looking for a way to find the factor of a natural number, call it $x$, which is closest to $\sqrt{x}$.

If this question needs to be clarified, just let me know and I'll be happy to add more.

  • 4
    If there were an efficient way of locating factors of $x$ near $\sqrt{x}$, then there would be an efficient way of performing Fermat factorization of $x$ for any $x$ that is not of the form $pq$ with $p$ and $q$ primes, and $p\ll q$. So I doubt that there is an efficient way of doing it.2011-03-01

1 Answers 1

3

The strength of the RSA cryptosystem hinges on the same question - more specifically, given $n=pq$ where $p,q$ are primes of the same relative magnitude, is it easy to find $p,q$? If so, you should stop putting your money in the bank.

The best known algorithm for factoring $n$ (NFS) takes time $\exp(O((\log n)^{1/3} (\log\log n)^{2/3}))$. This is much better than "trial division" (dividing by all numbers less than $\sqrt{n}$), which takes time $O(\sqrt{n}) = O(2^{(\log n)/2})$.

  • 0
    For those wondering (like me before I googled it), NFS stands for number field sieve. See http://en.wikipedia.org/wiki/Number_field_sieve2011-03-02