Number Theory and Algebra

Prev: Online Algorithms

Problems

14.1

Prove Theorem 14.2 by giving a detailed description of the extended Euclidean algorithm and its analysis. To prove a polynomial time bound for this algorithm, you will need to argue that the lengths of the operands in the intermediate computations are suitably bounded.

---

14.2

Show how to compute multiplicative inverses modulo a prime $p$ via a single exponentiation. Does this work modulo composite $n$?

---

14.3

Show that given any number $n$ and $\varphi (n)$, the prime factorization of $n$ can be computed by a randomized polynomial time algorithm.

---

14.4

Devise a randomized polynomial time algorithm for factoring a number $n$ that is the product of two primes, given that some multiple of $\varphi (n)$ is also provided as a part of the input. Can you generalize this to arbitrary $n$?

---

14.5

Show that for any odd prime $p$, the set $\{x^2\mid 1\le x\le \frac{p-1}{2}\}$ is exactly the set of all quadratic residues modulo $p$.

---

14.6

Let $a$ be a quadratic residue modulo $n=2^k$. Show that

• for $k=1$, $a$ has one square root modulo $n$;
• for $k=2$, $a$ has two square roots modulo $n$;
• for $k>2$, $a$ has four square roots modulo $n$.

---

14.7

Generalize Theorem 14.19 to allow the possibility of even numbers. (Hint: Use Problem 14.6.)

---

14.8

(a) Show that for any odd $n$ with $t$ distinct prime factors, the number of quadratic residues in $Z_n^{\ast }$ is $\varphi (n)/2^t$.

(b) Using Problem 14.7, generalize this to the case of even $n$.

(c) Can these observations be used to devise a randomized algorithm for finding a quadratic non-residue modulo $n$?

---

14.9

Due to M.O. Rabin [346].

Consider the Rabin cryptosystem with $n=pq$ such that $p\equiv 3(\mathrm{mod}8)$ and $q\equiv 7(\mathrm{mod}8)$.

(a) Prove that for all $x$ the Jacobi symbols satisfy $\left[\frac{x}{n}\right]=\left[\frac{-x}{n}\right]=-\left[\frac{2x}{n}\right]$.

(b) Using this observation and Exercise 14.12, show that we can choose the messages to lie in a subset of $Z_n$ such that there is a canonical way to determine the message from among the four square roots of its square modulo $n$.

---

14.10

Let $n$ have the prime factorization $p_1^{k_1}{p}_2^{k_2}\cdots p_t^{k_t}$, where each $p_i$ is an odd prime.

(a) Show that $n$ is a Carmichael number if and only if

$$\varphi (p_i^{k_i})\mid (n-1)$$

for $1\le i\le t$.

(b) Conclude that the Carmichael numbers can be characterized as products of distinct primes

$$n=\prod _{i=1}^t{p}_i,$$

such that for each $i$, $(p_i-1)\mid (n-1)$.

---

14.11

(a) Prove all the properties of the Jacobi symbol provided in Theorem 14.29.

(b) Using these properties, devise a polynomial time algorithm for computing $\left[\frac{a}{n}\right]$ without knowing the prime factorization of $n$ or $a$.

---

14.12

We have seen how to test if a number is prime. In several applications, it is necessary to pick large prime numbers at random. For example, in the RSA scheme Alice must have two large primes $p$ and $q$, but she would like to choose them randomly since they are to be kept secret. Suggest a randomized algorithm for generating a random $\Theta (\log n)$ bit length prime. Analyze the expected time to generate such a prime. (Hint: Refer to the Prime Number Theorem described in Section 7.4.)

---

14.13

Suppose you are given an algorithm $S$ for computing square roots modulo a prime number. Using this algorithm as a blackbox, design an efficient randomized (RP) algorithm for compositeness. (Hint: The idea is to choose a random element $a\in Z_n^{\ast }$, and run algorithm $S$ on $b=a^2$. If $S$ fails to find a square root, then $n$ is not a prime. On the other hand, if $S$ finds a square root other than $\pm a$, then again $n$ is not a prime.)

---

14.14

Due to M.O. Rabin [341,342].

Show that when the input $n$ is a Carmichael number, Algorithm Primality3 will return PRIME with probability at most $1/2$. (Hint: Use the characterization of Carmichael numbers described in Problem 14.10.)