5. Quadratic Residue Problem¶
This part includes Quadratic Residue Problem (\(QR_n\)) and composite residuosity problem (\(CR_n\)).
5.1. Knowledge required¶
5.2. Quadratic Residue Problem¶
Given an odd prime \(p\) and an integer \(x\) such that \(0 \leq x \leq p-1\).
Question “Is \(x~QR~mod~p\)?” i.e.
\[y^2 \equiv x ~mod~p\]
has a solution \(y\in\mathbb{Z}_p\).
If yes, \(x\) is defined to be \(QR~mod~p\); If no, \(x\) is \(QNR~mod~p\) If \(x \equiv 0~mod~p\), \(x\) is not \(QR~mod~p\)
5.2.1. Example¶
\(p=11\).
\[\begin{split}(\pm1)^2 \equiv 1~mod~11\\(\pm2)^2 \equiv 4~mod~11\\(\pm3)^2 \equiv 9~mod~11\\(\pm4)^2 \equiv 5~mod~11\\(\pm5)^2 \equiv 3~mod~11\end{split}\]
For \(x \in \{1, 3, 4, 5, 9\}\), \(x\) is \(QR~mod~p\).
5.2.2. Euler’s Theorem¶
\(p\) is an odd prime , then \(x\) is \(QR~mod~p\) iff \(x^{(p-1)/2} \equiv 1~mod~p\)
Proof \(\Rightarrow\)
Assume \(x \equiv y^2~mod~p\), \(x^{(p-1)/2} = y^{p-1} \equiv 1~mod~p.\)