Square root a number The task is as follows: Given a positive integer x and a prime n &gt; x, output the smallest positive integer y such that (y * y) mod n = x.  An  important part of this question is the time limit specified below which excludes brute force solutions.

If there is no such value y then your code should output N.

Test cases

(2, 5, N), 
(3, 5, N), 
(4, 5, 2),
(524291, 1048583, N),
(529533, 1048583, N),
(534775, 1048583, 436853),
(540017, 1048583, 73675),
(536870913, 1073741827, 375394238),
(542239622, 1073741827, 267746399),
(547608331, 1073741827, N),
(552977040, 1073741827, 104595351),
(1099511627676, 1099511627791, N),
(1099511627677, 1099511627791, 269691261521),
(1099511627678, 1099511627791, 413834069585),
(1267650600228229401496703204376, 1267650600228229401496703205653, 5312823546347991512233563776),
(1267650600228229401496703204476, 1267650600228229401496703205653, N)
(1267650600228229401496703204576, 1267650600228229401496703205653, N)
(1267650600228229401496703204676, 1267650600228229401496703205653, 79905476259539917812907012931)


Input and output

You may take input and give output in any way that is convenient. If you don't like to output N then any Falsey value will do.

Restrictions

Your code must answer all the test cases in under 1 minute on a standard desktop. This time limit is only to prevent brute force answers and I expect good answers to run almost instantly. You may not use any library or builtin that solves this problem or that tests if a number is a quadratic residue.
Python 2, 166 bytes

def Q(x,n,a=0):
 e=n/2
 while pow(a*a-x,e,n)&lt;2:a+=1
 w=a*a-x;b=r=a;c=s=1
 while e:
    if e%2:r,s=(r*b+s*c*w)%n,r*c+s*b
    b,c=(b*b+c*c*w)%n,2*b*c;e/=2
 return min(r,-r%n)