Math 1580 — HW Solutions

Return to Math 1580 Home Page
\( \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*}
Return to Math 1580 Home Page