I'm stuck on this question, and a little lost a bit in...

Assume that p ≡ 3 (mod 4) and n ≡ x**2 (mod p). Given n and p, find one possible value of x.

Question

I'm stuck on this question, and a little lost a bit in...

Assume that p ≡ 3 (mod 4) and n ≡ x**2 (mod p).  Given n and p, find one possible value of x.

anonymous · Answer

I know that p = 4k +3 for some unknown k.
I also know that n ** (p-1 / 2) is congruent to 1 (mod p).
Therefore I know that x ** (p-2) is congruent to 1 (mod p).

I can even introduce an additional variable to make some equation with these, but at this point, I'm ridiculously stuck.

dan815 · Answer

|dw:1383116973459:dw|