Integer Factorization and RSA

Prev: Discrete Logarithms and Diffie-Hellman Next: Digital Signatures

Exercises

Section 3.1. Euler’s Theorem and Roots Modulo $pq$

3.1

Solve the following congruences.

(a) $x^{19}\equiv 36(\mathrm{mod}97)$.

(b) $x^{137}\equiv 428(\mathrm{mod}541)$.

(c) $x^{73}\equiv 614(\mathrm{mod}1159)$.

(d) $x^{751}\equiv 677(\mathrm{mod}8023)$.

(e) $x^{38993}\equiv 328047(\mathrm{mod}401227)$. Hint: $401227=607\cdot 661$.

3.2

This exercise investigates what happens if we drop the assumption that $\gcd (e,p-1)=1$ in Proposition 3.2. So let $p$ be a prime, let $c\not\equiv 0(\mathrm{mod}p)$, let $e\ge 1$, and consider the congruence

$$x^e\equiv c(\mathrm{mod}p).\text{\hspace{1em}(3.36)}$$

(a) Prove that if (3.36) has one solution, then it has exactly $\gcd (e,p-1)$ distinct solutions. Hint: Use the primitive root theorem (Theorem 1.30), combined with the extended Euclidean algorithm (Theorem 1.11) or Exercise 1.27.

(b) For how many non-zero values of $c(\mathrm{mod}p)$ does the congruence (3.36) have a solution?

3.3

Let $p$ and $q$ be distinct primes and let $e$ and $d$ be positive integers satisfying

$$de\equiv 1(\mathrm{mod}(p-1)(q-1)).$$

Suppose further that $c$ is an integer with $\gcd (c,pq)>1$. Prove that

$$x\equiv c^d(\mathrm{mod}pq)$$

is a solution to the congruence $x^e\equiv c(\mathrm{mod}pq)$, thereby completing the proof of Proposition 3.5.

3.4

Recall from Sect. 1.3 that Euler’s phi function $\phi (N)$ is the function defined by

$$\phi (N)=\#\{0\le k<N:\gcd (k,N)=1\}.$$

In other words, $\phi (N)$ is the number of integers between $0$ and $N-1$ that are relatively prime to $N$, or equivalently, the number of elements in $\mathbb{Z}/N\mathbb{Z}$ that have inverses modulo $N$.

(a) Compute the values of $\phi (6)$, $\phi (9)$, $\phi (15)$, and $\phi (17)$.

(b) If $p$ is prime, what is the value of $\phi (p)$?

(c) Prove Euler’s formula

$$a^{\phi (N)}\equiv 1(\mathrm{mod}N)\text{for all integers }a\text{ satisfying }\gcd (a,N)=1.$$

Hint: Mimic the proof of Fermat’s little theorem (Theorem 1.24), but instead of looking at all of the multiples of $a$ as was done in (1.8), just take the multiples $ka$ of $a$ for values of $k$ satisfying $\gcd (k,N)=1$.

3.5

Euler’s phi function has many beautiful properties.

(a) If $p$ and $q$ are distinct primes, how is $\phi (pq)$ related to $\phi (p)$ and $\phi (q)$?

(b) If $p$ is prime, what is the value of $\phi (p^2)$? How about $\phi (p^j)$? Prove that your formula for $\phi (p^j)$ is correct. Hint: Among the numbers between $0$ and $p^j-1$, remove the ones that have a factor of $p$. The ones that are left are relatively prime to $p$.

(c) Let $M$ and $N$ be integers satisfying $\gcd (M,N)=1$. Prove the multiplication formula

$$\phi (MN)=\phi (M)\phi (N).$$

(d) Let $p_1,p_2,\dots ,p_r$ be the distinct primes that divide $N$. Use your results from (b) and (c) to prove the following formula:

$$\phi (N)=N\prod _{i=1}^r\left(1-\frac{1}{p_i}\right).$$

(e) Use the formula in (d) to compute the following values of $\phi (N)$.

(i) $\phi (1728)$.

(ii) $\phi (1575)$.

(iii) $\phi (889056)$. Hint: $889056=2^5\cdot 3^4\cdot 7^3$.

3.6

Let $N$, $c$, and $e$ be positive integers satisfying the conditions $\gcd (N,c)=1$ and $\gcd (e,\phi (N))=1$.

(a) Explain how to solve the congruence

$$x^e\equiv c(\mathrm{mod}N),$$

assuming that you know the value of $\phi (N)$. Hint: Use the formula in Exercise 3.4(c).

(b) Solve the following congruences. The formula in Exercise 3.5(d) may be helpful for computing the value of $\phi (N)$.

(i) $x^{577}\equiv 60(\mathrm{mod}1463)$.

(ii) $x^{959}\equiv 1583(\mathrm{mod}1625)$.

(iii) $x^{133957}\equiv 224689(\mathrm{mod}2134440)$.

Section 3.2. The RSA Public Key Cryptosystem

3.7

Alice publishes her RSA public key: modulus $N=2038667$ and exponent $e=103$.

(a) Bob wants to send Alice the message $m=892383$. What ciphertext does Bob send to Alice?

(b) Alice knows that her modulus factors into a product of two primes, one of which is $p=1301$. Find a decryption exponent $d$ for Alice.

(c) Alice receives the ciphertext $c=317730$ from Bob. Decrypt the message.

3.8

Bob’s RSA public key has modulus $N=12191$ and exponent $e=37$. Alice sends Bob the ciphertext $c=587$. Unfortunately, Bob has chosen too small a modulus. Help Eve by factoring $N$ and decrypting Alice’s message. Hint: $N$ has a factor smaller than $100$.

3.9

For each of the given values of $N=pq$ and $(p-1)(q-1)$, use the method described in Remark 3.11 to determine $p$ and $q$.

(a) $N=pq=352717$ and $(p-1)(q-1)=351520$.

(b) $N=pq=77083921$ and $(p-1)(q-1)=77066212$.

(c) $N=pq=109404161$ and $(p-1)(q-1)=109380612$.

(d) $N=pq=172205490419$ and $(p-1)(q-1)=172204660344$.

3.10

A decryption exponent for an RSA public key $(N,e)$ is an integer $d$ with the property that $a^{de}\equiv a(\mathrm{mod}N)$ for all integers $a$ that are relatively prime to $N$.

(a) Suppose that Eve has a magic box that creates decryption exponents for $(N,e)$ for a fixed modulus $N$ and for a large number of different encryption exponents $e$. Explain how Eve can use her magic box to try to factor $N$.

(b) Let $N=38749709$. Eve’s magic box tells her that the encryption exponent $e=10988423$ has decryption exponent $d=16784693$ and that the encryption exponent $e=25910155$ has decryption exponent $d=11514115$. Use this information to factor $N$.

(c) Let $N=225022969$. Eve’s magic box tells her the following three encryption/decryption pairs for $N$:

$$(70583995,4911157),(173111957,7346999),(180311381,29597249).$$

Use this information to factor $N$.

(d) Let $N=1291233941$. Eve’s magic box tells her the following three encryption/decryption pairs for $N$:

$$(1103927639,76923209),(1022313977,106791263),(387632407,7764043).$$

Use this information to factor $N$.

3.11

Here is an example of a public key system that was proposed at a cryptography conference. It was designed to be more efficient than RSA.

Alice chooses two large primes $p$ and $q$ and she publishes $N=pq$. It is assumed that $N$ is hard to factor. Alice also chooses three random numbers $g$, $r_1$, and $r_2$ modulo $N$ and computes

$$g_1\equiv g^{r_1(p-1)}(\mathrm{mod}N)\text{and}{g}_2\equiv g^{r_2(q-1)}(\mathrm{mod}N).$$

Her public key is the triple $(N,g_1,g_2)$ and her private key is the pair of primes $(p,q)$.

Now Bob wants to send the message $m$ to Alice, where $m$ is a number modulo $N$. He chooses two random integers $s_1$ and $s_2$ modulo $N$ and computes

$$c_1\equiv m{g}_1^{s_1}(\mathrm{mod}N)\text{and}{c}_2\equiv m{g}_2^{s_2}(\mathrm{mod}N).$$

Bob sends the ciphertext $(c_1,c_2)$ to Alice.

Decryption is extremely fast and easy. Alice uses the Chinese remainder theorem to solve the pair of congruences

$$x\equiv c_1(\mathrm{mod}p)\text{and}x\equiv c_2(\mathrm{mod}q).$$

(a) Prove that Alice’s solution $x$ is equal to Bob’s plaintext $m$.

(b) Explain why this cryptosystem is not secure.

Section 3.3. Implementation and Security Issues

3.12

Formulate a man-in-the-middle attack, similar to the attack described in Example 3.13 on page 126, for the following public key cryptosystems.

(a) The Elgamal public key cryptosystem (Table 2.3 on page 72).

(b) The RSA public key cryptosystem (Table 3.1 on page 123).

3.13

Alice decides to use RSA with the public key $N=1889570071$. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent $e_1=1021763679$ and once using the encryption exponent $e_2=519424709$. Eve intercepts the two encrypted messages

$$c_1=1244183534\text{and}{c}_2=732959706.$$

Assuming that Eve also knows $N$ and the two encryption exponents $e_1$ and $e_2$, use the method described in Example 3.15 to help Eve recover Bob’s plaintext without finding a factorization of $N$.

Section 3.4. Primality Testing

3.14

We stated that the number $561$ is a Carmichael number, but we never checked that $a^{561}\equiv a(\mathrm{mod}561)$ for every value of $a$.

(a) The number $561$ factors as $3\cdot 11\cdot 17$. First use Fermat’s little theorem to prove that

$$a^{561}\equiv a(\mathrm{mod}3),a^{561}\equiv a(\mathrm{mod}11),a^{561}\equiv a(\mathrm{mod}17)$$

for every value of $a$. Then explain why these three congruences imply that $a^{561}\equiv a(\mathrm{mod}561)$ for every value of $a$.

(b) Mimic the idea used in (a) to prove that each of the following numbers is a Carmichael number. To assist you, we have factored each number into primes.

(i) $1729=7\cdot 13\cdot 19$.

(ii) $10585=5\cdot 29\cdot 73$.

(iii) $75361=11\cdot 13\cdot 17\cdot 31$.

(iv) $1024651=19\cdot 199\cdot 271$.

(c) Prove that a Carmichael number must be odd.

(d) Prove that a Carmichael number must be a product of distinct primes.

(e) Look up Korselt’s criterion in a book or online, write a brief description of how it works, and use it to show that $29341=13\cdot 37\cdot 61$ and $172947529=307\cdot 613\cdot 919$ are Carmichael numbers.

3.15

Use the Miller-Rabin test on each of the following numbers. In each case, either provide a Miller-Rabin witness for the compositeness of $n$, or conclude that $n$ is probably prime by providing $10$ numbers that are not Miller-Rabin witnesses for $n$.

(a) $n=1105$. Yes, $5$ divides $n$, but this is just a warm-up exercise.

(b) $n=294409$.

(c) $n=294439$.

(d) $n=118901509$.

(e) $n=118901521$.

(f) $n=118901527$.

(g) $n=118915387$.

3.16

Looking back at Exercise 3.10, let’s suppose that for a given $N$, the magic box can produce only one decryption exponent. Equivalently, suppose that an RSA key pair has been compromised and that the private decryption exponent corresponding to the public encryption exponent has been discovered. Show how the basic idea in the Miller-Rabin primality test can be applied to use this information to factor $N$.

3.17

The function $\pi (X)$ counts the number of primes between $2$ and $X$.

(a) Compute the values of $\pi (20)$, $\pi (30)$, and $\pi (100)$.

(b) Write a program to compute $\pi (X)$ and use it to compute $\pi (X)$ and the ratio $\pi (X)/(X/\ln (X))$ for $X=100$, $X=1000$, $X=10000$, and $X=100000$. Does your list of ratios make the prime number theorem plausible?

3.18

Let

$$\begin{array}{rl}{\pi }_1(X)& =\#\{\text{primes }p\text{ between }2\text{ and }X\text{ satisfying }p\equiv 1(\mathrm{mod}4)\},\\ {\pi }_3(X)& =\#\{\text{primes }p\text{ between }2\text{ and }X\text{ satisfying }p\equiv 3(\mathrm{mod}4)\}.\end{array}$$

Thus every prime other than $2$ gets counted by either ${\pi }_1(X)$ or by ${\pi }_3(X)$.

(a) Compute the values of ${\pi }_1(X)$ and ${\pi }_3(X)$ for each of the following values of $X$.

(i) $X=10$.

(ii) $X=25$.

(iii) $X=100$.

(b) Write a program to compute ${\pi }_1(X)$ and ${\pi }_3(X)$ and use it to compute their values and the ratio ${\pi }_3(X)/{\pi }_1(X)$ for $X=100$, $X=1000$, $X=10000$, and $X=100000$.

(c) Based on your data from (b), make a conjecture about the relative sizes of ${\pi }_1(X)$ and ${\pi }_3(X)$. Which one do you think is larger? What do you think is the limit of the ratio ${\pi }_3(X)/{\pi }_1(X)$ as $X\to \infty$?

3.19

We noted in Sect. 3.4 that it really makes no sense to say that the number $n$ has probability $1/\ln (n)$ of being prime. Any particular number that you choose either will be prime or will not be prime; there are no numbers that are $35\%$ prime and $65\%$ composite. In this exercise you will prove a result that gives a more sensible meaning to the statement that a number has a certain probability of being prime. You may use the prime number theorem (Theorem 3.21) for this problem.

(a) Fix a large number $N$ and suppose that Bob chooses a random number $n$ in the interval $\frac{1}{2}N\le n\le \frac{3}{2}N$. If he repeats this process many times, prove that approximately $1/\ln (N)$ of his numbers will be prime. More precisely, define

$$\begin{array}{rl}P(N)& =\frac{\text{number of primes between }\frac{1}{2}N\text{ and }\frac{3}{2}N}{\text{number of integers between }\frac{1}{2}N\text{ and }\frac{3}{2}N}\\ & =\mathrm{Pr}\left(\text{an integer }n\text{ in the interval }\frac{1}{2}N\le n\le \frac{3}{2}N\text{ is prime}\right),\end{array}$$

and prove that

$$\underset{N\to \infty }{\lim }\frac{P(N)}{1/\ln (N)}=1.$$

This shows that if $N$ is large, then $P(N)$ is approximately $1/\ln (N)$.

(b) More generally, fix two numbers $c_1$ and $c_2$ satisfying $c_2>c_1>0$. Bob chooses random numbers $n$ in the interval $c_{1}N\le n\le c_{2}N$. Keeping $c_1$ and $c_2$ fixed, let

$$P(c_1,c_2;N)=\mathrm{Pr}(\text{an integer }n\text{ in the interval }{c}_{1}N\le n\le c_{2}N\text{ is prime}).$$

In the following formula, fill in the box with a simple function of $N$ so that the statement is true:

$$\underset{N\to \infty }{\lim }\frac{P(c_1,c_2;N)}{\boxed{}}=1.$$

3.20

Continuing with the previous exercise, explain how to make mathematical sense of the following statements.

(a) A randomly chosen odd number $N$ has probability $2/\ln (N)$ of being prime. What is the probability that a randomly chosen even number is prime?

(b) A randomly chosen number $N$ satisfying $N\equiv 1(\mathrm{mod}3)$ has probability $3/(2\ln (N))$ of being prime.

(c) A randomly chosen number $N$ satisfying $N\equiv 1(\mathrm{mod}6)$ has probability $3/\ln (N)$ of being prime.

(d) Let $m=p_1{p}_2\cdots p_r$ be a product of distinct primes and let $k$ be a number satisfying $\gcd (k,m)=1$. What number should go into the box to make statement (3.37) correct? Why?

$$\text{A randomly chosen number }N\text{ satisfying }N\equiv k(\mathrm{mod}m)\text{ has probability }\frac{\boxed{}}{\ln (N)}\text{ of being prime.}\text{\hspace{1em}(3.37)}$$

(e) Same question, but for arbitrary $m$, not just for $m$ that are products of distinct primes.

3.21

The logarithmic integral function $\mathrm{Li}(X)$ is defined to be

$$\mathrm{Li}(X)={\int }_2^X\frac{dt}{\ln t}.$$

(a) Prove that

$$\mathrm{Li}(X)=\frac{X}{\ln X}+{\int }_2^X\frac{dt}{(\ln t{)}^2}+O(1).$$

Hint: Integration by parts.

(b) Compute the limit

$$\underset{X\to \infty }{\lim }\frac{\mathrm{Li}(X)}{X/\ln X}.$$

Hint: Break the integral in (a) into two pieces, $2\le t\le \sqrt{X}$ and $\sqrt{X}\le t\le X$, and estimate each piece separately.

(c) Use (b) to show that formula (3.12) on page 135 implies the prime number theorem (Theorem 3.21).

Section 3.5. Pollard’s $p-1$ Factorization Algorithm

3.22

Use Pollard’s $p-1$ method to factor each of the following numbers.

(a) $n=1739$.

(b) $n=220459$.

(c) $n=48356747$.

Be sure to show your work and to indicate which prime factor $p$ of $n$ has the property that $p-1$ is a product of small primes.

3.23

A prime of the form $2^n-1$ is called a Mersenne prime.

(a) Factor each of the numbers $2^n-1$ for $n=2,3,\dots ,10$. Which ones are Mersenne primes?

(b) Find the first seven Mersenne primes. You may need a computer.

(c) If $n$ is even and $n>2$, prove that $2^n-1$ is not prime.

(d) If $3\mid n$ and $n>3$, prove that $2^n-1$ is not prime.

(e) More generally, prove that if $n$ is a composite number, then $2^n-1$ is not prime. Thus all Mersenne primes have the form $2^p-1$ with $p$ a prime number.

(f) What is the largest known Mersenne prime? Are there any larger primes known? You can find out at the “Great Internet Mersenne Prime Search” web site www.mersenne.org/prime.htm.

(g) Write a one page essay on Mersenne primes, starting with the discoveries of Father Mersenne and ending with GIMPS.

Section 3.6. Factorization via Difference of Squares

3.24

For each of the following numbers $N$, compute the values of

$$N+1^2,N+2^2,N+3^2,N+4^2,\dots$$

as we did in Example 3.34 until you find a value $N+b^2$ that is a perfect square $a^2$. Then use the values of $a$ and $b$ to factor $N$.

(a) $N=53357$.

(b) $N=34571$.

(c) $N=25777$.

(d) $N=64213$.

3.25

For each of the listed values of $N$, $k$, and $b_{\mathrm{init}}$, factor $N$ by making a list of values of $k\cdot N+b^2$, starting at $b=b_{\mathrm{init}}$ and incrementing $b$ until $k\cdot N+b^2$ is a perfect square. Then take greatest common divisors as we did in Example 3.35.

(a) $N=143041$, $k=247$, $b_{\mathrm{init}}=1$.

(b) $N=1226987$, $k=3$, $b_{\mathrm{init}}=36$.

(c) $N=2510839$, $k=21$, $b_{\mathrm{init}}=90$.

3.26

For each part, use the data provided to find values of $a$ and $b$ satisfying $a^2\equiv b^2(\mathrm{mod}N)$, and then compute $\gcd (N,a-b)$ in order to find a nontrivial factor of $N$, as we did in Examples 3.37 and 3.38.

(a) $N=61063$

$$\begin{array}{rlrl}1882^2& \equiv 270(\mathrm{mod}61063),& 270& =2\cdot 3^3\cdot 5,\\ 1898^2& \equiv 60750(\mathrm{mod}61063),& 60750& =2\cdot 3^5\cdot 5^3.\end{array}$$

(b) $N=52907$

$$\begin{array}{rlrl}399^2& \equiv 480(\mathrm{mod}52907),& 480& =2^5\cdot 3\cdot 5,\\ 763^2& \equiv 192(\mathrm{mod}52907),& 192& =2^6\cdot 3,\\ 773^2& \equiv 15552(\mathrm{mod}52907),& 15552& =2^6\cdot 3^5,\\ 976^2& \equiv 250(\mathrm{mod}52907),& 250& =2\cdot 5^3.\end{array}$$

(c) $N=198103$

$$\begin{array}{rlrl}1189^2& \equiv 27000(\mathrm{mod}198103),& 27000& =2^3\cdot 3^3\cdot 5^3,\\ 1605^2& \equiv 686(\mathrm{mod}198103),& 686& =2\cdot 7^3,\\ 2378^2& \equiv 108000(\mathrm{mod}198103),& 108000& =2^5\cdot 3^3\cdot 5^3,\\ 2815^2& \equiv 105(\mathrm{mod}198103),& 105& =3\cdot 5\cdot 7.\end{array}$$

(d) $N=2525891$

$$\begin{array}{rlrl}1591^2& \equiv 5390(\mathrm{mod}2525891),& 5390& =2\cdot 5\cdot 7^2\cdot 11,\\ 3182^2& \equiv 21560(\mathrm{mod}2525891),& 21560& =2^3\cdot 5\cdot 7^2\cdot 11,\\ 4773^2& \equiv 48510(\mathrm{mod}2525891),& 48510& =2\cdot 3^2\cdot 5\cdot 7^2\cdot 11,\\ 5275^2& \equiv 40824(\mathrm{mod}2525891),& 40824& =2^3\cdot 3^6\cdot 7,\\ 5401^2& \equiv 1386000(\mathrm{mod}2525891),& 1386000& =2^4\cdot 3^2\cdot 5^3\cdot 7\cdot 11.\end{array}$$

Section 3.7. Smooth Numbers, Sieves, and Building Relations for Factorization

3.27

Compute the following values of $\psi (X,B)$, the number of $B$-smooth numbers between $2$ and $X$ (see page 150).

(a) $\psi (25,3)$.

(b) $\psi (35,5)$.

(c) $\psi (50,7)$.

(d) $\psi (100,5)$.

(e) $\psi (100,7)$.

3.28

An integer $M$ is called $B$-power-smooth if every prime power $p^e$ dividing $M$ satisfies $p^e\le B$. For example, $180=2^2\cdot 3^2\cdot 5$ is $10$-power-smooth, since the largest prime power dividing $180$ is $9$, which is smaller than $10$.

(a) Suppose that $M$ is $B$-power-smooth. Prove that $M$ is also $B$-smooth.

(b) Suppose that $M$ is $B$-smooth. Is it always true that $M$ is also $B$-power-smooth? Either prove that it is true or give an example for which it is not true.

(c) The following is a list of $20$ randomly chosen numbers between $1$ and $1000$, sorted from smallest to largest. Which of these numbers are $10$-power-smooth? Which of them are $10$-smooth?

$$\{84,141,171,208,224,318,325,366,378,390,420,440,504,530,707,726,758,765,792,817\}.$$

(d) Prove that $M$ is $B$-power-smooth if and only if $M$ divides the least common multiple of $[1,2,\dots ,B]$. The least common multiple of a list of numbers $k_1,\dots ,k_r$ is the smallest number $K$ that is divisible by every number in the list.

3.29

Let $L(N)=e^{\sqrt{(\ln N)(\ln \ln N)}}$ as usual. Suppose that a computer does one billion operations per second.

(a) How many seconds does it take to perform $L(2^{100})$ operations?

(b) How many hours does it take to perform $L(2^{250})$ operations?

(c) How many days does it take to perform $L(2^{350})$ operations?

(d) How many years does it take to perform $L(2^{500})$ operations?

(e) How many years does it take to perform $L(2^{750})$ operations?

(f) How many years does it take to perform $L(2^{1000})$ operations?

(g) How many years does it take to perform $L(2^{2000})$ operations?

For simplicity, you may assume that there are $365.25$ days in a year.

3.30

Prove that the function $L(X)=e^{\sqrt{(\ln X)(\ln \ln X)}}$ is subexponential. That is, prove the following two statements.

(a) For every positive constant $\alpha$, no matter how large, $L(X)=\Omega ((\ln X{)}^{\alpha })$.

(b) For every positive constant $\beta$, no matter how small, $L(X)=O(X^{\beta })$.

3.31

For any fixed positive constants $a$ and $b$, define the function

$$F_{a,b}(X)=e^{(\ln X{)}^{1/a}(\ln \ln X{)}^{1/b}}.$$

Prove the following properties of $F_{a,b}(X)$.

(a) If $a>1$, prove that $F_{a,b}(X)$ is subexponential.

(b) If $a=1$, prove that $F_{a,b}(X)=\Omega (X^{\alpha })$ for every $\alpha >0$. Thus $F_{a,b}(X)$ grows faster than every exponential function, so one says that $F_{a,b}(X)$ has superexponential growth.

(c) What happens if $a<1$?

3.32

This exercise asks you to verify an assertion in the proof of Corollary 3.45. Let $L(X)$ be the usual function $L(X)=e^{\sqrt{(\ln X)(\ln \ln X)}}$.

(a) Prove that there is a value of $ϵ>0$ such that

$$(\ln X{)}^{ϵ}<\ln L(X)<(\ln X{)}^{1-ϵ}\text{for all }X>10.$$

(b) Let $c>0$, let $Y=L(X{)}^c$, and let $u=(\ln X)/(\ln Y)$. Prove that

$$u^{-u}=L(X{)}^{-\frac{1}{2c}(1+o(1))}.$$

3.33

Proposition 3.48 assumes that we choose random numbers $a$ modulo $N$, compute $a^2(\mathrm{mod}N)$, and check whether the result is $B$-smooth. We can achieve better results if we take values for $a$ of the form

$$a=\lfloor \sqrt{N}\rfloor +k\text{for }1\le k\le K.$$

For simplicity, you may treat $K$ as a fixed integer, independent of $N$. More rigorously, it is necessary to take $K$ equal to a power of $L(N)$, which has a small effect on the final answer.

(a) Prove that $a^2-N\le 2K\sqrt{N}+K^2$, so in particular, $a^2(\mathrm{mod}N)$ is smaller than a multiple of $\sqrt{N}$.

(b) Prove that $L(\sqrt{N})\approx L(N{)}^{1/\sqrt{2}}$ by showing that

$$\underset{N\to \infty }{\lim }\frac{\log L(\sqrt{N})}{\log L(N{)}^{1/\sqrt{2}}}=1.$$

More generally, prove that in the same sense, $L(N^{1/r})\approx L(N{)}^{1/\sqrt{r}}$ for any fixed $r>0$.

(c) Re-prove Proposition 3.48 using this better choice of values for $a$. Set $B=L(N{)}^c$ and find the optimal value of $c$. Approximately how many relations are needed to factor $N$?

3.34

Illustrate the quadratic sieve, as was done in Fig. 3.3 (page 161), by sieving prime powers up to $B$ on the values of $F(T)=T^2-N$ in the indicated range.

(a) Sieve $N=493$ using prime powers up to $B=11$ on values from $F(23)$ to $F(38)$. Use the relation(s) that you find to factor $N$.

(b) Extend the computations in (a) by using prime powers up to $B=16$ and sieving values from $F(23)$ to $F(50)$. What additional value(s) are sieved down to $1$ and what additional relation(s) do they yield?

3.35

Let $\mathbb{Z}[\beta ]$ be the ring described in Example 3.55, i.e., $\beta$ is a root of $f(x)=1+3x-2x^3+x^4$. For each of the following pairs of elements $u,v\in \mathbb{Z}[\beta ]$, compute the sum $u+v$ and the product $uv$. Your answers should involve only powers of $\beta$ up to ${\beta }^3$.

(a) $u=-5-2\beta +9{\beta }^2-9{\beta }^3$ and $v=2+9\beta -7{\beta }^2+7{\beta }^3$.

(b) $u=9+9\beta +6{\beta }^2-5{\beta }^3$ and $v=-4-6\beta -2{\beta }^2-5{\beta }^3$.

(c) $u=6-5\beta +3{\beta }^2+3{\beta }^3$ and $v=-2+7\beta +6{\beta }^2$.

Section 3.8. The Index Calculus and Discrete Logarithms

3.36

This exercise asks you to use the index calculus to solve a discrete logarithm problem. Let $p=19079$ and $g=17$.

(a) Verify that $g^i(\mathrm{mod}p)$ is $5$-smooth for each of the values $i=3030$, $i=6892$, and $i=18312$.

(b) Use your computations in (a) and linear algebra to compute the discrete logarithms ${\log }_g(2)$, ${\log }_g(3)$, and ${\log }_g(5)$. Note that $19078=2\cdot 9539$ and that $9539$ is prime.

(c) Verify that $19\cdot 17^{-12400}(\mathrm{mod}p)$ is $5$-smooth.

(d) Use the values from (b) and the computation in (c) to solve the discrete logarithm problem

$$17^x\equiv 19(\mathrm{mod}19079).$$

Section 3.9. Quadratic Residues and Quadratic Reciprocity

3.37

Let $p$ be an odd prime and let $a$ be an integer with $p\nmid a$.

(a) Prove that $a^{(p-1)/2}$ is congruent to either $1$ or $-1$ modulo $p$.

(b) Prove that $a^{(p-1)/2}$ is congruent to $1$ modulo $p$ if and only if $a$ is a quadratic residue modulo $p$. Hint: Let $g$ be a primitive root for $p$ and use the fact, proven during the course of proving Proposition 3.61, that $g^m$ is a quadratic residue if and only if $m$ is even.

(c) Prove that

$$a^{(p-1)/2}\equiv \left(\frac{a}{p}\right)(\mathrm{mod}p).$$

This holds even if $p\mid a$.

(d) Use (c) to prove Theorem 3.62(a), that is, prove that

$$\left(\frac{-1}{p}\right)=\{\begin{array}{ll}1& \text{if }p\equiv 1(\mathrm{mod}4),\\ -1& \text{if }p\equiv 3(\mathrm{mod}4).\end{array}$$

3.38

Prove that the three parts of the quadratic reciprocity theorem (Theorem 3.62) are equivalent to the following three concise formulas, where $p$ and $q$ are odd primes:

(a)

$$\left(\frac{-1}{p}\right)=(-1{)}^{(p-1)/2}.$$

(b)

$$\left(\frac{2}{p}\right)=(-1{)}^{(p^2-1)/8}.$$

(c)

$$\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1{)}^{\frac{p-1}{2}\cdot \frac{q-1}{2}}.$$

3.39

Let $p$ be a prime satisfying $p\equiv 3(\mathrm{mod}4)$.

(a) Let $a$ be a quadratic residue modulo $p$. Prove that the number

$$b\equiv a^{(p+1)/4}(\mathrm{mod}p)$$

has the property that $b^2\equiv a(\mathrm{mod}p)$. Hint: Write $(p+1)/2$ as $1+(p-1)/2$ and use Exercise 3.37. This gives an easy way to take square roots modulo $p$ for primes that are congruent to $3$ modulo $4$.

(b) Use (a) to compute the following square roots modulo $p$. Be sure to check your answers.

(i) Solve $b^2\equiv 116(\mathrm{mod}587)$.

(ii) Solve $b^2\equiv 3217(\mathrm{mod}8627)$.

(iii) Solve $b^2\equiv 9109(\mathrm{mod}10663)$.

3.40

Let $p$ be an odd prime, let $g\in {\mathbb{F}}_p^{\ast }$ be a primitive root, and let $h\in {\mathbb{F}}_p^{\ast }$. Write $p-1=2^{s}m$ with $m$ odd and $s\ge 1$, and write the binary expansion of ${\log }_g(h)$ as

$${\log }_g(h)={ϵ}_0+2{ϵ}_1+4{ϵ}_2+8{ϵ}_3+\cdots \text{with }{ϵ}_0,{ϵ}_1,\dots \in \{0,1\}.$$

Give an algorithm that generalizes Example 3.69 and allows you to rapidly compute ${ϵ}_0,{ϵ}_1,\dots ,{ϵ}_{s-1}$, thereby proving that the first $s$ bits of the discrete logarithm are insecure. You may assume that you have a fast algorithm to compute square roots in ${\mathbb{F}}_p^{\ast }$, as provided for example by Exercise 3.39(a) if $p\equiv 3(\mathrm{mod}4)$. Hint: Use Example 3.69 to compute the $0$th bit, take the square root of either $h$ or $g^{-1}h$, and repeat.

3.41

Let $p$ be a prime satisfying $p\equiv 1(\mathrm{mod}3)$. We say that $a$ is a cubic residue modulo $p$ if $p\nmid a$ and there is an integer $c$ satisfying $a\equiv c^3(\mathrm{mod}p)$.

(a) Let $a$ and $b$ be cubic residues modulo $p$. Prove that $ab$ is a cubic residue modulo $p$.

(b) Give an example to show that, unlike the case with quadratic residues, it is possible for none of $a$, $b$, and $ab$ to be a cubic residue modulo $p$.

(c) Let $g$ be a primitive root modulo $p$. Prove that $a$ is a cubic residue modulo $p$ if and only if $3\mid {\log }_g(a)$, where ${\log }_g(a)$ is the discrete logarithm of $a$ to the base $g$.

(d) Suppose instead that $p\equiv 2(\mathrm{mod}3)$. Prove that for every integer $a$ there is an integer $c$ satisfying $a\equiv c^3(\mathrm{mod}p)$. In other words, if $p\equiv 2(\mathrm{mod}3)$, show that every number is a cube modulo $p$.

Section 3.10. Probabilistic Encryption and the Goldwasser-Micali Cryptosystem

3.42

Perform the following encryptions and decryptions using the Goldwasser-Micali public key cryptosystem (Table 3.9).

(a) Bob’s public key is the pair $N=1842338473$ and $a=1532411781$. Alice encrypts $3$ bits and sends Bob the ciphertext blocks

$$1794677960,525734818,420526487.$$

Decrypt Alice’s message using the factorization

$$N=pq=32411\cdot 56843.$$

(b) Bob’s public key is $N=3149$ and $a=2013$. Alice encrypts $3$ bits and sends Bob the ciphertext blocks $2322$, $719$, and $202$. Unfortunately, Bob used primes that are much too small. Factor $N$ and decrypt Alice’s message.

(c) Bob’s public key is $N=781044643$ and $a=568980706$. Encrypt the $3$ bits $1,1,0$ using, respectively, the three random values

$$r=705130839,r=631364468,r=67651321.$$

3.43

Suppose that the plaintext space $\mathcal{M}$ of a certain cryptosystem is the set of bit strings of length $2b$. Let $e_k$ and $d_k$ be the encryption and decryption functions associated with a key $k\in \mathcal{K}$. This exercise describes one method of turning the original cryptosystem into a probabilistic cryptosystem. Most practical cryptosystems that are currently in use rely on more complicated variants of this idea in order to thwart certain types of attacks. See Sect. 8.6 for further details.

Alice sends Bob an encrypted message by performing the following steps:

1. Alice chooses a $b$-bit message $m^{\prime }$ to be encrypted.
2. Alice chooses a string $r$ consisting of $b$ random bits.
3. Alice sets $m=r\Vert (r\oplus m^{\prime })$, where $\Vert$ denotes concatenation and $\oplus$ denotes exclusive or (see Sect. 1.7.4). Notice that $m$ has length $2b$ bits.
4. Alice computes $c=e_k(m)$ and sends the ciphertext $c$ to Bob.

(a) Explain how Bob decrypts Alice’s message and recovers the plaintext $m^{\prime }$. We assume, of course, that Bob knows the decryption function $d_k$.

(b) If the plaintexts and the ciphertexts of the original cryptosystem have the same length, what is the message expansion ratio of the new probabilistic cryptosystem?

(c) More generally, if the original cryptosystem has a message expansion ratio of $\mu$, what is the message expansion ratio of the new probabilistic cryptosystem?