Chapter 10

Show that an integer \(n>1\) is prime if and only if there exists an element in \(\mathbb{Z}_{\mathbf{n}}^{*}\) of multiplicative order \(n-1\).

Show that Carmichael numbers satisfy Fermat's little theorem; that is, if \(n\) is a Carmichael number, then \(\alpha^{n}=\alpha\) for all \(\alpha \in \mathbb{Z}_{n}\).

Let \(p\) be a prime. Show that \(n:=2 p+1\) is a prime if and only if \(2^{n-1} \equiv 1(\bmod n)\)

Here is another primality test that takes as input an odd integer \(n>1,\) and a positive integer parameter \(k .\) The algorithm chooses \(\alpha_{1}, \ldots, \alpha_{k} \in \mathbb{Z}_{n}^{+}\) at random, and computes $$ \beta_{i}:=\alpha_{i}^{(n-1) / 2} \quad(i=1, \ldots, k) $$

Suppose that \(s\) is a function of \(m\) such that \(s=O\left((\log m)^{c}\right)\) for some positive constant \(c .\) Show that \(\sigma(m, s)=O(1 / \log s)\)

Design an algorithm that takes as input a prime \(q\) and a bound \(m,\) and outputs a random prime \(p\) between 2 and \(m\) such that \(p \equiv 1(\bmod q) .\) Clearly, we need to assume that \(m\) is sufficiently large with respect to \(q\). Analyze your algorithm assuming Conjecture 5.22. State how large \(m\) must be with respect to \(q,\) and under these assumptions, show that your algorithm runs in time \(O\left(\ell^{4} / \operatorname{len}(\ell)+k \ell^{3}\right),\) and that its output is incorrect with probability \(O\left(4^{-k} \ell\right) .\) As usual, \(\ell:=\operatorname{len}(m)\)

Suppose there is a probabilistic algorithm \(A\) that takes as input an integer \(n\) of the form \(n=p q,\) where \(p\) and \(q\) are distinct, \(\ell\) -bit primes, with \(p=2 p^{\prime}+1\) and \(q=2 q^{\prime}+1,\) where \(p^{\prime}\) and \(q^{\prime}\) are prime. The algorithm also takes as input \(\alpha, \beta \in\left(\mathbb{Z}_{n}^{*}\right)^{2} .\) It outputs either "failure," or integers \(x, y,\) not both zero, such that \(\alpha^{x} \beta^{y}=1\). Furthermore, assume that \(A\) runs in expected polynomial time, and that for all \(n\) of the above form, and for randomly chosen \(\alpha, \beta \in\left(\mathbb{Z}_{n}^{*}\right)^{2}\), \(A\) succeeds in finding \(x, y\) as above with probability \(\varepsilon(n) .\) Here, the probability is taken over the random choice of \(\alpha\) and \(\beta,\) as well as the random choices made during the execution of \(A\) on input \((n, \alpha, \beta)\). Show how to use \(A\) to construct another probabilistic algorithm \(A^{\prime}\) that takes as input \(n\) as above, runs in expected polynomial time, and that satisfies the following property: if \(\varepsilon(n) \geq 0.001,\) then \(A^{\prime}\) factors \(n\) with probability at least \(0.999 .\)