Các bước thực hiện:
Bước này áp dụng Định lý nhỏ Fermat để kiểm tra nhanh nguyên tố.
Định lý nhỏ Fermat: $p \in P \Rightarrow \forall b: b^{p-1} \equiv 1 \pmod \phi$ (với $P$ là tập số nguyên tố)
Để tạo một số nguyên tố lớn, tham khảo thuật toán tạo số nguyên tố lớn bên dưới.
Từ công thức bên trên, $d \equiv e^{-1} \pmod \phi$.
Quan trọng:
Khi đó ta dùng Extended Euclidean Algorithm để tìm nghịch đảo của $d$ trong modulo $\phi$.
Quá trình này có sử dụng Định lý thặng dư Trung Hoa (cho nhanh).
Với các quá trình tính toán bên trên cần thuật toán tính nhân + mũ modulo nhanh và hiệu quả.
Một số thuật toán bổ trợ:
Thuật toán Euclide mở rộng - XEuclidean
Bổ đề Bézout: $\exists x, y \in \mathbb{Z}: ax + by = \text{gcd}(a, b)$. Trong trường hợp $a, b$ nguyên tố thì $ax + by = 1$.
Ở đây ta quan tâm đến trường hợp $a, b$ nguyên tố. Khi đó, $ax \equiv 1 \pmod b \Rightarrow x \equiv a^{-1} \pmod b$. Thuật toán XEuclidean sẽ trả về $\text{gcd}(a, b), x, y$ tương ứng với biểu diễn Bézout $ax + by = \text{gcd}(a, b)$.
# Extended Euclidean Algorithm
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
g, y, x = extended_gcd(b % a, a)
return g, x - (b // a) * y, y
# Example: Tìm và in biểu diễn Bézout với a = 7, b = 31;
a, b = 7, 31
g, x, y = extended_gcd(a, b)
print('{0}.{1} + {2}.{3} = {4}'.format(a, x, b, y, g))
# Finding inverse modulo with extended_gcd:
def inverse_modulo(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise Exception('Inverse modular does not exists!')
return x % m
# Example: Tìm nghịch đảo của 7 trong Z_{31}, 8 trong Z_{31}
print(inverse_modulo(7, 31))
print(inverse_modulo(8, 31))
7.9 + 31.-2 = 1
9
4
Nhân naive có vẻ hơi “chậm”. Vậy giờ ta xài bit manipulation!
def add_mod(a, b, m):
return (a + b) % m
# Các thuật toán tính nhanh modulo.
# (x * y) % m
def mul_mod(x, y, n):
p = 0
x %= n
while y > 0:
if y & 1:
p = add_mod(p, x, n)
x = (x << 1) % n
y = y >> 1
return p
# x^p % m
def pow_mod(x, p, n):
y = 1
x %= n
if p == 0:
return y
while p > 0:
if p & 1:
y = mul_mod(y, x, n)
p = p >> 1
x = mul_mod(x, x, n)
return y
# Example:
# 3 * 50 = 14 (mod 17)
print(mul_mod(3, 50, 17))
# 3 ^ 50 = 9 (mod 17)
print(pow_mod(3, 50, 17))
14
9
Định lý thặng dư Trung Hoa (Tầu-khựa) - CRT
Cho hệ phương trình đồng dư \(\begin{cases} x \equiv b_1 \pmod{m_1} \\ x \equiv b_2 \pmod{m_2} \\ .. \\ x \equiv b_n \pmod{m_n} \end{cases}\)
yêu cầu đặt ra là tìm $x$?
Tìm modulo nghịch đảo của $N_i$ trong modulo $m_i$, $i \in [1, n]$). Gợi ý: xài thuật Extended Euclidean bên trên.
Hay, $\displaystyle x = Nk + \sum_{i = 1}^{n} (x_i \times N_i \times b_i), k \in \mathbb{N}$
Ta có thể sử dụng CRT để giải mã nhanh RSA cipher. Xét $c^d \pmod{n} \equiv c^d \pmod{pq}$.
Đặt $d_1 \equiv d \pmod{p - 1}, d_2 \equiv d \pmod{q - 1}$. $\exists n_1, n_2: d = n_1(p - 1) + d_1 = n_2(q - 1) + d_2$.
Áp vào công thức ban đầu, ta có $c^d \pmod{pq} \equiv c^{d_1}c^{(p - 1)} \pmod{p}$. Mà theo định lý nhỏ Fermat, $c^{p - 1} \equiv 1 \pmod{p}$. Vậy $c^{d} \equiv c^{d_1} \pmod{p}$
Tương tự, $c^{d} \equiv c^{d_2} \pmod{q}$. Vậy ta có hệ phương trình đồng dư
\[\begin{cases} c^{d} \equiv c^{d_1} \pmod{p} \\ c^{d} \equiv c^{d_2} \pmod{q} \end{cases}\]Ưu điểm của phương pháp này là thực hiện ít phép mũ hơn so với việc phải tính $c^d$.
Code (naive) và ví dụ bên dưới lần lượt giải các hệ
\[1. \begin{cases} x \equiv 1 \pmod{2} \\ x \equiv 2 \pmod{3} \end{cases} \\ 2. \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 0 \pmod{2} \\ x \equiv 0 \pmod{5} \end{cases} \\ 3. \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 1 \pmod{7} \end{cases}\]# Naive solution to the Chinese Remainder Theorem
def chinese_remainder(b, m):
# Calculate N
N = 1
for i in m: N *= i
# Calculate N_i
Ni = [N // i for i in m]
# Calculate x^{-1}_i
reverse_x = [inverse_modulo(n, m[i]) for i, n in enumerate(Ni)]
result = 0
for i, x in enumerate(reverse_x):
result = add_mod(mul_mod(Ni[i], mul_mod(b[i], x, N), N), result, N)
return N, result
print('{0[0]}k + {0[1]}'.format(chinese_remainder([1, 2], [2, 3])))
print('{0[0]}k + {0[1]}'.format(chinese_remainder([2, 0, 0], [3, 2, 5])))
print('{0[0]}k + {0[1]}'.format(chinese_remainder([2, 1], [3, 7])))
6k + 5
30k + 20
21k + 8
Cho $p$ là một số nguyên tố lẻ, $k \in \mathbb{N+}$ thỏa $1 < k < 2(p+1), k \nmid p$. Đặt $n = 2kp + 1$, các phát biểu sau là tương đương:
Khi đó $p_2$ là một số nguyên tố. Tiếp tục thay $p_1 \leftarrow p_2$ và thực hiện lại từ bước 2 đến khi đạt được số nguyên tố có số chữ số $d_1$ cần tạo.
Quan trọng: Đây là phương pháp brute-force để tìm một số nguyên tố lớn. Vì vậy, nên generate trước 1 cặp nguyên tố lớn trước khi xài trong RSA.
def large_prime_generator(expected_length, seed, collision = 1):
p1 = seed
d1 = len(str(p1))
while (d1 <= expected_length):
found = 0
for k1 in range(2, 2 * (p1 + 1) + 1):
p2 = 2 * k1 * p1 + 1
d2 = len(str(p2))
if d2 > expected_length: break
if p2 % 10 == 5: continue
# print('Testing {0} (k = {1})'.format(p2, k1))
for a1 in range(2, p2 + 1, collision):
power_mod = pow_mod(a1, k1 * p1, p2)
egcd = extended_gcd(a1**k1 + 1, p2)[0]
if power_mod == p2 - 1 and egcd == 1:
# print(p2, ' valid')
found = 1
break
if found == 1: break
if found == 1:
p1 = p2
d1 = len(str(p1))
if d2 >= expected_length: break
return p1
# Generate a prime with 5 digits, but with different seed
print(large_prime_generator(5, 13))
print(large_prime_generator(5, 17))
19319
34679