Finding a square root of -1 mod p
If p is an odd prime, there is a theorem that says x² = −1 mod p has a solution if and only if p = 1 mod 4. When a solution x 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 if p = 1 mod 4, the same condition on p for −1 to have […]