Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Find $\sqrt{x}$ and then find the factors of $x$ and compare them? –  PEV Mar 1 '11 at 16:21
1  
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
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. –  Arturo Magidin Mar 1 '11 at 16:31

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
For those wondering (like me before I googled it), NFS stands for number field sieve. See en.wikipedia.org/wiki/Number_field_sieve –  admchrch Mar 2 '11 at 3:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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