e-Monk
February 14th, 2003, 12:03 AM
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.
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.