# How would I find the factor of $x$ nearest to $\sqrt{x}$?

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.

-
Find $\sqrt{x}$ and then find the factors of $x$ and compare them? –  PEV Mar 1 '11 at 16:21
Factors of $x$ always come in pairs whose product is $x$, and of each such pair, a) one is $\le\sqrt{x}$ and the other is $\ge\sqrt{x}$, and b) the lesser one is closer to $\sqrt{x}$ than the greater one. So you can restrict the search to factors $\le\sqrt{x}$. –  joriki Mar 1 '11 at 16:24
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. –  Arturo Magidin Mar 1 '11 at 16:31

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