Math 1580 - Solutions to Selected HW Problems

Problem # 1.18: Suppose that \(g^a\equiv1\pmod m\) and \(g^b\equiv1\pmod m\). Prove that \[ g^{\gcd(a,b)} \equiv 1 \pmod{m}. \]

Solution: Whenever you see a problem that involves the gcd, one thing you should think about is the extended Euclidean algorithm. This says that there are integers \(u\) and \(v\) that are solutions to the equation \[ au+bv=\gcd(a,b). \] So the first thing we do is raise both sides of the congruence \(g^a\equiv1\pmod m\) to the \(u\)'th power and raise both sides of the congruence \(g^b\equiv1\pmod m\) to the \(v\)'th power. This gives \[ g^{au}\equiv 1^u\equiv 1\pmod{m} \quad\hbox{and}\quad g^{bv}\equiv 1^v\equiv 1\pmod{m}. \] Multiplying these two congruences gives \[ g^{au+bv}\equiv1\pmod{m}. \] But \(au+bv=\gcd(a,b)\), so we get the desired result \[ g^{\gcd(a,b)}\equiv1\pmod{m}. \] (An additional comment: One of \(u\) or \(v\) will be negative. Suppose for example that \(u\) is negative. Then we use \(g^u \equiv (g^{-1})^{-u}\pmod{m}\), where \(g^{-1}\) is the inverse of \(g\) modulo \(m\).

Problem # 1.29: Let \(p\) be a prime. Prove that \(\hbox{ord}_p\) has the following properties.
(a) \(\hbox{ord}_p(ab)=\hbox{ord}_p(a)+\hbox{ord}_p(b)\).
(b) \(\hbox{ord}_p(a+b)\ge\min \{\hbox{ord}_p(a),\hbox{ord}_p(b)\}\).
(c) If \(\hbox{ord}_p(a)\ne\hbox{ord}_p(b)\), then \(\hbox{ord}_p(a+b)=\min \{\hbox{ord}_p(a),\hbox{ord}_p(b)\}\).
Solution: Most people got this problem, but in doing (c), many people did more work than necessary. For (c) the assumption is that \(\hbox{ord}_p(a)\ne\hbox{ord}_p(b)\), so there are two cases, either \[ \hbox{ord}_p(a)>\hbox{ord}_p(b) \quad\hbox{or}\quad \hbox{ord}_p(a)<\hbox{ord}_p(b). \] Many people wrote out the proof twice, once for each case. It's less work to say that since \(a\) and \(b\) appear symmetrically in this problem, we can always switch them if necessary, so it's enough to do just one of the cases, say \(\hbox{ord}_p(a)>\hbox{ord}_p(b)\).

So we can assume that \(\hbox{ord}_p(a)>\hbox{ord}_p(b)\). This means that \(a=p^iA\) and \(b=p^jB\) with \(i>j\) and with \(p\) not dividing \(A\) or \(B\). Then \[ a+b = p^iA+p^jB = p^j(p^{i-j}A+B). \] Since \(i>j\) and \(p\nmid B\), we see that \(p\nmid(p^{i-j}A+B)\), so \(\hbox{ord}_p(a+b)=j=\hbox{ord}_p(b)=\min \{\hbox{ord}_p(a),\hbox{ord}_p(b)\}\).

Problem # 3.9: A decryption exponent for an RSA public key \((N,e)\) is an integer \(d\) with the property that \(a^{de}\equiv a\pmod{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\).
Solution: (a) Let \(e_1,e_2,\ldots,e_n\) be a bunch of random encryption exponents, and suppose that Eve uses her magic box to create decryption exponents \(d_1,d_2,\ldots,d_n\). The numbers \(K\) with the property that \(a^K\equiv a\pmod{N}\) for all \(a\) satisfying \(\gcd(a,N)=1\) are numbers satisfying \[ K\equiv 1 \left(\bmod\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}\right). \] Thus \(d_ie_i-1\) is a multiple of \((p-1)(q-1)/\gcd(p-1,q-1)\) for all \(1\le i\le n\). Assuming that the \(e_i\)'s are reasonably random, Eve will find that \[ T = \gcd(d_1e_1-1,d_2e_2-1,d_3e_3-1,\ldots,d_ne_n-1) \] is equal to a small multiple of \[ \frac{(p-1)(q-1)}{\gcd(p-1,q-1)}. \] Next Eve uses the fact that \(\gcd(p-1,q-1)\) is even and tends to be fairly small. So she first assumes that \(T = (p-1)(q-1)/2\) and uses this to compute \(R=N+1-(p-1)(q-1)=N+1-2T\). If she is right about the value of \(T\), then \(R\) will equal \(p+q\), and she can recover \(p\) and \(q\) by factoring \(x^2-Tx+N\). If this doesn't work, she repeats the process with \(R=N+1-3T\), \(R=N+1-4T\), etc. Continuing in this fashion, she should recover \(p\) and \(q\) fairly quickly.

Eve can save a bit of time in finding the right multiple of \(T\). The idea is that \(N+1-kT\) should equal \(p+q\), and in practice \(p\) and \(q\) will have more or less the same order of magnitude. So Eve wants \(N+1-kT\approx 2\sqrt{N}\), which means that she should take \(k\approx (N+1-2\sqrt{N})/T\).

(b) \begin{align*} \gcd(16784693\cdot 10988423-1,11514115\cdot 25910155-1) & = \gcd(184437306609138,298332504337824) \\ & = 19368558 \end{align*} First Eve tries \(N + 1 - 1\cdot\gcd = 19381152\), but \(x^2 - 19381152x+38749709\) does not factor. (Its roots are not integers, they contain square roots.) Next she tries \(N + 1 - 2\cdot\gcd = 12594\), and this time she finds that \(x^2 - 12594x+38749709=(x - 7247)(x - 5347)\). Hence \(N=38749709=7247\cdot 5347\).

Problem # 7.7: Suppose that Samantha is using the ElGamal signature scheme and that she is careless and uses the same ephemeral key \(e\) to sign two documents \(D\) and \(D'\).
(a) Explain how Eve can tell at a glance whether Samantha has made this mistake.
(b) If the signature on \(D\) is \((S_1,S_2)\) and the signature on \(D'\) is \((S_1',S_2')\), explain how Eve can recover \(s\), Samantha's private signing key.
(c) Apply your method from (b) to the following example and recover Samantha's signing key \(s\), where Samantha is using the prime \(p=348149\), base \(g=113459\), and verification key \(v=185149\). \begin{align*} D &= 153405, &S_1 &= 208913, &S_2 &= 209176, \\ D' &= 127561, &S_1' &= 208913, &S_2' &= 217800. \end{align*} Solution: (a) Since \(S_1\equiv g^e\) and \(S_1'=g^{e'}\), Eve can check if the two signatures used the same ephemeral key by checking if \(S_1=S_1'\).

(b) Using discrete logarithms to the base \(g\), the verification conditions are \begin{align*} S_1\log(v) + S_2\log(S_1) \equiv D \pmod{p-1}, \\ S_1'\log(v) + S_2'\log(S_1') \equiv D' \pmod{p-1}. \end{align*} Since \(S_1=S_1'\) from (a), this becomes \begin{align*} S_1s + S_2\log(S_1) \equiv D \pmod{p-1}, \\ S_1s + S_2'\log(S_1) \equiv D' \pmod{p-1}, \end{align*} where \(s=\log(v)\) is Samantha's secret signing key. Taking \(S_2'\) times the first congruence and subtracting \(S_2\) times the second congruence, we obtain \[ S_1(S_2'-S_2)s \equiv S_2'D-S_2D' \pmod{p-1}. \] For notational convenience we write this congruence as \[ As \equiv B \pmod{p-1}, \] where we know the values of \(A\) and \(B\). If \(\gcd(A,p-1)=1\), we can solve uniquely for \(s\). In general, if \(\gcd(A,p-1)>1\) (it's unlikely to be too large), then there are \(\gcd(A,p-1)\) solutions for \(s\), and after computing them, we can decide which one is correct by checking which one yields \(g^s\equiv v\pmod{p}\).

(c) From (b) we begin by computing \begin{align*} A &\equiv S_1(S_2'-S_2) \equiv 347960 \pmod{p-1},\\ B &\equiv S_2'D-S_2D' \equiv 252868 \pmod{p-1}. \end{align*} We need to solve \(As\equiv B\pmod{p-1}\), so we need to solve \[ 347960s\equiv 252868\pmod{348148}. \] This congruence has several solutions. More precisely, since \(\gcd(347960,348148)=4\) and \(4\mid 252868\), we divide through by \(4\) to get \[ 86990s\equiv 63217\pmod{87037}. \] Then \(\gcd(86990,87037)=1\), so we can solve this congruence. The solution is \[ s \equiv 72729 \pmod{87037}. \] Adding on multiples of \((p-1)/4=87037\) yields the four solutions \[ s\equiv 72729,\,159766,\,246803,\,333840\pmod{348148} \] to the original congruence. We can pick out which solution is correct from the relation \(g^s\equiv v\pmod{p}\), i.e., the correct value of \(s\) should satisfy \[ 113459^s\equiv 185149 \pmod{348149}. \] We compute \begin{align*} 113459^{72729}&\equiv 185149 \pmod{348149},\\ 113459^{159766}&\equiv137653 \pmod{348149},\\ 113459^{246803}&\equiv163000 \pmod{348149},\\ 113459^{333840}&\equiv210496 \pmod{348149}. \end{align*} Hence Samantha's secret signing key is \[ s = 72729. \]

Problem # 6.27: Alice and Bob agree to communicate using the NTRU cryptosystem with \[ (N,p,q) = (7,2,37). \] Alice's private key is \[ \mathbf{f}(x) = x + x^{3} + x^{6}\qquad\text{and}\qquad \mathbf{F}_2(x) = 1 + x + x^{4} + x^{5} + x^{6}. \] (You can check that \(\mathbf{f}\star\mathbf{F}_2\equiv1\pmod{2}\).) Alice receives the ciphertext \[ \mathbf{e}(x) = 1 + 3x + 3x^{2} + 4x^{3} + 4x^{4} + x^{5} + 35x^{6} \] from Bob. Decipher the message and find the plaintext.
Solution: Alice first computes \[ \mathbf{a} \equiv \mathbf{f}\star \mathbf{e} \equiv 5 + 5x + 5x^{2} + 8x^{3} + 8x^{4} + 5x^{5} + 6x^{6}\pmod{37}. \] Then she computes \begin{align*} \mathbf{F}_2\star \mathbf{a} & = 29 + 31x + 31x^{2} + 32x^{3} + 32x^{4} + 29x^{5} + 26x^{6} \\ &\equiv 1 + x + x^{2} + x^{5}\pmod{2}. \end{align*} The plaintext is \(\mathbf{m} = 1 + x + x^{2} + x^{5}\).

Problem # 6.28: Alice and Bob decide to communicate using the NTRU cryptosystem with parameters \((N,p,q)=(7,2,29)\). Alice's public key is \[ \mathbf{h}(x) = 23 + 23x + 23x^{2} + 24x^{3} + 23x^{4} + 24x^{5} + 23x^{6}. \] Bob sends Alice the plaintext message \(\mathbf{m}(x) = 1 + x^{5}\) using the ephemeral key \(\mathbf{r}(x) = 1 + x + x^{3} + x^{6}\).

(a) What ciphertext does Bob send to Alice?

(b) Alice's secret key is \(\mathbf{f}(x) = 1 + x + x^{2} + x^{4} + x^{5}\) and \(\mathbf{F}_2(x) = 1 + x^{5} + x^{6}\). Check your answer in (a) by using \(\mathbf{f}\) and \(\mathbf{F}_2\) to decrypt the message.
Solution: (a) \(\mathbf{c} \equiv 2\mathbf{r}\star \mathbf{h}+\mathbf{m}\equiv 11 + 12x + 12x^{2} + 12x^{3} + 14x^{4} + 13x^{5} + 14x^{6}\pmod{29}\).

(b) First compute \[ \mathbf{b} \equiv \mathbf{f}\star \mathbf{c} \equiv 4 + 5x + 4x^{2} + 5x^{3} + 5x^{4} + 4x^{5} + 7x^{6}\pmod{37}. \] Then compute \begin{align*} \mathbf{F}\star \mathbf{b} & = 13 + 14x + 14x^{2} + 14x^{3} + 16x^{4} + 15x^{5} + 16x^{6} \\ &\equiv 1 + x^{5}\pmod{2}. \end{align*} This agrees with the plaintext.

Problem # 6.49:
Erratum: The modulus should be \(q=67\), not \(q=97\). So the public parameters for this problem are \((N,p,q,d)=(11,3,67,3)\).

Alice and Bob communicate using the NTRU cryptosystem with public parameters \((N,p,q,d)=(11,3,97,3)\). Alice's public key is \[ \mathbf{h} = 39+ 9x+ 33x^2+52x^3+58x^4+11x^5+38x^6+6x^7+x^8+48x^9+41x^{10}. \] Apply the LLL algorithm to the associated NTRU lattice to find an NTRU private key \((\mathbf{f},\mathbf{g})\) for \(\mathbf{h}\). Check your answer by verifying that \(\mathbf{g}\equiv\mathbf{f}\star\mathbf{h}\pmod{q}\). Use the private key to decrypt the ciphertext \[ \mathbf{e} = 52+ 50x+ 50x^2 + 61x^3 + 61x^4 + 7x^5 + 53x^6 + 46x^7 + 24x^8 + 17x^9 + 50x^{10}. \]
Solution: We apply LLL to the 22 dimensional NTRU lattice \(L_\mathbf{h}^{NTRU}\) associated to \(\mathbf{h}\). It requires 322 swaps and returns the LLL reduced the matrix \[ \tiny \left[\begin{array}{*{22}{@{\hspace{2pt}}c@{\hspace{2pt}}}} {-1}&{-1}&{-1}&{0}&{0}&{-1}&{0}&{1}&{0}&{1}&{1} &{1}&{1}&{-1}&{0}&{0}&{-1}&{-1}&{0}&{1}&{0}&{-1}\cr {1}&{-1}&{-1}&{-1}&{0}&{0}&{-1}&{0}&{1}&{0}&{1} &{-1}&{1}&{1}&{-1}&{0}&{0}&{-1}&{-1}&{0}&{1}&{0}\cr {0}&{1}&{0}&{0}&{0}&{1}&{0}&{1}&{-1}&{0}&{-2} &{0}&{-1}&{0}&{0}&{-1}&{1}&{1}&{0}&{-1}&{1}&{0}\cr {0}&{1}&{0}&{0}&{0}&{0}&{-2}&{1}&{-1}&{1}&{1} &{0}&{1}&{0}&{1}&{0}&{0}&{0}&{0}&{-1}&{1}&{-1}\cr {0}&{1}&{1}&{-1}&{-1}&{-1}&{0}&{0}&{-1}&{0}&{1} &{1}&{0}&{-1}&{1}&{1}&{-1}&{0}&{0}&{-1}&{-1}&{0}\cr {0}&{0}&{2}&{1}&{0}&{-1}&{0}&{0}&{1}&{1}&{-1} &{1}&{0}&{1}&{0}&{0}&{0}&{1}&{1}&{0}&{-1}&{0}\cr {-1}&{0}&{0}&{0}&{-1}&{0}&{-1}&{1}&{0}&{2}&{0} &{1}&{0}&{0}&{1}&{-1}&{-1}&{0}&{1}&{-1}&{0}&{0}\cr {1}&{-1}&{1}&{1}&{0}&{1}&{0}&{0}&{0}&{0}&{-2} &{0}&{-1}&{1}&{-1}&{0}&{1}&{0}&{1}&{0}&{0}&{0}\cr {-1}&{0}&{2}&{1}&{0}&{1}&{-1}&{1}&{0}&{0}&{-1} &{0}&{0}&{0}&{0}&{0}&{0}&{1}&{2}&{-1}&{0}&{0}\cr {0}&{0}&{0}&{0}&{-1}&{0}&{0}&{-1}&{-1}&{0}&{-2} &{0}&{-2}&{0}&{0}&{-1}&{0}&{0}&{0}&{-1}&{-1}&{0}\cr {1}&{1}&{1}&{-1}&{1}&{1}&{0}&{0}&{-2}&{0}&{0} &{0}&{-1}&{0}&{1}&{1}&{0}&{1}&{0}&{-1}&{1}&{0}\cr {-4}&{8}&{0}&{2}&{-7}&{0}&{1}&{-8}&{13}&{-4}&{-2} &{4}&{-9}&{-1}&{0}&{7}&{-7}&{-6}&{1}&{2}&{18}&{-10}\cr {9}&{2}&{3}&{-7}&{-1}&{0}&{-9}&{12}&{-4}&{-4}&{-3} &{-10}&{0}&{0}&{7}&{-6}&{-5}&{1}&{1}&{17}&{-11}&{4}\cr {-6}&{-2}&{-5}&{3}&{13}&{2}&{0}&{1}&{5}&{-11}&{-1} &{16}&{-3}&{9}&{5}&{3}&{2}&{-8}&{-5}&{-14}&{-4}&{-2}\cr {-3}&{7}&{2}&{0}&{8}&{-12}&{3}&{3}&{4}&{-8}&{-1} &{0}&{-7}&{7}&{6}&{-1}&{-2}&{-17}&{12}&{-5}&{9}&{1}\cr {-9}&{7}&{7}&{-8}&{-14}&{2}&{-10}&{-8}&{-2}&{1}&{-1} &{4}&{-3}&{1}&{-6}&{2}&{0}&{3}&{-1}&{21}&{12}&{-1}\cr {7}&{1}&{0}&{9}&{-12}&{4}&{4}&{3}&{-9}&{-2}&{-3} &{-7}&{6}&{5}&{-1}&{-1}&{-17}&{11}&{-4}&{10}&{0}&{0}\cr {-2}&{-3}&{9}&{2}&{3}&{-6}&{-1}&{0}&{-8}&{13}&{-4} &{-11}&{4}&{-8}&{0}&{0}&{8}&{-6}&{-5}&{1}&{2}&{18}\cr {13}&{3}&{-4}&{1}&{3}&{4}&{-12}&{-2}&{9}&{-14}&{-2} &{14}&{-2}&{-7}&{2}&{-10}&{-12}&{3}&{3}&{8}&{4}&{-4}\cr {-1}&{-5}&{11}&{1}&{6}&{2}&{5}&{-3}&{-13}&{-2}&{0} &{5}&{14}&{4}&{2}&{-16}&{3}&{-9}&{-5}&{-3}&{-2}&{8}\cr {-6}&{11}&{0}&{6}&{2}&{5}&{-3}&{-11}&{-3}&{1}&{-2} &{15}&{4}&{1}&{-16}&{2}&{-9}&{-5}&{-3}&{-2}&{9}&{4}\cr {-3}&{-3}&{-3}&{9}&{2}&{1}&{-8}&{-1}&{0}&{-7}&{13} &{18}&{-10}&{5}&{-9}&{0}&{0}&{7}&{-7}&{-5}&{1}&{0}\cr \end{array}\right]. \] The top row is \[ (-1, -1, -1, 0, 0, -1, 0, 1, 0, 1, 1, 1, 1, -1, 0, 0, -1, -1, 0, 1, 0, -1), \] which gives the private key polynomials \begin{align*} \mathbf{f}(x) &= -1 -x -x^2 -x^5 +x^7 +x^9 +x^{10} \\ \mathbf{g}(x) &= 1 +x -x^2 -x^5 -x^6+ x^8 -x^{10} . \end{align*}

To decipher the message, we compute \[ \mathbf{a} \equiv \mathbf{f}\star\mathbf{e} \equiv -11 -13x -1x^2 +3x^3 -4x^4 +2x^5 +16x^6 +4x^7 +4x^9 -2x^{10} \pmod{q}. \] Then we use \[ \mathbf{f}^{-1} \equiv -1 + x -x^3 +x^4 -x^6 +x^7 -x^8 -x^9 +x^{10} \pmod{3} \] to compute the plaintext \[ \mathbf{m} \equiv \mathbf{a}\star\mathbf{f}^{-1} \equiv 1 -x -x^2 -x^3 -x^4 +x^7 +x^{10} \pmod{3}. \] In vector form, \(\mathbf{m}=(1, -1, -1, -1, -1, 0, 0, 1, 0, 0, 1)\).

Problem # 6.50: (a) Suppose that \(k\) is a \(10\) digit integer, and suppose that when \(\sqrt{k}\) is computed, the first 15 digits after the decimal place are \(418400286617716\). Find the number \(k\). (Hint Reformulate it as a lattice problem.)
(b) More generally, suppose that you know the first \(d\)-digits after the decimal place of \(\sqrt{K}\). Explain how to set up a lattice problem to find \(K\).
Solution: We do (b) first, then illustrate the general idea by doing (a). Let \(\alpha\) be the \(d\)-digit number consisting of the first \(d\) digits after the decimal place of \(\sqrt{K}\). If we let \(\beta=\alpha/10^d\), then we can write \[ \sqrt{K} \approx J + \beta\qquad\text{for some \(J\in\mathbb{Z}\).} \] There are two unknowns here, \(K\) and \(J\), and all that we know is that they are both integers. Squaring both sides gives \[ K \approx J^2 + 2J\beta + \beta^2. \] Thus there are integers \(A\) and \(B\) satisfying \[ \beta^2 + A\beta + B \approx 0, \] namely \(A=2J\) and \(B=J^2-K\). Of course, we don't know \(A\) or \(B\), so we now describe a lattice reduction problem that finds a (quadratic) polynomial with small integer coefficients that has a given decimal number as an (approximate) root. Once we find \(A\) and \(B\), it is easy to recover \(K\) as \(K=\frac{1}{4}A^2-B\).

Let \(L\) be the lattice generated by the rows of the matrix \[ M = \begin{pmatrix} 1&0&t\\ 0&1&t\beta\\ 0&0&t\beta^2\\ \end{pmatrix}, \] where we will choose \(t\) later. Notice that \[ \begin{pmatrix} B & A & 1 \\ \end{pmatrix} \begin{pmatrix} 1&0&t\\ 0&1&t\beta\\ 0&0&t\beta^2\\ \end{pmatrix} = \begin{pmatrix} B & A & t(B+A\beta+\beta^2) \\ \end{pmatrix}. \] What we do is to choose \(t\) so that \(A\), \(B\), and \(t(B+A\beta+\beta^2)\) are all about the same size. Then the vector \((B , A , t(B+A\beta+\beta^2))\) will be a small vector in the lattice generated by the rows of \(M\). So we can hope that LLL applied to this lattice will give this small vector. In fact, our target vector may not be the smallest vector in the lattice, so we may need to try small linear combinations of the LLL basis vectors until we find \((B , A , t(B+A\beta+\beta^2))\).

A more careful analysis, which we leave to the reader, shows that \(A\) and \(B\) are both approximately equal to \(2\sqrt{K}\), while \(B+A\beta+\beta^2\) is approximately equal to \(10^{-d}\sqrt{K}\), so taking \(t\approx10^d\) should work well.

(a) We are told that \(K\) is a 10 digit number, and we are given \(d=15\) digits after the decimal place of \(\sqrt{K}\), namely \(\beta=0.418400286617716\). We take \(t=10^{15}\), so \(t\beta=418400286617716\) and \(t\beta^2=175058799841786.8985151250567\). We can round this off, so we take the lattice generated by the rows of the matrix \[ \begin{pmatrix} 1&0&10^{15}\\ 0&1&418400286617716\\ 0&0&175058799841787\\ \end{pmatrix}. \] Applying LLL gives the matrix \[ \begin{pmatrix} -12420&9695&-27668\\ -4562&50882&35875\\ 80169&19398&-39511\\ \end{pmatrix} \] Call the rows of this matrix \(\mathbf{v}_1\), \(\mathbf{v}_2\), and \(\mathbf{v}_3\). We note that \(A=2L\) has to be even, so \(\mathbf{v}_1\) cannot be \((B,A,*)\). If we try setting \(\mathbf{v}_2=(B,A,*)\), then \(B=-4562\) and \(A=50882\), then \(K=\frac{1}{4}A^2-B=647249043\). This \(K\) has \(\sqrt{K}=25441.08966\cdots\), which is not what we want.

So we try various small linear combinations of \(\mathbf{v}_1\), \(\mathbf{v}_2\), and \(\mathbf{v}_3\). When we get to \[ 2\mathbf{v}_1 + \mathbf{v}_2 = (-29402, 70272, -19461), \] we obtain \(A=70272\), \(B=-29402\), \(K=\frac{1}{4}A^2-B=1234567898\), which yields \(\sqrt{K}=35136.41840028661771627694\). Eureka! We have found a 10 digit number \(K\) whose first 15 digits after the decimal place are the desired digits.

Problem # 3.28: 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.)
Solution:
(a) \(N =2^{100}\) : \(L(N) = 2^{24.73}\) steps takes 0.03 seconds.
(b) \(N =2^{250}\) : \(L(N) = 2^{43.12}\) steps takes 2.65 hours.
(c) \(N =2^{350}\) : \(L(N) = 2^{52.66}\) steps takes 82.24 days.
(d) \(N =2^{500}\) : \(L(N) = 2^{64.95}\) steps takes 1129.30 years.
(e) \(N =2^{750}\) : \(L(N) = 2^{82.26}\) steps takes \(10^{8.26}\) years.
(f) \(N =2^{1000}\) : \(L(N) = 2^{97.14}\) steps takes \(10^{12.74}\) years.
(g) \(N =2^{2000}\) : \(L(N) = 2^{144.48}\) steps takes \(10^{26.99}\) years.

Problem # 3.29: 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\bigl((\ln X)^\alpha\bigr)\).
(b) For every positive constant \(\beta\), no matter how small, \(L(X) =\mathcal{O}\bigl(X^\beta)\).
Solution: (a) We want to show that \(L(X)\ge(\ln X)^\alpha\) when \(X\) is large. Since the logarithm function is an increasing function, it suffices to show that \(\ln L(X) \ge \ln\bigl( (\ln X)^\alpha \bigr)\). Using laws of logarithms, this is equivalent to showing that \[ \sqrt{(\ln X)(\ln\ln X)} \ge \alpha \ln(\ln X). \] Dividing by \(\ln (\ln X)\), this is equivalent to showing that \[ \sqrt{\frac{\ln X}{\ln\ln X}} \ge \alpha \] when \(X\) is large. But it is clear that \[ \lim_{X\to\infty} \frac{\ln X}{\ln\ln X} = \infty, \] which gives us the desired result. If it's not clear to you that the limit is \(\infty\), use L'Hopital's rule to compute \[ \lim_{X\to\infty} \frac{\ln X}{\ln\ln X} = \lim_{X\to\infty} \frac{1/X}{1/(X\ln X)} = \lim_{X\to\infty} \ln X = \infty. \]
(b) Similarly, taking logs, we need to show that \[ \ln L(X) = \sqrt{(\ln X)(\ln\ln X)} \quad\text{is smaller than}\quad \ln(X^\beta) = \beta\ln X. \] Dividing both sides by \(\ln X\), this means showing that \[ \sqrt{\frac{\ln\ln X}{\ln X}} \le \beta \] when \(X\) is large. This is true, since (using the calculation in (a)) we have \[ \lim_{X\to\infty} \frac{\ln\ln X}{\ln X} = 0. \]

Problem # 3.33: Illustrate the quadratic sieve, as was done in Figure 3.3 (page 157), 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?
Solution: (a) We sieve the following values, as illustrated in the table given below:

• The congruence \(t^2\equiv493\equiv1\pmod{2}\) has solution \(t\equiv1\pmod{2}\), so we sieve \(2\) from \(F(23)\), \(F(25)\), \(F(27)\),... .
• The congruence \(t^2\equiv493\equiv1\pmod{3}\) has solutions \(t\equiv1\pmod{3}\) and \(t\equiv2\pmod{3}\), so first we sieve \(3\) from \(F(23)\), \(F(26)\), \(F(29)\),..., and then we sieve \(3\) from \(F(25)\), \(F(28)\), \(F(31)\),... .
• The congruence \(t^2\equiv493\equiv1\pmod{4}\) has solution \(t\equiv1\pmod{2}\), so we sieve another \(2\) from \(F(23)\), \(F(25)\), \(F(27)\),... .
• The congruence \(t^2\equiv493\equiv3\pmod{5}\) has no solutions.
• The congruence \(t^2\equiv493\equiv3\pmod{7}\) has no solutions.
• The congruence \(t^2\equiv493\equiv5\pmod{8}\) has no solutions.
• The congruence \(t^2\equiv493\equiv7\pmod{9}\) has solutions \(t\equiv4\pmod{9}\) and \(t\equiv5\pmod{9}\), so first we sieve another \(3\) from \(F(31)\) and then we sieve another \(3\) from \(F(23)\) and \(F(32)\).
• The congruence \(t^2\equiv493\equiv9\pmod{11}\) has solutions \(t\equiv3\pmod{11}\) and \(t\equiv8\pmod{11}\), so first we sieve \(11\) from \(F(25)\) and \(F(36)\) and then we sieve \(11\) from \(F(30)\).

Problem # 3.13: We stated that the number \(561\) is a Carmichael number, but we never checked that \(a^{561}\equiv a\pmod{561}\) for every value of \(a\).

(a) The number \(561\) factors as \(3\cdot11\cdot17\). First use Fermat's little theorem to prove that \[ a^{561}\equiv a\pmod{3},\quad a^{561}\equiv a\pmod{11},\quad\text{and}\quad a^{561}\equiv a\pmod{17} \] for every value of \(a\). Then explain why these three congruences imply that \(a^{561}\equiv a\pmod{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\)

Problem # 3.18: We noted in Section 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.20) 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 \[ P(N) =\frac{\text{number of primes between \(\frac12N\) and \(\frac32N\)}} {\text{number of integers between \(\frac12N\) and \(\frac32N\)}}, \] so \(P(N)\) represents the probability that an integer \(n\) in the interval \(\frac{1}{2}N\le n\le\frac{3}{2}N\) is a prime number}. Prove that \[ \lim_{N\to\infty} \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_1\lt c_2\). Bob chooses random numbers \(n\) in the interval \(c_1N\le n\le c_2N\). Keeping \(c_1\) and \(c_2\) fixed, let \(P(c_1,c_2;N)\) be the probability that an integer \(n\) in the interval \(c_1N\le n\le c_2N\) is a prime number. In the following formula, replace the \(XXXXX\) with a simple function of \(N\) so that the statement is true: \[ \lim_{N\to\infty} \frac{P(c_1,c_2;N)}{XXXXXX} = 1. \]
Solution: We will just write \(P(N)\), instead of \(P(c_1,c_2;N)\). \begin{align*} P(N) & = \frac{\text{# of primes between \(c_1N\) and \(c_2N\)}}{N} \\ &= \frac{\pi(c_2N)-\pi(c_2N)}{N} \\ &= \frac{c_2}{\ln(c_2N)} - \frac{c_1}{\ln(c_1N)} + o\left(\frac{1}{\ln(N)}\right) \quad\text{from the prime number theorem} \\ &= \frac{(c_2-c_1)\ln(N)+O(1)}{\ln(c_1N)\ln(c_2N)} + o\left(\frac{1}{\ln(N)}\right) \\ &= \frac{c_2-c_1}{\ln(N)} + o\left(\frac{1}{\ln(N)}\right). \end{align*} Hence \(P(N)\) divided by \((c_2-c_1)/\ln(N)\) goes to \(1\) as \(N\to\infty\), or equivalently, \[ \lim_{N\to\infty} \frac{P(N)}{1/\ln(N)} = c_2-c_1. \] For part (a), we have \(c_1=\frac{1}{2}\) and \(c_2=\frac{3}{2}\), so the limit is \(1\).

Return to the Math 158 Homework Page

Return to the Math 158 Home Page