I have been reading about the public key cipher where the encrption is squaring your message mod n where n=pq (primes = 3 mod 4).

The decryption scheme here relies on finding roots mod p,q - namely on the theorem that states: x^(p+1)/4 is a square root of either x or negative x mod p, if p is prime=3 mod 4. It was not mentioned in my text why the -x case is not relevant. Since the number that needs to be rooted is known to be a rsult of squaring, it is implied that the way they know the -x will not happen is that there is some theorem that states the following:

let p be prime and p=3 mod 4, then there is no x such that x^2= -1 mod p.

 

My question is: is there indeed such a theorem? if yes, can a proof be outlined or linked to? if no, is there a counter example?

 

Thanks in advance.

Eurika. I found what I was looking for. If you're interested:

http://www.math.swt.edu/~haz/prob_sets/notes/node30.html

 

Good week.