Editing Trapdoor function (section)

===Rabin's quadratic residue assumption===

Let <math>n</math> be a large composite number such that <math>n = pq</math>, where <math>p</math> and <math>q</math> are large primes such that <math>p \equiv 3 \pmod{4}, q \equiv 3 \pmod{4}</math>, and kept confidential to the adversary. The problem is to compute <math>z</math> given <math>a</math> such that <math>a \equiv z^2 \pmod{n}</math>. The trapdoor is the factorization of <math>n</math>. With the trapdoor, the solutions of ''z'' can be given as <math>cx + dy, cx - dy, -cx + dy, -cx - dy</math>, where <math>a \equiv x^2 \pmod{p}, a \equiv y^2 \pmod{q}, c \equiv 1 \pmod{p}, c \equiv 0 \pmod{q}, d \equiv 0 \pmod{p}, d \equiv 1 \pmod{q}</math>. See [[Chinese remainder theorem]] for more details. Note that given primes <math>p</math> and <math>q</math>, we can find <math>x \equiv a^{\frac{p+1}{4}} \pmod{p}</math> and <math>y \equiv a^{\frac{q+1}{4}} \pmod{q}</math>. Here the conditions <math>p \equiv 3 \pmod{4}</math> and <math>q \equiv 3 \pmod{4}</math> guarantee that the solutions <math>x</math> and <math>y</math> can be well defined.<ref>Goldwasser's lecture notes, 2.3.4.</ref>