[Foxtrot] Square Roots

[Alan Lawrence]

Ok, got it. Firstly, the formula root(a) = a^((p+1)/4) mod p only works
for p congruent to 3 mod 4, as that's the only time p+1 is divisible by
4. Secondly, it always gives the square root
_where_there_is_one_; so check that (result^2) = a, and if not, a has no
square root.

e.g. modulo 7

1^2 = 1
2^2 = 4
3^2 = 2
4^2 = 2
5^2 = 4
6^2 = 1

sqrt (2) = 2^((7+1)/4) = 2^2 = 4

and indeed, 4^2 = 16 = 2 mod 7

sqrt(3) = 3^((7+1)/4) = 3^2 = 2

but 2^2 != 3 mod 7.


Onto square roots modulo 7^2.

a^phi(m) = a mod m for any m

for m prime, phi(m) = m-1

for m = p^k, phi(m) = p^k - p^(k-1)

i.e. for m=p^2, phi(m) = p^2 - p = p(p-1)

check
a^42=1 mod 49 (seems to work for all a)
a^44=(a^42)a^2 = a^2 mod 49
a^22 = a mod 49
a^11 = root(a) mod 49

which seems to work.

i.e., mod p^2, root(a) = a^((p(p-1)+2)/4)

again, only works is p(p-1)+2 is divisible by 4, i.e. if p=4k+3.....

suggest you try it a bit more than I have as well!

--Alan