6. Logarithm rời rạc

6.1. Các thuật toán tính logarithm rời rạc

6.1.1. Thuật toán Baby-Step-Giant-Step

Thuật toán Baby-Step-Giant-Step (BSGS) giúp tính discrete logarithm trên nhóm cyclic với order là số nguyên tố.

Thuật toán 6.1 (Thuật toán Baby-Step-Giant-Step)

Input: Nhóm vòng \(G\) có order \(n\), phần tử sinh \(g\) và phần tử \(h \in G\).

Output: Số \(x\) duy nhất thuộc \(\{ 0, 1, \ldots, n-1 \}\) thỏa \(g^x = h\).

  1. Đặt \(m = \lfloor \sqrt{n} \rfloor\)

  2. For \(j = 0\) to \(m-1\)

    1. Tính \(g^j\). Lưu \((j, g^j)\) vào bảng

  3. Tính \(g^{-m}\)

  4. \(\gamma = h\)

  5. For \(i = 0\) to \(m-1\)

    1. Kiểm tra điều kiện \(\gamma \stackrel{?}{=} g^j\) với \(j = 0, 1, \ldots, m-1\)

    2. Nếu điều kiện thỏa, trả về \(im + j\)

    3. Nếu không, đặt \(\gamma = \gamma \cdot g^{-m}\)

6.1.2. Thuật toán Pohlig-Hellman cho order là lũy thừa nguyên tố

Khi order của nhóm vòng là lũy thừa một số nguyên tố thì ta dùng thuật toán Pohlig-Hellman.

Thuật toán 6.2 (Thuật toán Pohlig-Hellman)

Input: Nhóm vòng \(G\) có order \(n=p^e\), phần tử sinh \(g\) và phần tử \(h \in G\).

Output: Số \(x\) duy nhất thuộc \(\{ 0, 1, \ldots, n-1 \}\) thỏa \(g^x = h\).

  1. Khởi tạo \(x_0 = 0\)

  2. Tính \(\gamma = g^{p^{e-1}}\). Theo định lý Lagrange, \(\gamma\) có order là \(p\)

  3. For \(k = 0\) to \(e-1\)

    1. Tính \(h_k = (g^{-x_k} \cdot h)^{e-1-k}\)

    2. Sử dụng thuật toán BSGS (Thuật toán 6.1), tìm \(d_k \in \{ 0, 1, \ldots, p-1 \}\) sao cho \(\gamma^{d_k} = h_k\). Bước này có độ phức tạp \(O(\sqrt{p})\)

    3. Tính \(x_{k+1} = x_k + p^k d_k\)

  4. Trả về \(x_e\) là kết quả cần tìm.

6.1.3. Thuật toán Pohlig-Hellman tổng quát

Thuật toán 6.3 (Thuật toán Pohlig-Hellman tổng quát)

Input: Nhóm vòng \(G\) có order \(n\), phần tử sinh \(g\), phần tử \(h \in G\), và phân tích nhân tử \(n = \prod\limits_{i=1}^r p_i^{e_i}\)

Output: Số \(x\) duy nhất thuộc \(\{ 0, 1, \ldots, n-1 \}\) thỏa \(g^x = h\).

  1. For \(i = 1\) to \(r\)

    1. Tính \(g_i = g^{n / p_i^{e_i}}\). Theo định lí Lagrange thì \(g_i\) có order là \(p_i^{e_i}\)

    2. Tính \(h_i = h^{n / p_i^{e_i}}\). Khi đó \(h_i \in \langle g_i \rangle\)

    3. Sử dụng thuật toán Pohlig-Hellman cho nhóm vòng \(\langle g_i \rangle\) (Thuật toán 6.2) để tính \(x_i \in \{ 0, \ldots, p_i^{e_i} - 1 \}\) sao cho \(g_i^{x_i} = h_i\)

  2. Giải hệ phương trình đồng dư

    \[x \equiv x_i \pmod{p_i^{e_i}}\]

    với mọi \(i \in \{ 1, \ldots, r \}\)

  3. Return \(x\)