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.

$\endgroup$
  • 1
    $\begingroup$ Find $\sqrt{x}$ and then find the factors of $x$ and compare them? $\endgroup$ – PrimeNumber Mar 1 '11 at 16:21
  • 1
    $\begingroup$ 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}$. $\endgroup$ – joriki Mar 1 '11 at 16:24
  • 4
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Mar 1 '11 at 16:31
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.