0

The Handbook of Applied Cryptography states Algorithm 3.39 for solving $x^2\equiv a\pmod p$ (for prime $p\ge5$ and $\left({a\over p}\right)=+1$ ):

  1. Choose random $b\in\mathbb Z_p$ until $b^2-4a$ is a quadratic non-residue modulo $p$, i.e., $\left({b^2-4a\over p}\right)=-1$ .
  2. Let $f$ be the polynomial $x^2−bx+a$ in $\mathbb Z_p[x]$ .
  3. Compute $r=x^{(p+1)/2}\bmod f$ using Algorithm 2.227 (Note: $r$ will be an integer).
  4. Return $(r,−r)$ .

How can we prove the correctness of this algorithm?

Note: $\left({a\over p}\right)$ is the Legendre symbol; one of several ways to compute it is as $a^{(p-1)/2}\bmod p$ with result $p-1$ replaced by $-1$.

Note: Here is context and a worked-out example.

fgrieu
  • 1,758

1 Answers1

1

By the condition on $b^2-4a$, $f$ is irreducible. Therefore $R=\Bbb Z_p[x]/(f(x))$ is isomorphic to $\Bbb F_{p^2}$, the finite field of order $p^2$. Write $\xi$ for the image of $x$ in $R$. Over $R$ we have $f(x)=(x-\xi)(x-\xi^p)$ so that $\xi^{p+1}=a$ in $R$. Therefore $\xi^{(p+1)/2}$ is a square root in $R$ of $a$. If $a$ is a quadratic residue, then $\xi^{(p+1)/2}\in\Bbb Z_p\subset R$.

Angina Seng
  • 158,341