Chapter 12

Let \(p\) be an odd prime. Show that the following are equivalent: (a) \((-2 \mid p)=1 ;\) (b) \(p \equiv 1\) or \(3(\bmod 8) ;\) (c) \(p=r^{2}+2 t^{2}\) for some \(r, t \in \mathbb{Z}\)

Let \(n\) be an odd, positive integer, and consider the Jacobi map \(J_{n}\) (a) Show that \(\left(\mathbb{Z}_{n}^{*}\right)^{2} \subseteq \operatorname{Ker} J_{n}\). (b) Show that if \(n\) is the square of an integer, then \(\operatorname{Ker} J_{n}=\mathbb{Z}_{n}^{*}\). (c) Show that if \(n\) is not the square of an integer, then \(\left[\mathbb{Z}_{n}^{*}: \operatorname{Ker} J_{n}\right]=2\) and \(\left[\operatorname{Ker} J_{n}:\left(\mathbb{Z}_{n}^{*}\right)^{2}\right]=2^{r-1},\) where \(r\) is the number of distinct prime divisors of \(n .\)

Let \(p\) and \(q\) be distinct primes, with \(p \equiv q \equiv 3(\bmod 4),\) and let \(n:=p q\) (a) Show that \([-1]_{n} \in \operatorname{Ker} J_{n} \backslash\left(\mathbb{Z}_{n}^{*}\right)^{2},\) and from this, conclude that the cosets of \(\left(\mathbb{Z}_{n}^{*}\right)^{2}\) in \(\operatorname{Ker} J_{n}\) are the two distinct cosets \(\left(\mathbb{Z}_{n}^{*}\right)^{2}\) and \([-1]_{n}\left(\mathbb{Z}_{n}^{*}\right)^{2}\). (b) Let \(\delta \in \mathbb{Z}_{n}^{*} \backslash\) Ker \(J_{n}\). Show that the map from \(\\{0,1\\} \times\\{0,1\\} \times\left(\mathbb{Z}_{n}^{*}\right)^{2}\) to \(\mathbb{Z}_{n}^{*}\) that sends \((a, b, \gamma)\) to \(\delta^{a}(-1)^{b} \gamma\) is a bijection.

This exercise develops a probabilistic primality test based on the Jacobi symbol. For odd integer \(n>1,\) define $$ G_{n}:=\left\\{\alpha \in \mathbb{Z}_{n}^{*}: \alpha^{(n-1) / 2}=J_{n}(\alpha)\right\\} $$ where \(J_{n}: \mathbb{Z}_{n}^{*} \rightarrow\\{\pm 1\\}\) is the Jacobi map. (a) Show that \(G_{n}\) is a subgroup of \(\mathbb{Z}_{n}^{*}\). (b) Show that if \(n\) is prime, then \(G_{n}=\mathbb{Z}_{n}^{*}\). (c) Show that if \(n\) is composite, then \(G_{n} \subseteq \mathbb{Z}_{n}^{*}\). (d) Based on parts (a)-(c), design and analyze an efficient probabilistic primality test that works by choosing a random, non-zero element \(\alpha \in \mathbb{Z}_{n},\) and testing if \(\alpha \in G_{n}\)

Let \(p\) be an odd prime, and let \(f \in \mathbb{Z}_{p}[X]\) be a polynomial with \(0 \leq \operatorname{deg}(f) \leq 2\). Design and analyze an efficient, deterministic algorithm that takes as input \(p, f,\) and an element of \(\mathbb{Z}_{p}^{*} \backslash\left(\mathbb{Z}_{p}^{*}\right)^{2},\) and which determines if \(f\) has any roots in \(\mathbb{Z}_{p},\) and if so, finds all of the roots. Hint: see Exercise 7.17 .

Show how to deterministically compute square roots modulo primes \(p \equiv 5(\bmod 8)\) in time \(O\left(\operatorname{len}(p)^{3}\right)\)

Show that the following two problems are deterministic, polytime equivalent (see discussion just above Exercise 11.10 in \(\S 11.3\) ): (a) Given an odd prime \(p\) and \(\alpha \in\left(\mathbb{Z}_{p}^{*}\right)^{2},\) find \(\beta \in \mathbb{Z}_{p}^{*}\) such that \(\beta^{2}=\alpha\). (b) Given an odd prime \(p,\) find an element of \(\mathbb{Z}_{p}^{*} \backslash\left(\mathbb{Z}_{p}^{*}\right)^{2}\).

Design and analyze an efficient, deterministic algorithm that takes as input primes \(p\) and \(q\), such that \(q \mid(p-1)\), along with an element \(\alpha \in \mathbb{Z}_{p}^{*}\), and determines whether or not \(\alpha \in\left(\mathbb{Z}_{p}^{*}\right)^{q}\).

Design and analyze an efficient, deterministic algorithm that takes as input primes \(p\) and \(q,\) such that \(q \mid(p-1)\) but \(q^{2} \nmid(p-1),\) along with an element \(\alpha \in\left(\mathbb{Z}_{p}^{*}\right)^{q},\) and computes a \(q\) th root of \(\alpha,\) that is, an element \(\beta \in \mathbb{Z}_{p}^{*}\) such that \(\beta^{q}=\alpha\).

Design and analyze an algorithm that takes as input primes \(p\) and \(q,\) such that \(q \mid(p-1),\) along with an element \(\alpha \in\left(\mathbb{Z}_{p}^{*}\right)^{q},\) and computes a \(q\) th root of \(\alpha\). (Unlike Exercise \(12.12,\) we now allow \(q^{2} \mid(p-1) .\) ) Your algorithm may be probabilistic, and should have an expected running time that is bounded by \(q^{1 / 2}\) times a polynomial in len \((p)\). Hint: Exercise 4.13 may be useful.

Let \(p\) be an odd prime, \(\gamma\) be a generator for \(\mathbb{Z}_{p}^{*},\) and \(\alpha\) be any element of \(\mathbb{Z}_{p}^{*} .\) Define $$ B(p, \gamma, \alpha):=\left\\{\begin{array}{ll} 1 & \text { if } \log _{\gamma} \alpha \geq(p-1) / 2 \\ 0 & \text { if } \log _{\gamma} \alpha<(p-1) / 2 \end{array}\right. $$ Suppose that there is an algorithm that efficiently computes \(B(p, \gamma, \alpha)\) for all \(p, \gamma, \alpha\) as above. Show how to use this algorithm as a subroutine in an efficient, probabilistic algorithm that computes \(\log _{\gamma} \alpha\) for all \(p, \gamma, \alpha\) as above. Hint: in addition to the algorithm that computes \(\boldsymbol{B}\), use algorithms for testing quadratic residuosity and computing square roots modulo \(p,\) and "read off' the bits of \(\log _{\gamma} \alpha\) one at a time.

Suppose there is a probabilistic algorithm \(A\) that takes as input positive integers \(n\) and \(m,\) and an element \(\alpha \in\left(\mathbb{Z}_{n}^{*}\right)^{m} .\) It outputs either "failure," or an \(m\) th root of \(\alpha .\) Furthermore, assume that \(A\) runs in expected polynomial time, and that for all \(n\) and \(m,\) and for randomly chosen \(\alpha \in\left(\mathbb{Z}_{n}^{*}\right)^{m}, A\) succeeds in computing an \(m\) th root of \(\alpha\) with probability \(\varepsilon(n, m) .\) Here, the probability is taken over the random choice of \(\alpha,\) as well as the random choices made during the execution of \(A .\) Show how to use \(A\) to construct another probabilistic algorithm \(A^{\prime}\) that takes as input \(n, m,\) and \(\alpha \in\left(\mathbb{Z}_{n}^{*}\right)^{m},\) runs in expected polynomial time, and that satisfies the following property: if \(\varepsilon(n, m) \geq 0.001,\) then for all \(\alpha \in\left(\mathbb{Z}_{n}^{*}\right)^{m}, A^{\prime}\) computes an \(m\) th root of \(\alpha\) with probability at least \(0.999 .\)

Suppose that \(A\) is a probabilistic algorithm that takes as input \(n\) of the form \(n=p q,\) where \(p\) and \(q\) are distinct primes such that \(p \equiv q \equiv 3(\bmod 4)\). The algorithm also takes as input \(\alpha \in \operatorname{Ker} J_{n},\) and outputs either 0 or \(1 .\) Furthermore, assume that \(A\) runs in expected polynomial time. Define two random variables, \(X_{n}\) and \(Y_{n},\) as follows: \(X_{n}\) is defined to be the output of \(A\) on input \(n\) and a value \(\alpha\) chosen at random from Ker \(J_{n} \backslash\left(\mathbb{Z}_{n}^{*}\right)^{2},\) and \(Y_{n}\) is defined to be the output of \(A\) on input \(n\) and a value \(\alpha\) chosen at random from \(\left(\mathbb{Z}_{n}^{*}\right)^{2} .\) In both cases, the value of the random variable is determined by the random choice of \(\alpha,\) as well as the random choices made by the algorithm. Define \(\varepsilon(n):=\left|\mathrm{P}\left[X_{n}=1\right]-\mathrm{P}\left[Y_{n}=1\right]\right|\). Show how to use \(A\) to design a probabilistic, expected polynomial time algorithm \(A^{\prime}\) that takes as input \(n\) as above and \(\alpha \in \operatorname{Ker} J_{n},\) and outputs either "square" or "non-square," with the following property: if \(\varepsilon(n) \geq 0.001,\) then for all \(\alpha \in \operatorname{Ker} J_{n},\) the probability that \(A^{\prime}\) correctly identifies whether \(\alpha \in\left(\mathbb{Z}_{n}^{*}\right)^{2}\) is at least \(0.999 .\)