Finding a square root of -1 mod p

If p is an odd prime, there is a theorem that says

x^2 = -1 mod p

has a solution if and only if p = 1 mod 4. When a solutionx exists, how do you find it?

The previous two posts have discussed Stan Wagon's algorithm for expressing an odd prime p as a sum of two squares. This is possible if and only ifp = 1 mod 4, the same condition onp for -1 to have a square root.

In the previous post we discussed how to findc such thatc does not have a square root modp. This is most of the work for finding a square root of -1. Once you havec, set

x =c^k

where p = 4k + 1.

For example, let's find a square root of -1 modp wherep = 2²⁵⁵ - 19. We found in the previous post that c = 2 is a non-residue for this value of p.

>>> p = 2**255 - 19>>> k = p // 4>>> x = pow(2, k, p)

Let's viewx and verify that it is a solution.

>>> x19681161376707505956807079304988542015446066515923890162744021073123829784752>>> (x**2 + 1) % p0

Sometimes you'll see a square root of -1 mod p written as i. This makes sense in context, but it's a little jarring at first since here i is an integer, not a complex number.

The next post completes this series, giving a full implementation of Wagon's algorithm.

The post Finding a square root of -1 mod p first appeared on John D. Cook.