Chapter 2. Discrete Logarithms and Diffie-Hellman

Exercise (Câu 2.3)

Let \(g\) be a primitive root of \(\mathbb{F}_p\).

  1. Suppose that \(x = a\) and \(x = b\) are both integer solutions to the congruence \(g^x \equiv h\) (mod \(p\)). Prove that \(a \equiv b\) (mod \(p-1\)). Explain why this implies that the map (2.1) on page 64 is well-defined

  2. Prove that \(\log_g(h_1 h_2) = \log_g(h_1) + \log_g(h_2)\) for all \(h_1, h_2 \in \mathbb{F}^*_p\)

  3. Prove that \(\log_g(h^n) = n\log_g(h)\) for all \(h \in \mathbb{F}^{*}_p\) and \(n \in \mathbb{Z}\)

Các tính chất cơ bản của hàm Euler.

  1. Cả \(a\) and \(b\) là nghiệm của đồng dư \(g^x \equiv h\) (mod \(p\)) nên \(g^a \equiv h \pmod p\) và \(g^b \equiv h \pmod p\).

Suy ra ta có \(g^{-b} \equiv h^{-1} \pmod p\).

Ta nhân kết quả với đồng dư đầu thì được \(g^a g^{-b} \equiv h h^{-1} \equiv 1 \pmod p\), hay \(g^{a-b} \equiv 1 \pmod p\).

Do \(g\) là primitive root of \(\mathbb{F}_p\) tên ta có \(\phi(p) \mid (a-b)\), tương đương với \((p-1) \mid (a-b)\).

Như vậy \(a - b \equiv 0 \pmod{p-1}\) hay \(a \equiv b \pmod {p-1}\) (đpcm).

  1. Giả sử \(h_1 \equiv g^{x_1} \pmod p\) và \(h_2 \equiv g^{x_2} \pmod p\).

Suy ra \(x_1 = \log_g h_1\) và \(x_2 = \log_g h_2\) (1).

Do \(h_1 h_2 \equiv g^{x_1 + x_2} \pmod p\) nên \(x_1 + x_2 = \log_g(h_1 h_2)\) (2).

Từ (1) và (2), \(\log_g h_1 + \log_g h_2 = \log_g (h_1 h_2)\).

  1. tương tự (b).

Exercise (Câu 2.5)

Let \(p\) be an odd prime and let \(g\) be a primitive root modulo \(p\).

Prove that \(a\) has a square root modulo \(p\) if and only if its discrete logarithm \(\log_g(a)\) modulo \(p-1\) is even.

Ta có \(g^{p-1} \equiv 1 \pmod p\) do \(g\) là primitive root modulo \(p\).

Điều kiện đủ. Nếu \(a\) là số chính phương modulo \(p\) thì tồn tại số \(b\) sao cho \(b \equiv a^2 \pmod p\), suy ra

\[\log_g a = \log_g(b^2) = 2 \log_g b \pmod{p-1},\]

như vậy \(\log_ga\) chẵn.

Điều kiện cần. Nếu \(\log_g a\) modulo \(p-1\) chẵn.

Điều này xảy ra khi

\[\log_ga = 2\log_g b \pmod{p-1}\]

với số \(b \in \mathbb{F}_p\) nào đó, suy ra

\[\log_ga = \log_g (b^2) \pmod{p-1},\]

hay \(a \equiv b^2 \pmod{p-1}\).

Như vậy \(a\) có căn bậc hai modulo \(p-1\).

Exercise (Câu 2.10)

The exercise describes a public key cryptosystem that requires Bob and Alice to exchange several messages. We illustrate the system with an example.

Bob and Alice fix a publicly known prime \(p=32611\), and all of other numbers used are private.

Alice takes her message \(m=11111\), chooses a random exponent \(a=3589\), and sends the number \(u=m^a\) (mod \(p\)) \(=15950\) to Bob.

Bob chooses a random exponent \(b=4037\) and sends \(v=u^b\) (mod \(p\)) \(=15422\) back to Alice.

Alice then computes \(w=v^{15619} \equiv 27257\) (mod \(32611\)) and sends \(w=27257\) to Bob.

Finally, Bob computes \(w^{31883}\) (mod \(32611\)) and recovers the value \(11111\) of Alice's message.

  1. Explain why this algorithm works. In particular, Alice uses the numbers \(a=3589\) and 15619 as exponents. How are they related? Similarly, how are Bob's exponents \(b=4037\) and 31883 related?

  2. Formulate a general version of this cryptosystem, i.e., using variables, and show how it works in general.

  3. What is the disadvantage of this cryptosystem over Elgamal? (Hint. How many times must Alice and Bob exchange data?)

  4. Are there any advantages of this cryptosystem over Elgamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve the Diffie-Hellman problem?

  1. Ta có

\[3589 \cdot 15619 \equiv 4073 \cdot 31883 \equiv 1 \pmod{p-1}.\]

  1. Alice chọn \(a\) và \(a'\) sao cho \(aa' \equiv 1 \pmod{p-1}\).

Tương tự, Bob chọn \(b\) và \(b'\) sao cho \(bb' \equiv 1 \pmod{p-1}\).

Do đó ta có \(aa' = k(p-1)+1\) và \(bb' = l(p-1) + 1\).

\[\begin{split}& \Rightarrow v \equiv u^b \equiv (m^a)^b \equiv m^{ab} \pmod p \\ & \Rightarrow w \equiv v^{a'} \equiv (m^{ab})^{a'} \equiv m^{aa'b} \pmod p \\ & \Rightarrow w^{b'} \equiv m^{aa'bb'} \equiv m^{[k(p-1)+1]x[l(p-1)+1]} \equiv m^{D(p-1)+1} \equiv m \pmod p.\end{split}\]

Exercise (Câu 2.11)

The group \(S_3\) consists of the following six distinct elements

\[e, \sigma, \sigma^2, \tau, \sigma\tau, \sigma^2\tau\]

where \(e\) is the identity element and multiplication is performed using the rules

\[\sigma^3 = e, \quad \tau^2 = e, \quad \tau\sigma = \sigma^2\tau\]

Compute the following values in the group \(S_3\):

  1. \(\tau\sigma^2\)

  2. \(\tau(\sigma\tau)\)

  3. \((\sigma\tau)(\sigma\tau)\)

  4. \((\sigma\tau)(\sigma^2\tau)\)

Is \(S_3\) a commutative group?

\[\tau\sigma^2 = \tau\sigma\sigma = \sigma^2\tau\sigma = \sigma\sigma^2\tau = \sigma^3\tau = e\tau = \tau.\]
\[\tau(\sigma\tau)=(\tau\sigma)\tau = \sigma^2\tau\tau = \sigma^2\tau^2 = \sigma^2e = \sigma^2.\]
\[(\sigma\tau)(\sigma\tau) = \sigma(\tau\sigma)\tau = \sigma(\sigma^2\tau)\tau = \sigma^3\tau^2 = ee = e.\]
\[(\sigma\tau)(\sigma^2\tau) = (\sigma\tau)(\tau\sigma) = \sigma\tau^2\sigma=\sigma e \sigma = \sigma^2.\]

\(S_3\) không là nhóm giao hoán vì:

\[\sigma\tau = \sigma\tau, \quad \tau\sigma = \sigma^2\tau,\]

đây là hai phần tử phân biệt trong \(S_3\).

Exercise (Câu 2.12)

Let \(G\) be a group, let \(d \geqslant 1\) be an integer, and define a subset of \(G\) by

\[G[d] = \{g \in G: g^d = e\}\]

  1. Prove that if \(g\) is in \(G[d]\), then \(g^{-1}\) is in \(G[d]\)

  2. Suppose that \(G\) is commutative. Prove that is \(g_1\) and \(g_2\) are in \(G[d]\), then their product \(g_1 \star g_2\) is in \(G[d]\)

  3. Deduce that if \(G\) is commutative, then \(G[d]\) is a group.

  4. Show by an example that is \(G\) is not a commutative group, then \(G[d]\) need not be a group. (Hint. Use Exercise 2.11.)

  1. Vì \(g \star g^{-1} = e\) nên

\[\begin{split}& g \star e \star g^{-1} = e \\ \Rightarrow & g \star g \star g^{-1} \star g^{-1} = e \\ \Rightarrow & g^2 \star (g^{-1})^2 = e.\end{split}\]

Thực hiện thêm \(d-2\) lần nữa và ta nhận được

\[\begin{split}& g^d \star (g^{-1})^d = e \\ \Rightarrow & e \star (g^{-1})^2 = e \\ \Rightarrow & (g^{-1})^2 = e \\ \Rightarrow & g^{-1} \in G[d]\end{split}\]

  1. Ta có \(g_1^d = e\) and \(g_2^d = e\).

Do \(G\) là nhóm hoán vị nên \(g_1^d \star g_2^d = (g_1 \star g_2)^d\), suy ra \((g_1 \star g_2)^d = e \star e = e\).

Như vậy \(g_1 \star g_2 \in G[d]\).

  1. Từ câu (b), ta có với mọi \(g_1, g_2 \in G[d]\), thì \(g_1 \star g_2 \in G[d]\).

Do \(e\) là phần tử đơn vị của \(G\) nên cũng là phần tử đơn vị của \(G[d]\).

Từ câu (a) ta chứng minh được sự tồn tại của phần tử nghịch đảo.

Với \(a, b, c \in G[d]\) thì \(a^d = b^d = c^d = e\).

Ta có \(b^d \star c^d = (b \star c)^d\) do tính giao hoán, suy ra

\[\begin{split}a^d \star (b^d \star c^d) & = a^d \star (b \star c)^d = (a \star b \star c)^d \\ & = (a \star b)^d \star c^d = (a^d \star b^d) \star c^d.\end{split}\]

Như vậy ta chứng minh được tính kết hợp. Và từ đó \(G[d]\) là nhóm.

  1. Sử dụng kết quả câu 2.11

\[S_3[2] = \{\tau, \sigma\tau, \sigma^2, \tau, e \}.\]

Vì

\[(\sigma\tau)\tau = \sigma\tau^2 = \sigma \notin S_3[2]\]

nên \(S_3[2]\) không là nhóm.

Exercise (Câu 2.13)

Let \(G\) and \(H\) be groups. A function \(\phi: G \rightarrow H\) is called a (group) homomorphism if it satisfies

\[\phi(g_1 \star g_2) = \phi(g_1) \star \phi(g_2) \quad \text{for all} \ g_1, g_2 \in G\]

(Note that the product \(g_1 \star g_2\) uses the group law in the group \(G\), while the product \(\phi(g_1) \star \phi(g_2)\) uses the group law in the group \(H\).)

  1. Let \(e_G\) be the identity element of \(G\), let \(e_H\) be identity element of \(H\), and the \(g \in G\). Prove that

\[\phi(e_G) = e_H \quad\quad \text{and} \quad\quad \phi(g^{-1}) = \phi(g)^{-1}\]

  1. Let \(G\) be a commutative group. Prove that the map \(\phi: G \rightarrow G\) defined by \(\phi(g)=g^2\) is a homomorphism. Give an example of a noncommutative group for which this map is not a homomorphism.

  2. Same question as (b) for the map \(\phi(g)=g^{-1}\).

  1. Với mọi \(g \in G\) thì \(g = g \star e = e \star g\). Suy ra

\[\begin{split}& \phi(g) = \phi(g \star e_G) = \phi(e_G \star g) \\ \Longleftrightarrow \ & \phi(g) = \phi(g) \star \phi(e_G) = \phi(e_G) \star \phi(g)\end{split}\]

Do \(\phi(g) \in H\), \(\phi(e_G)\) là phần tử đơn vị của \(H\), nói cách khác là \(\phi(e_G) = e_H\).

Trong nhóm \(G\), \(g \star g^{-1} = e_G\). Suy ra

\[\begin{split}& \phi(g \star g^{-1}) = \phi(e_G) \\ \Longleftrightarrow \ & \phi(g) \star \phi(g^{-1}) = \phi(e_G) \\ \Longleftrightarrow \ & \phi(g) \star \phi(g^{-1}) = e_H \\ \Longleftrightarrow \ & \phi(g^{-1}) = \phi(g)^{-1}\end{split}\]

  1. \(\phi: G \rightarrow G\), \(\phi(g) = g^2\). Với mọi \(g_1, g_2 \in G\), do \(G\) là nhóm giao hoán nên

\[\phi(g_1 \star g_2) = (g_1 \star g_2)^2 = g_1^2 \star g_2^2\]

Ta có \(g_1^2 \star g_2^2 = \phi(g_1) \star \phi(g_2)\) nên \(\phi(g_1 \star g_2) = \phi(g_1) \star \phi(g_2)\). Như vậy \(G\) là homomorphism.

Xét nhóm ở Câu 2.11 và ánh xạ \(\phi: G \rightarrow G\), \(\phi(g)=g^2\).

Khi đó

\[\begin{split}\phi(e) = e^2 = e, & \quad \phi(\sigma) = \sigma^2, \\ \phi(\tau) = \tau^2 = e, & \quad \phi(\sigma\tau) = (\sigma\tau)^2 = e.\end{split}\]

Vì

\[\phi(\sigma\tau) = e \neq \sigma^2 = \phi(\sigma)\phi(\tau),\]

nên \(G\) không là homomorphism.

  1. \(\phi: G \rightarrow G\), \(\phi(g) = g^{-1}\).

Với mọi \(g_1, g_2 \in G\) thì \(g_1 g_1^{-1} = e\) và \(g_2 g_2^{-1} = e\)

Do đó \(g_1 g_1^{-1} g_2 g_2^{-1} = e\), mà \(G\) là nhóm hoán vị nên \((g_1 g_2)(g_1^{-1} g_2^{-1}) = e\), tương đương với \(g_1^{-1} g_2^{-1} = (g_1 g_2)^{-1}\). Như vậy

\[\phi(g_1 g_2) = (g_1 g_2)^{-1} = g_1^{-1} g_2^{-1} = \phi(g_1) \phi(g_2)\]

Kết luận: \(G\) là homomorphism.

Xét nhóm ở Câu 2.11 và ánh xạ \(\phi: G \rightarrow G\), \(\phi(g) = g^{-1}\). Ta có

\[\sigma\sigma^2 = e = \sigma^2\sigma = e, \quad \tau^2 = e, \quad (\sigma\tau)^2 = e, \quad (\sigma^2\tau)^2 = e,\]

suy ra

\[\phi(\sigma\tau) = \sigma\tau, \quad \phi(\sigma) = \sigma^2, \quad \phi(\tau) = \tau\]

Vì \(\phi(\sigma\tau) = \sigma\tau \neq \sigma^2\tau = \phi(\sigma)\phi(\tau)\) nên \(G\) không là homomorphism.

Exercise (Câu 2.14)

Prove that each of the following maps is a group homomophism.

  1. The map \(\phi: \mathbb{Z} \rightarrow \mathbb{Z}/N\mathbb{Z}\) that sends \(a \in Z\) to \(a\) mod \(N\) in \(\mathbb{Z}/N\mathbb{Z}\).

  2. The map \(\phi: \mathbb{R}^* \to GL_2(\mathbb{R})\) defined by \(\phi(a) = \begin{pmatrix}a & 0 \\ 0 & a^{-1}\end{pmatrix}\).

  3. The discrete logarithm map \(\log_g: \mathbb{F}_p^* \rightarrow \mathbb{Z}/(p-1)\mathbb{Z}\), where \(g\) is a primitive root modulo \(p\).

  1. Với mọi \(a, b \in \mathbb{Z}\),

\[\begin{split}\phi(ab) & = (ab) \pmod N \\ & = (a \bmod N) \ (b \bmod N) \pmod N \\ & = \phi(a) \phi(b) \\\end{split}\]

Do đó \(\phi\) là homomorphism.

  1. Với mọi \(a, b \in \mathbb{R}^*\) thì

\[\begin{split}\phi(ab)=\begin{pmatrix}ab & 0 \\ 0 & (ab)^{-1}\end{pmatrix}\end{split}\]

Ta có

\[\begin{split}\phi(a)\phi(b) = \begin{pmatrix}a & 0 \\ 0 & a^{-1}\end{pmatrix} \begin{pmatrix}b & 0 \\ 0 & b^{-1}\end{pmatrix} = \begin{pmatrix}ab & 0 \\ 0 & a^{-1}b^{-1}\end{pmatrix}\end{split}\]

Trong \(\mathbb{R}^*\) ta có tính chất \((ab)^{-1} = a^{-1}b^{-1}\), do đó \(\phi(ab) = \phi(a)\phi(b)\). Suy ra \(\phi\) là homomorphism.

  1. Ta chọn ánh xạ \(\phi(a) = x\) thỏa mãn \(g^x \equiv a \pmod p\).

Khi đó, với mọi \(a, b \in \mathbb{F}_p^*\), \(\phi(a) = x\), hay \(g^x \equiv a \pmod p\), và \(\phi(b) = y\), hay \(g^y \equiv b \pmod p\).

Ta có \(\phi(a) \phi(b) = x+y\) vì \(x\), \(y \in \mathbb{Z}/(p-1)\mathbb{Z}\), đây là phép cộng trong modulo \(p-1\).

Ta lại có \(g^{x+y} \equiv ab \pmod p\), suy ra \(\phi(ab) = x + y\). Như vậy \(\phi(a)\phi(b) = \phi(ab)\) và \(\phi\) là homomorphism.

Exercise (Câu 2.15)

  1. Prove that \(\mathrm{GL}_2(\mathbb{F}_p)\) is a group.

  2. Show that \(\mathrm{GL}_2(\mathbb{F}_p)\) is a noncommutative group for every prime \(p\).

  3. Describe \(\mathrm{GL}_2(\mathbb{F}_p)\) completely. That is, list its elements and describe the multiplication table.

  4. How many elements are there in the group \(\mathrm{GL}_2(\mathbb{F}_p)\)?

  5. How many elements are there in the group \(\mathrm{GL}_n(\mathbb{F}_p)\)?

  1. Nếu \(A\) và \(B\) là hai ma trận thuộc \(\mathrm{GL}_2(\mathbb{F}_p)\) thì \(AB\) cũng thuộc \(GL_2(\mathbb{F}_p)\) do \(\det(AB) = \det(A) \cdot \det(B)\) khác \(0\).

Phần tử đơn vị là \(E = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\).

Với mọi \(A \in GL_2(\mathbb{F}_p)\), do \(\det A \neq 0\) nên luôn tồn tại nghịch đảo của \(A\) trong \(GL_2(\mathbb{F}_p)\).

Với mọi \(A, B, C \in GL_2(\mathbb{F}_p)\) ta đều có \((AB)C=A(BC)\) vì phép nhân ma trận có tính kết hợp.

Kết luận: \(GL_2(\mathbb{F}_p)\) là nhóm.

Giả sử ta có \(A = \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}\) và \(B=\begin{pmatrix}b_{11} & b_{12} \\ b_{21} & b_{22}\end{pmatrix}\) với \(A, B \in GL_2(\mathbb{F}_p)\).

Phần tử ở hàng \(1\) và cột \(1\) của tích \(AB\) là \((a_{11}b_{11}+a_{12}b_{21}) \pmod p\).

Phần tử ở hàng \(1\) và cột \(1\) của tích \(BA\) là \((b_{11}a_{11} + b_{12}a_{21}) \pmod p\).

Nếu ta chọn \(a_{12} \not\equiv b_{21}^{-1}a_{21}b_{21} \pmod p\) thì \(AB \neq BA\), do đó nhóm không có tính giao hoán.

  1. Ta liệt kê tất cả ma trận:

\[\begin{split}A_1 = \begin{pmatrix}0 & 1\\1 & 0\end{pmatrix}, \quad A_2 = \begin{pmatrix}0 & 1\\1 & 1\end{pmatrix}, \quad A_3 = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix}, \\ A_4 = \begin{pmatrix}1 & 0\\1 & 1\end{pmatrix}, \quad A_5 = \begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}, \quad A_6 = \begin{pmatrix}1 & 1\\1 & 0\end{pmatrix}.\end{split}\]

Bảng phép nhân sẽ như sau:

\(A_1\)

\(A_2\)

\(A_3\)

\(A_4\)

\(A_5\)

\(A_6\)

\(A_1\)

\(A_3\)

\(A_5\)

\(A_1\)

\(A_6\)

\(A_2\)

\(A_4\)

\(A_2\)

\(A_4\)

\(A_6\)

\(A_2\)

\(A_5\)

\(A_1\)

\(A_3\)

\(A_3\)

\(A_1\)

\(A_2\)

\(A_3\)

\(A_4\)

\(A_5\)

\(A_6\)

\(A_4\)

\(A_2\)

\(A_1\)

\(A_4\)

\(A_3\)

\(A_6\)

\(A_5\)

\(A_5\)

\(A_6\)

\(A_4\)

\(A_5\)

\(A_2\)

\(A_3\)

\(A_1\)

\(A_6\)

\(A_5\)

\(A_3\)

\(A_6\)

\(A_1\)

\(A_4\)

\(A_2\)

  1. Hàng đầu \(\bm{u}_1\) là vector bất kì thuộc \(\mathbb{F}_p^2\) ngoại trừ \((0, 0)\). Do đó ta có \(p^2-1\) cách chọn.

Hàng thứ hai \(\bm{u}_2\) là vector bất kì ngoại trừ một bội của hàng đầu. Do đó ta có \(p^2-p\) cách (loại các cách chọn \(i \cdot \bm{u}_1\) với \(i = 0, 1, \ldots, p-1\)).

Kết luận: có \((p^2-1)(p^2-p)\) phần tử trong \(GL_2(\mathbb{F}_p)\).

  1. Tương tự (d), ta chọn hàng đầu \(\bm{u}_1\) là bất kì vector nào ngoại từ \((0,0)\). Ta có \(p^n-1\) cách chọn.

Hàng thứ hai \(\bm{u}_2\) là bất kì vector nào ngoại trừ bội của hàng đầu, nghĩa là loại các tổ hợp \(i \cdot \bm{u}_1\) với \(i = 0, 1, \ldots, p-1\). Ta có \(p^n-p\) cách chọn.

Hàng thứ ba \(\bm{u}_3\) là bất kì vector nào ngoại trừ các tổ hợp tuyến tính của \(\bm{u}_1\) và \(\bm{u}_2\). Số lượng tổ hợp tuyến tính \(a_1 \cdot \bm{u}_1 + a_2 \cdot \bm{u}_2\) chính là số lượng cặp \((a_1, a_2)\) và ta có \(p^2\) trường hợp (vì \(a_1, a_2 \in \mathbb{F}_p\)). Như vậy hàng thứ ba có \(p^n-p^2\) cách chọn.

Tổng quát, vector thứ \(n\) (hàng thứ \(n\)) là bất kì vector nào ngoại trừ tổ hợp tuyến tính của các vector trước đó \(\bm{u}_1\), \(\bm{u}_2\), ..., \(\bm{u}_{n-1}\). Như vậy ta có \(p^n-p^{n-1}\) cách chọn.

Kết luận: có tất cả \((p^n-1)(p^n-p) \cdots (p^n-p^{n-1})\) phần tử trong \(GL_n(\mathbb{F}_p)\).

Exercise (Câu 2.18)

Solve each of the following simultaneous systems of congruences (or explain why no solutions exists).

  1. \(x \equiv 3 \pmod 7\) and \(x \equiv 4 \pmod 9\)

  2. \(x \equiv 137 \pmod {423}\) and \(x \equiv 87 \pmod {191}\)

  1. \(x \equiv 5 \pmod 9\), \(x \equiv 6 \pmod {10}\) and \(x \equiv 7 \pmod {11}\)

  2. \(x \equiv 37 \pmod {43}\), \(x \equiv 22 \pmod {49}\) and \(x \equiv 18 \pmod {71}\)

  1. Vì \(N = 7 \cdot 9 = 63\), đặt \(T_1 = 63/7 = 9\), \(T_1^{-1} \bmod 7 = 4\), \(T_2 = 63/9 = 7\), \(T_2^{-1} \bmod 9 = 4\).

\[\Rightarrow x \equiv 3 \cdot 9 \cdot 4 + 4 \cdot 7 \cdot 4 \equiv 220 \equiv 31 \pmod {63}\]

  1. Vì \(N=423 \cdot 191=90793\), đặt \(T_1=N/423=191\), \(T_1^{-1} \bmod 423 = 392\), \(T_2=N/191=423\), \(T_2^{-1} \bmod 191 = 14\).

\[\Rightarrow x \equiv 137 \cdot 191 \cdot 392 + 87 \cdot 423 \cdot 14 \equiv 27209 \pmod N\]

  1. Không thể tính vì \(\gcd(451, 697) = 41 \neq 1\).

  2. Vì \(N = 9 \cdot 10 \cdot 11 = 990\), đặt \(T_1=N / 9=110\), \(T_1^{-1} \bmod 9 = 5\), \(T_2=N/10=99\), \(T_2^{-1} \bmod 10=9\), \(T_3=N/11=90\), \(T_3^{-1} \bmod 11 = 6\)

\[\Rightarrow x \equiv 5 \cdot 110 \cdot 5 + 6 \cdot 99 \cdot 9 + 7 \cdot 90 \cdot 6 \equiv 986 \pmod N\]

  1. Vì \(N=43 \cdot 49 \cdot 71=149597\), đặt \(T_1=N/43=3479\), \(T_1^{-1} \bmod 43 = 32\), \(T_2=N/49=3053\), \(T_2^{-1} \bmod 49=36\), \(T_3=N/71=2107\), \(T_3^{-1} \bmod 71 = 37\)

\[\Rightarrow x \equiv 37 \cdot 3479 \cdot 32 + 22 \cdot 3053 \cdot 36 + 18 \cdot 2107 \cdot 37 \equiv 11733 \pmod N\]

Exercise (Câu 2.19)

Solve the 1700-year-old Chinese remainder problem from the Sun Tzu Suan Ching stated on page 84.

\[\begin{split}\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}.\end{split}\]

Đáp án: \(x \equiv 23 \pmod {105}\).

Exercise (Câu 2.21.)

  1. Let \(a,b,c\) be positive integers and suppose that

\[a \mid c, \quad b \mid c, \quad \text{and} \quad \gcd(a,b)=1\]

Prove that \(ab \mid c\)

  1. Let \(x=c\) and \(x=c'\) be two solutions to the system of simultaneous congruences in the Chinese remainder theorem. Prove that

\[c \equiv c' \pmod{m_1m_2...m_k}\]

  1. Do \(a \mid c\) nên tồn tại \(k \in \mathbb{Z}\) sao cho \(c = ka\).

Do \(b \mid c\) nên tồn tại \(l \in \mathbb{Z}\) sao cho \(c = lb\).

Như vậy \(ka = lb\).

Tuy nhiên do \(\gcd(a,b) = 1\) nên \(a \mid l\), hay \(l = ma\) với \(m \in \mathbb{Z}\)

Như vậy \(c=lb=lma\), hay \(ab \mid c\).

  1. Nếu \(c \equiv c' (\equiv a_i) \pmod m_i\) thì \(c \equiv c' \pmod{m_1 m_2 \cdots m_k}\).

Exercise (Câu 2.24)

Let \(p\) be an odd prime, let \(a\) be an integer that is not divisible by \(p\), and let \(b\) is a square root of \(a\) modulo \(p\). This exercise investigates the square root of \(a\) modulo powers of \(p\)

  1. Prove that for some choise of \(k\), the number \(b+kp\) is a square root of \(a\) modulo \(p^2\), i.e., \((b+kp)^2 \equiv a \pmod{p^2}\)

  2. The number \(b=537\) is a square root of \(a=476\) modulo the prime \(p=1291\). Use the idea in (a) to compute a square root of 476 modulo \(p^2\)

  3. Suppose that \(b\) is a square root of \(a\) modulo \(p^n\). Prove that for some choice of \(j\), the number \(b+jp^n\) is a square root of \(a\) modulo \(p^{n+1}\)

  4. Explain why (c) implies the following statements: If \(p\) is an odd prime and if \(a\) has a square root modulo \(p\), then \(a\) has a square root modulo \(p^n\) for every power of \(p\). Is this true if \(p=2\)?

  5. Use the method in (c) to compute the square root of 3 modulo \(13^3\), given that \(9^2\equiv 3 \pmod{13}\)

  1. Đặt \(f(b_n)=b_n^2-a \pmod{p^n}\) với \(b_1 = b\). Suy ra \(f(b_1) = b^2-a \equiv 0 \pmod p\).

Ta cần tìm \(b_2\) thỏa \(f(b_2)=b_2^2-a \equiv 0 \pmod{p^2}\).

Nói cách khác, \(b_2 = b_1 + kp\) nên suy ra

\[f(b_1 + kp) = (b_1 + kp)^2 - a = b_1^2 + 2 b_1 kp + (kp)^2 - a \equiv 0 \pmod{p^2}\]

Tương đương với

\[2b_1k \equiv -(b_1^2-a)/p \pmod{p^2},\]

vì \(b_1^2-a \equiv 0 \pmod p\).

Do \(2b_1 \not\equiv 0 \pmod{p^2}\) nên tồn tại \(k\) thỏa mãn đẳng thức.

  1. Ta có công thức

\[k = -(b^2-a)/p \times (2b)^{-1} \pmod{p^2}\]

  1. Ta chứng minh theo quy nạp với mọi \(n \geqslant 1\), tồn tại \(b_n \in \mathbb{Z}\) sao cho

\[\begin{split}f(b_n) & = b_n^2-a \equiv 0 \pmod{p^n} \\ b_n & = b \pmod{p^n}\end{split}\]

Trường hợp \(n = 1\) là điều kiện ban đầu với \(b_1 = b\). Giả sử mệnh đề đúng tới \(n\), nghĩa là:

\[\begin{split}f(b_n) & = b_n^2 - a \pmod{p^n} \\ b_n & = b \pmod{p^n}\end{split}\]

Xét \(b_{n+1}\)

\[f(b_{n+1}) = b_{n+1}^2-a \equiv 0 \pmod{p^{n+1}}.\]

Ta viết \(b_{n+1}=b_n+p^nt_n\).

\[ \begin{align}\begin{aligned}\Rightarrow f(b_{n+1})=b_n^2+2b_np^nt_n+p^{2n}t_n^2 - a \equiv 0 \pmod{p^{n+1}}\\\Rightarrow b_n^2+2b_np^nt_n-a \equiv 0 \pmod{p^{n+1}} \ (\text{vì} \ 2n \geqslant n+1)\\\Rightarrow 2 b_n t_n \equiv -(b_n^2-a)/p^n \pmod{p^{n+1}} \ \text{từ} \ (2)\end{aligned}\end{align} \]

Nghiệm \(t_n\) tồn tại vì ta đã giả sử \(2b_n \equiv 0 \pmod{p^{n}}\). Như vậy

\[f(b_{n+1}) \equiv 0 \pmod{p^{n+1}}, \quad \text{và} \quad b_{n+1} \equiv b_n \pmod{p^n}.\]

Chứng minh này dùng cho \(b+jp^n\) modulo \(p^n\), không phải cho \(p^{n+1}\).

  1. Sử dụng quy nạp. Đặc biệt, nếu \(p=2\) thì mọi số nguyên đều thỏa.

Exercise (Câu 2.31)

Let \(R\) and \(S\) be rings. A functions \(\phi: R \rightarrow S\) is called a (ring) homomorphism if it satisfies

\[\phi(a+b)=\phi(a) + \phi(b) \quad \text{and} \quad \phi(a \star b) = \phi(a) \star \phi(b)\]

for all \(a, b \in R\).

  1. Let \(0_R\), \(0_S\), \(1_R\) and \(1_S\) denote the additive and multiplicative identities of \(R\) and \(S\), respectively. Prove that

\[\phi(0_R)=0_S, \, \phi(1_R)=1_S, \, \phi(-a)=-\phi(a), \, \phi(a^{-1})=\phi(a)^{-1}\]

where the last equality holds for those \(a \in R\) that have a multiplicative inverse.

  1. Let \(p\) be a prime, and let \(R\) be a ring with the property that \(pa = 0\) for every \(a \in R\). (Here \(pa\) means to add \(a\) to itself \(p\) times.) Prove that the map

\[\phi: R \rightarrow R, \quad \phi(a)=a^p\]

is a ring homomorphism. It is called the Frobenius homomorphism.

Điều kiện đề bài là \(\phi(a+b)=\phi(a)+\phi(b)\) và \(\phi(a \star b) = \phi(a) \star \phi(b)\) với mọi \(a, b \in R\).

  1. Trong \(R\), với mọi \(a \in R\) ta có

\[a + 0_R = 0_R + a = a.\]

Suy ra

\[\phi(a) = \phi(a + 0_R) = \phi(0_R + a),\]

hay

\[\phi(a) = \phi(a) + \phi(0_R) = \phi(0_R) + \phi(a).\]

Đặt \(\phi(a)=b \in S\). Khi đó

\[b = b + \phi(0_R) = \phi(0_R) + b\]

nên suy ra \(\phi(0_R) = 0_S\).

Trong \(R\), với mọi \(a \in R\) thì

\[a \star 1_R = 1_R \star a = a.\]

Khi đó

\[\phi(a \star 1_R) = \phi(1_R \star a) = \phi(a)\]

nên suy ra

\[\phi(a) \star \phi(1_R) = \phi(1_R) \star \phi(a) = \phi(a),\]

hay \(\phi(1_R) = 1_S\).

Với \(\phi(-a) = -\phi(a)\), trong \(R\) ta có

\[a + (-a) = (-a) + a = 0_R,\]

suy ra

\[\phi(a + (-a)) = \phi((-a) + a) = \phi(0_R),\]

tương đương với

\[\phi(a) + \phi(-a) = \phi(-a) + \phi(a) = \phi(0_R) = 0_S.\]

Như vậy \(\phi(-a) = -\phi(a)\).

Với \(\phi(a^{-1}) = \phi(a)^{-1}\), trong \(R\) ta có

\[a \star a^{-1} = a^{-1} \star a = 1_R,\]

suy ra

\[\phi(a \star a^{-1}) = \phi(a^{-1} \star a) = \phi(1_R),\]

tương đương với

\[\phi(a) \star \phi(a^{-1}) = \phi(a^{-1}) \star \phi(a) = \phi(1_R) = 1_S.\]

Như vậy \(\phi(a^{-1})=\phi(a)^{-1}\).

  1. Ánh xạ \(\phi: R \rightarrow R\) cho bởi \(\phi(a)=a^p\), suy ra

\[\phi(a+b) = (a+b)^p = \sum_{i=0}^{p} \binom{p}{i} a^i b^{p-1}.\]

Vì \(p \mid \displaystyle{\binom{p}{i}} = \dfrac{p!}{(p-i)! \cdot i!}\) (\(p\) là số nguyên tố) nên suy ra với mọi \(1 \leqslant i \leqslant p-1\), ta có \(\displaystyle{\binom{p}{i}} = 0\) (do \(pa=0\)).

\(\Rightarrow \phi(a+b)=a^p+b^p=\phi(a)+\phi(b)\) (1)

\(\Rightarrow \phi(ab)=(ab)^p=a^p b^p = \phi(a) \phi(b)\) (2)

Từ (1) và (2) ta thu được ring homomorphism.

Exercise (Câu 2.32)

Prove Proposition 2.41

Vì \(a_1 \equiv a_2 \pmod m\) nên \(m \mid (a_1 - a_2)\).

Nói cách khác là tồn tại \(k \in R\) sao cho \(a_1 - a_2 = k \star m\).

Tương tự, tồn tại \(l \in R\) sao cho \(b_1 - b_2 = l \star m\).

Từ đó

\[a_1 - a_2 + b_1 - b_2 = (k+l) \star m,\]

tương đương với

\[m \mid (a_1 + b_1 - (a_2 + b_2)),\]

hay

\[a_1 + b_1 \equiv a_2 + b_2 \pmod m.\]

Tương tự cho \(a_1-b_1 \equiv a_2-b_2 \pmod m\).

Đối với phép nhân, do

\[\begin{split}\begin{cases} a_1 = a_2 + k \star m \\ b_1 = b_2 + l \star m \end{cases}\end{split}\]

ta có

\[\begin{split}a_1 \star b_1 & = (a_2 + k \star m)(b_2 + l \star m) \\ & = a_2 \star b_2 + a_2 \star l \star m + k \star b_2 \star m + k \star l \star m^2,\end{split}\]

suy ra \(m \mid (a_1 \star b_1 - a_2 \star b_2)\) hay nói cách khác là

\[a_1 \star b_1 \equiv a_2 \star b_2 \pmod m.\]

Exercise (Câu 2.33)

Prove Proposition 2.43

Theo Câu 2.32, nếu ta có \(a' \in \bar{a}\) thì tương đương \(a' \equiv a \pmod m\).

Tương tự, nếu ta có \(b' \in \bar{b}\) thì tương đương \(b' \equiv b \pmod m\).

Như vậy, theo Câu 2.32 thì

\[a' + b' \equiv a+b \pmod m, \quad a' \star b' \equiv a \star b \pmod m\]

Nói cách khác

\[a'+b' \in \overline{a+b} \quad \text{và} \quad a' \star b' \in \overline{a \star b},\]

nói cách khác phép tính cộng và nhân đóng trên \(R\) (closed).

Với mọi \(a \in R\) ta có

\[\overline{a} + \overline{0} = \overline{a+0} = \overline{a} = \overline{0+a} = \overline{0} + \overline{a}\]

Như vậy phần tử trung hòa của phép cộng là \(\overline{0}\).

Với mọi \(a \in R\) thì

\[\overline{a} + \overline{m-a} = \overline{a + m - a} = \overline{0} = \overline{m-a} + \overline{a},\]

suy ra \(\overline{m-a}\) là phần tử đối của phần tử \(a\) trong phép cộng.

Phép cộng trong modulo cũng có tính kết hợp

\[\overline{a} + (\overline{b}+\overline{c}) = \overline{a} + \overline{b+c} = \overline{a+b+c} = \overline{a+b} + \overline{c} = (\overline{a}+\overline{b})+\overline{c}\]

Với mọi \(a, b \in R\)

\[\overline{a}+\overline{b}=\overline{a+b}=\overline{b+a}=\overline{b}+\overline{a}\]

nên phép cộng modulo có tính giao hoán.

Vì \(a \star 1 \equiv a \pmod m\) với mọi \(a \in R\) nên

\[\overline{a} \star \overline{1} = \overline{a \star 1} = \overline{a} = \overline{1 \star a} = \overline{1} \star \overline{a}.\]

Suy ra phần tử đơn vị của phép nhân là \(\overline{1}\).

Với mọi \(a, b, c \in R\) ta có \(a(bc)=(ab)c \pmod m\). Suy ra tính kết hợp của phép nhân

\[\overline{a} \star (\overline{b} \star \overline{c}) = \overline{a} \star \overline{bc} = \overline{abc} = \overline{ab} \star \overline{c} = (\overline{a} \star \overline{b}) \star \overline{c}.\]

Vì

\[\overline{a} \star \overline{b} = \overline{a \star b} = \overline{b \star a} = \overline{b} \star \overline{a}\]

ta có tính giao hoán của phép nhân.

Tính phân phối giữa phép nhân và phép cộng:

\[\overline{a} \star (\overline{b} + \overline{c}) = \overline{a} \star \overline{b + c} = \overline{a(b+c)} = \overline{ab + ac} = \overline{ab} + \overline{ac} = \overline{a} \star \overline{b} + \overline{a} \star \overline{c}.\]

Như vậy, \(R/(m)\) là vành (cụ thể vừa là vành với đơn vị vừa là vành giao hoán).

Exercise (Câu 2.34)

Let \(\mathbb{F}\) be a field and let \(\mathbf{a}\) and \(\mathbf{b}\) be nonzero polynomials in \(\mathbb{F}[x]\)

  1. Prove that \(\deg(\mathbf{a} \cdot \mathbf{b}) = \deg(\mathbf{a}) + \deg(\mathbf{b})\)

  2. Prove that \(\mathbf{a}\) has a multiplicative inverse in \(\mathbb{F}[x]\) if and only if \(\mathbb{a}\) is in \(\mathbb{F}\), i.e., if and only if \(\mathbb{a}\) is a constant polynomial

  3. Prove that every nonzero element of \(\mathbb{F}[x]\) can be factored into a product of irreducible polynomials. (Hint. Use (a), (b) and induction on the degree of the polynomial.)

  4. Let \(R\) be ring \(\mathbb{Z}/6\mathbb{Z}\). Give an example to show that (a) is false for some polynomials \(\mathbf{a}\) and \(\mathbf{b}\) in \(R[x]\).

  1. Đặt

\[\mathbf{a} = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0,\]

với \(a_i \in \mathbb{F}\) và \(\deg(\mathbf{a}) = n\).

Đặt

\[b = b_m x^m + b_{m-1} x^{m-1} + \cdots + b_1 x + b_0,\]

với \(b_i \in \mathbb{F}\) và \(\deg(\mathbf{b}) = m\).

Hạng tử với bậc cao nhất trong phép nhân \(\mathbf{a} \cdot \mathbf{b}\) là \(x^{n+m}\), do đó

\[\deg(\mathbf{a} \cdot \mathbf{b}) = n + m = \deg(\mathbf{a}) + \deg(\mathbf{b}).\]

  1. Với

\[\mathbf{a} = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0\]

Giả sử \(\mathbf{a}\) có nghịch đảo trong \(\mathbb{F}[x]\) là đa thức

\[\mathbf{b}=b_m x^m + b_{m-1} x^{m-1} + \cdots + b_1 x + b_0.\]

Vì

\[\mathbf{ab} =\sum_{i=0}^n a_i x_i \sum_{j=0}^m b_j x^j = \sum_{i=0}^n \sum_{j=0}^m a_i b_j x^{i+j} = 1.\]

Đồng nhất hệ số ta có \(a_0 b_0 = 1\), các tích khác bằng \(0\). Như vậy \(\mathbf{a}\) là đa thức hằng.

  1. \(\mathbf{a} = 2x^2 + 3x + 1\), \(\mathbf{b} = 3x + 2\).

Trong \(\mathbb{Z}/6\mathbb{Z}\) các hệ số được modulo cho \(6\) và ta có

\[\mathbf{a} \mathbf{b} = x^2 + 3x + 2\]

Như vậy \(\deg(\mathbf{a} \mathbf{b}) = 2 < 3 = \deg(\mathbf{a}) + \deg(\mathbf{b})\)

Exercise (Câu 2.37)

Prove that the polynomial \(x^3+x+1\) is irreducible in \(\mathbb{F}_2[x]\)

Nếu \(f(x) = x^3+x+1\) có nhân tử nào khác \(1\) và chính nó thì đa thức đó phải có bậc nhỏ hơn \(3\).

Các đa thức như vậy trong \(\mathbb{F}_2[x]\) là

\[0, x+1, x^2, x^2+1, x^2+x, x^2+x+1, x.\]

Tuy nhiên \(f(x)\) không chia hết cho bất kì đa thức nào kể trên nên \(f(x)\) là đa thức tối giản.

Exercise (Câu 2.39)

The field \(\mathbb{F}_7[x]/(x^2+1)\) is a field with \(49\) elements, which for the moment we donote by \(\mathbb{F}_{49}\)

Using example 2.58, every element in \(\mathbb{F}_7[x]/(x^2+1)\) has form \(f(x)=a+bx\), so in \(\mathbb{F}_{49}\) it has form \(a+bi\) (here \(i^2=-1\))

  1. Is \(2+5x\) is a primitive root in \(\mathbb{F}_{49}\)? No because \((2+5x)^8=1\)

  2. Is \(2+x\) is a primitive root in \(\mathbb{F}_{49}\)? Yes

  3. Is \(1+x\) is a primitive root in \(\mathbb{F}_{49}\)? No because \((1+x)^{24} = 1\)