Section 3.9, due Friday October 15

1. (Difficult) Can you explain why -1 cannot be a square root of mod p when p = 3 mod 4, on pages 86-87? Does that have something to do with the fact that if p = 3 mod 4, then p =-1 mod 4? Also, I assume you are going to go over an example in class, which would be helpful. I follow the example in the book pretty well, but some of the steps are confusing. Can you explain the step at the end, where the gcd(a-b, n) = p?

2. (Reflective) It amazes me some of the propositions and theorems are discovered. I wonder how someone discovered that we need p = 3 (mod 4) for this to work. It is certainly a useful theorem for factoring, it just seems like the needed conditions are somewhat arbitrary. This material is also new to me, so that may be why that seems rather random, but possibly should be intuitive. This proposition certainly will be helpful in RSA, since this proposition is computationally equivalent to factoring n. I assume that this has been used many times in attacks of RSA.