31-4 Quadratic residues

Let \(p\) be an odd prime. A number \(a \in Z_p^\*\) is a quadratic residue if the equation \(x^2 = a \pmod p\) has a solution for the unknown \(x\).

a. Show that there are exactly \((p - 1) / 2\) quadratic residues, modulo \(p\).

b. If \(p\) is prime, we define the Legendre symbol \((\frac{a}{p})\), for \(a \in \mathbb Z_p^\*\), to be \(1\) if \(a\) is a quadratic residue modulo \(p\) and \(-1\) otherwise. Prove that if \(a \in \mathbb Z_p^\*\), then

\[\left(\frac{a}{p}\right) \equiv a^{(p - 1) / 2} \pmod p.\]

Give an efficient algorithm that determines whether a given number \(a\) is a quadratic residue modulo \(p\). Analyze the efficiency of your algorithm.

c. Prove that if \(p\) is a prime of the form \(4k + 3\) and \(a\) is a quadratic residue in \(\mathbb Z_b^\*\), then \(a^{k + 1} \mod p\) is a square root of \(a\), modulo \(p\). How much time is required to find the square root of a quadratic residue \(a\) modulo \(p\)?

d. Describe an efficient randomized algorithm for finding a nonquadratic residue, modulo an arbitrary prime \(p\), that is, a member of \(\mathbb Z_p^\*\) that is not a quadratic residue. How many arithmetic operations does your algorithm require on average?

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用