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