Chapter 4

Let \(a, b \in \mathbb{Z}\) with \(a \geq b \geq 0,\) let \(d:=\operatorname{gcd}(a, b),\) and assume \(d>0\). Suppose that on input \(a, b\), Euclid's algorithm performs \(\lambda\) division steps, and computes the remainder sequence \(\left\\{r_{i}\right\\}_{i=0}^{\lambda+1}\) and the quotient sequence \(\left\\{q_{i}\right\\}_{i=1}^{\lambda}\) (as in Theorem 4.1 ). Now suppose we run Euclid's algorithm on input \(a / d, b / d\). Show that on these inputs, the number of division steps performed is also \(\lambda,\) the remainder sequence is \(\left\\{r_{i} / d\right\\}_{i=0}^{\lambda+1},\) and the quotient sequence is \(\left\\{q_{i}\right\\}_{i=1}^{\lambda} .\)

Let \(\lambda\) be a positive integer. Show that there exist integers \(a, b\) with \(a>b>0\) and \(\lambda \geq \log b / \log \phi\), such that Euclid's algorithm on input \(a, b\) performs at least \(\lambda\) divisions. Thus, the bound in Theorem 4.1 on the number of divisions is essentially tight.

This exercise looks at an alternative algorithm for computing \(\operatorname{gcd}(a, b),\) called the binary ged algorithm. This algorithm avoids complex operations, such as division and multiplication; instead, it relies only on subtraction, and division and multiplication by powers of \(2,\) which, assuming a binary representation of integers (as we are), can be very efficiently implemented using "right shift" and "left shift" operations. The algorithm takes positive integers \(a\) and \(b\) as input, and runs as follows: $$ \begin{array}{l} r \leftarrow a, r^{\prime} \leftarrow b, e \leftarrow 0 \\ \text { while } 2 \mid r \text { and } 2 \mid r^{\prime} \text { do } r \leftarrow r / 2, r^{\prime} \leftarrow r^{\prime} / 2, e \leftarrow e+1 \end{array} $$ repeat $$ \begin{array}{l} \text { while } 2 \mid r \text { do } r \leftarrow r / 2 \\ \text { while } 2 \mid r^{\prime} \text { do } r^{\prime} \leftarrow r^{\prime} / 2 \\ \text { if } r^{\prime}

Assume notation as in Theorem 4.3. Show that: (a) for all \(i=2, \ldots, \lambda,\) we have \(\left|t_{i}\right|<\left|t_{i+1}\right|\) and \(r_{i-1}\left|t_{i}\right|0,\) then \(\left|s_{\lambda+1}\right|=b / d\) and \(\left|t_{\lambda+1}\right|=a / d\).

One can extend the binary gcd algorithm discussed in Exercise 4.6 so that in addition to computing \(d=\operatorname{gcd}(a, b)\), it also computes \(s\) and \(t\) such that \(a s+b t=d\). Here is one way to do this (again, we assume that \(a\) and \(b\) are positive integers): $$ \begin{array}{l} r \leftarrow a, r^{\prime} \leftarrow b, e \leftarrow 0 \\ \text { while } 2 \mid r \text { and } 2 \mid r^{\prime} \text { do } r \leftarrow r / 2, r^{\prime} \leftarrow r^{\prime} / 2, e \leftarrow e+1 \\ \tilde{a} \leftarrow r, \tilde{b} \leftarrow r^{\prime}, s \leftarrow 1, t \leftarrow 0, s^{\prime} \leftarrow 0, t^{\prime} \leftarrow 1 \end{array} $$ repeat $$ \begin{array}{l} \text { while } 2 \mid r \text { do } \\ r \leftarrow r / 2 \end{array} $$ if \(2 \mid s\) and \(2 \mid t\) then \(s \leftarrow s / 2, t \leftarrow t / 2\) $$ \begin{array}{l} \text { while } 2 \mid r^{\prime} \text { do } \\ \qquad r^{\prime} \leftarrow r^{\prime} / 2 \end{array} \text { else } s \leftarrow(s+\tilde{b}) / 2, t \leftarrow(t-\tilde{a}) / 2 $$ if \(2 \mid s^{\prime}\) and \(2 \mid t^{\prime}\) then \(s^{\prime} \leftarrow s^{\prime} / 2, t^{\prime} \leftarrow t^{\prime} / 2\) $$ \text { else } s^{\prime} \leftarrow\left(s^{\prime}+\tilde{b}\right) / 2, t^{\prime} \leftarrow\left(t^{\prime}-\tilde{a}\right) / 2 $$ if \(r^{\prime}

In this exercise, you are to make the result of Theorem 2.17 effective. Suppose that we are given a positive integer \(n,\) two elements \(\alpha, \beta \in \mathbb{Z}_{n}^{*}\), and integers \(\ell\) and \(m,\) such that \(\alpha^{\ell}=\beta^{m}\) and \(\operatorname{gcd}(\ell, m)=1 .\) Show how to compute \(\gamma \in \mathbb{Z}_{n}^{*}\) such that \(\alpha=\gamma^{m}\) in time \(O\left(\operatorname{len}(\ell) \operatorname{len}(m)+(\operatorname{len}(\ell)+\operatorname{len}(m)) \operatorname{len}(n)^{2}\right)\).

In this exercise and the next, you are to analyze an "incremental Chinese remaindering algorithm." Consider the following algorithm, which takes as input integers \(a_{1}, n_{1}, a_{2}, n_{2}\) satisfying $$ 0 \leq a_{1}

Suppose we are given \(\alpha_{1}, \ldots, \alpha_{k} \in \mathbb{Z}_{n}^{*} .\) Show how to compute \(\alpha_{1}^{-1}, \ldots, \alpha_{k}^{-1}\) by computing one multiplicative inverse modulo \(n,\) and performing fewer than \(3 k\) multiplications modulo \(n .\) This result is useful, as in practice, if \(n\) is several hundred bits long, it may take \(10-20\) times longer to compute multiplicative inverses modulo \(n\) than to multiply modulo \(n\).

Let \(n, b \in \mathbb{Z}\) with \(0 \leq b

Using the decimal approximation \(\pi \approx 3.141592654\), apply Euclid's algorithm to calculate a rational number of denominator less than 1000 that is within \(10^{-6}\) of \(\pi\). Illustrate the computation with a table as in Fig. 4.1 .

Show that if a sequence \(\Psi\) is ultimately periodic, then it is \(\left(k^{*}, \ell^{*}\right)\) -periodic for some uniquely determined pair \(\left(k^{*}, \ell^{*}\right)\) for which the following holds: for every pair \((k, \ell)\) such that \(\Psi\) is \((k, \ell)\) -periodic, we have \(k^{*} \leq k\) and \(\ell^{*} \mid \ell\)

Let \(z\) be a real number whose decimal expansion is an ultimately periodic sequence. Show that \(z\) is rational.

Let \(z=s / t \in \mathbb{Q},\) where \(s\) and \(t\) are relatively prime integers with \(0 \leq s

This exercise develops a method to speed up RSA decryption. Suppose that we are given two distinct \(\ell\) -bit primes, \(p\) and \(q,\) an element \(\beta \in \mathbb{Z}_{n}\), where \(n:=p q,\) and an integer \(d,\) where \(1

Alice submits a bid to an auction, and so that other bidders cannot see her bid, she encrypts it under the public key of the auction service. Suppose that the auction service provides a public key for an RSA encryption scheme, with a modulus \(n\). Assume that bids are encoded simply as integers between 0 and \(n-1\) prior to encryption. Also, assume that Alice submits a bid that is a "round number," which in this case means that her bid is a number that is divisible by \(10 .\) Show how an eavesdropper can submit an encryption of a bid that exceeds Alice's bid by \(10 \%\), without even knowing what Alice's bid is. In particular, your attack should work even if the space of possible bids is very large.

To speed up RSA decryption, one might choose a small decryption exponent, and then derive the encryption exponent from this. This exercise develops a "small decryption exponent attack" on RSA. Suppose \(n=p q,\) where \(p\) and \(q\) are distinct primes with \(\operatorname{len}(p)=\operatorname{len}(q) .\) Let \(d\) and \(e\) be integers such that \(1