# Find $y=\sqrt{x}$ where $x$ and $y$ positive integers in polynomial time?

Let $x$ be a positive integer and let $y$ be a real number such that $$y=\sqrt{x}$$

Objectives:

1. If $y$ is an integer, find it in polynomial time.

2. If $y$ is not an integer, prove that there is no integer solution in polynomial time.

Is there any algorithm which can do that?

• If you can find the integer square root in polynomial time, the you can prove the 2nd objective at the cost of 1 multiplication & 1 comparison: $\lfloor \sqrt{x} \rfloor^2 \stackrel{?}{=} x$. Check the book:$\$ A Course in Computational Algebraic Number Theory by H. Cohen. There might be an algorithm for computing the integer square root. – user2468 Sep 1 '12 at 16:13
• Apparently this post math.stackexchange.com/questions/34235/… – user2468 Sep 1 '12 at 16:14
• Don't you want polynomial in $\ln(x)$? – i. m. soloveichik Sep 1 '12 at 16:25

You could implement some sort of digit-by-digit algorithm. If $n=\log x$, this should involve $O(n)$ arithmetic operations, none of which involve numbers larger than $x$. So the time required will be no worse than $O(n^3)$ or thereabouts; certainly it'll be polynomial in $n$.
Simply testing if $x=k^2$ for $k=0, 1, \ldots$ until you hit or exceed $x$. has time $O(\sqrt x)$.
• ... and not forgetting that "polynomial" here should mean "polynomial evaluated at $\log x$" or "polynomial in the number of digits of $x$" – Jyrki Lahtonen Sep 1 '12 at 19:22