# Math 1580 — HW Solutions

$$\def\ZZ{{\mathbb{Z}}} \def\FF{{\mathbb{F}}} \def\a{\alpha} \def\b{\beta} \def\g{\gamma} \def\d{\delta}$$

Problem # 5.40: Table 5.18 gives some of the computations for the solution of the discrete logarithm problem $$11^t = 41387\quad\text{in \FF_{81799}} \qquad\qquad(5.62).$$ using Pollard's $$\rho$$~method. (It is similar to Table 5.11 in Example 5.52.) Use the data in Table 5.18 to solve (5.62).

Solution to Problem # 5.40: \begin{gather*} x_{308} = x_{154} = 15386\quad\text{in $\FF_{81799}$.} \\ \a_{154} = 81756,\qquad \b_{154} = 9527,\qquad \g_{154} = 67782,\qquad\d_{154} = 28637. \\ 11^{81756}\cdot 41387^{9527} = 11^{67782}\cdot 41387^{28637} \quad\text{in $\FF_{81799}$.} \\ 11^{13974} = 41387^{19110}\quad\text{in $\FF_{81799}$.} \\ \gcd(19110,81798) = 6. \\ 81340 \cdot 19110 \equiv 6 \pmod{81798}. \\ 11^{13974\cdot 81340} = 11^{1136645160} = 11^{61950} = 41387^{6} \quad\text{in $\FF_{81799}$.} \\ \frac{61950}{6} = 10325,\qquad \frac{81798}{6} = 13633. \\ \log_{11}(41387) \in \{10325 + 13633 \cdot k : 0 \le k < 6 \} \\ = \{10325,23958,37591,51224,64857,78490\}. \\ 11^{10325} = 73192,\quad 11^{23958} = 40412,\quad 11^{37591} = 49019, \quad 11^{51224} = 8607,\\ \boxed{11^{64857} = 41387}, \quad 11^{78490} = 32780. \\ \end{gather*}

Problem # 5.41: Table 5.19 gives some of the computations for the solution of the discrete logarithm problem $$7^t = 3018\quad\text{in \FF_{7963}} \qquad\qquad(5.63)$$ using Pollard's $$\rho$$ method. (It is similar to Table 5.11 in Example 5.52.) Extend Table 5.19 until you find a collision (we promise that it won't take too long) and then solve (5.63).

Solution to Problem # 5.41: Extending the table:

 $$i$$ $$x_i$$ $$y_i$$ $$\a_i$$ $$\b_i$$ $$\g_i$$ $$\d_i$$ 87 1329 1494 6736 7647 3148 3904 88 1340 1539 6737 7647 3150 3904 89 1417 4767 6738 7647 6302 7808 90 1956 1329 6739 7647 4642 7655 91 5729 1417 6740 7647 4644 7655 92 2449 5729 6740 7648 4646 7655 93 1217 1217 6741 7648 4647 7656 Table 5.19 (extended)
This yields a collision, and then we compute \begin{gather*} x_{186} = x_{93} = 1217\quad\text{in $\FF_{7963}$.} \\ \a_{93} = 6741,\qquad \b_{93} = 7648,\qquad \g_{93} = 4647,\qquad\d_{93} = 7656. \\ 7^{6741}\cdot 3018^{7648} = 7^{4647}\cdot 3018^{7656} \quad\text{in $\FF_{7963}$.} \\ 7^{2094} = 3018^{8}\quad\text{in $\FF_{7963}$.} \\ 7^{2094} = 3018^{8}\quad\text{in $\FF_{7963}$.} \\ \gcd(8,7962) = 2. \\ 6967 \cdot 8 \equiv 2 \pmod{7962}. \\ 7^{2094\cdot 6967} = 7^{14588898} = 7^{2514} = 3018^{2} \quad\text{in $\FF_{7963}$.} \\ \frac{2514}{2} = 1257,\qquad \frac{7962}{2} = 3981. \\ \log_{7}(3018) \in \{1257 + 3981 \cdot k : 0 \le k < 2 \} = \{1257,5238\}. \\ 7^{1257} = 4945,\quad \boxed{7^{5238} = 3018}. \\ \end{gather*}