Can I reduce the computational complexity of this?

Ignoring the algorithm for a moment (yes, I know, bad idea), the running time of this can be decreased hugely just by switching from while to for.

for a in range(1, n / 2 + 1)

(Hope this doesn't have an off-by-one error. I'm prone to make these.)

Another thing that I would try is to look if the step width can be incremented.

Take a look at http://modular.fas.harvard.edu/ent/ent_py .The function sqrtmod does the job if you set a = -1 and p = n.

You missed a small point because the running time of your improved algorithm is still in the order of the square root of n. As long you have only small primes n (let's say less than 2^64), that's ok, and you should probably prefer your implementation to a more complex one.

If the prime n becomes bigger, you might have to switch to an algorithm using a little bit of number theory. To my knowledge, your problem can be solved only with a probabilistic algorithm in time log(n)^3. If I remember correctly, assuming the Riemann hypothesis holds (which most people do), one can show that the running time of the following algorithm (in ruby - sorry, I don't know python) is log(log(n))*log(n)^3:

class Integer  # calculate b to the power of e modulo self  def power(b, e)    raise 'power only defined for integer base' unless b.is_a? Integer    raise 'power only defined for integer exponent' unless e.is_a? Integer    raise 'power is implemented only for positive exponent' if e < 0    return 1 if e.zero?    x = power(b, e>>1)    x *= x    (e & 1).zero? ? x % self : (x*b) % self  end  # Fermat test (probabilistic prime number test)  def prime?(b = 2)    raise "base must be at least 2 in prime?" if b < 2    raise "base must be an integer in prime?" unless b.is_a? Integer    power(b, self >> 1) == 1  end  # find square root of -1 modulo prime  def sqrt_of_minus_one    return 1 if self == 2    return false if (self & 3) != 1    raise 'sqrt_of_minus_one works only for primes' unless prime?    # now just try all numbers (each succeeds with probability 1/2)    2.upto(self) do |b|      e = self >> 1      e >>= 1 while (e & 1).zero?      x = power(b, e)      next if [1, self-1].include? x      loop do        y = (x*x) % self        return x if y == self-1        raise 'sqrt_of_minus_one works only for primes' if y == 1        x = y      end    end  endend# find a primep = loop do      x = rand(1<<512)      next if (x & 3) != 1      break x if x.prime?    endputs "%x" % pputs "%x" % p.sqrt_of_minus_one

The slow part is now finding the prime (which takes approx. log(n)^4 integer operation); finding the square root of -1 takes for 512-bit primes still less than a second.

Consider pre-computing the results and storing them in a file. Nowadays many platforms have a huge disk capacity. Then, obtaining the result will be an O(1) operation.