Căn nguyên thủy modulo n

Căn nguyên thủy modulo n là một khái niệm trong số học modulo của lý thuyết số.

Khái niệm

Nếu n ≥ 1 là một số nguyên thì các số nguyên nguyên tố cùng nhau với n tạo thành một nhóm với phép nhân modulo n; nhóm này được ký hiệu là (Z/nZ)^× hay Z_n^*. Nhóm này là nhóm cyclic nếu và chỉ nếu n bằng 1, 2, 4, p^k, hoặc 2 p^k với một số nguyên tố p ≥ 3 và lũy thừa k ≥ 1. Một phần tử sinh của nhóm cyclic này được gọi là một căn nguyên thủy modulo n, hay một phần tử nguyên thủy của Z_n^*.

Nói cách khác, số nguyên dương a gọi là căn nguyên thủy của n khi và chỉ khi a và n nguyên tố cùng nhau, a < n, và <\ord_{n}(a)= $\varphi (n)$

Ví dụ

Ta lấy chẳng hạn n = 14. Các phần tử của

(Z/14Z)^×

là các lớp đồng dư của

1, 3, 5, 9, 11 và 13.

(Mỗi số trên và n = 14 đều có ước chung lớn nhất là 1).

trong đó 3 là một căn nguyên thủy modulo 14,và ta có 3² ≡ 9, 3³ ≡ 13, 3⁴ ≡ 11, 3⁵ ≡ 5 và 3⁶ ≡ 1 (mod 14). Ngoài ra, còn một căn nguyên thủy modulo 14 khác là 5.

 m     m^k (mod 14) – (chỉ liệt kê khoảng đầu tiên của mỗi chu kỳ)
 1:   1
 3:   3,  9, 13, 11,  5,  1 
 5:   5, 11, 13,  9,  3,  1
 9:   9, 11,  1
11:  11,  9,  1
13:  13,  1

Số các giá trị tính được bởi modulo của 14 với m = 1 là 1, m = 3 là 6, m = 5 là 6, m = 9 là 3, m = 11 là 3, m = 13 là 2. Ta thấy chỉ có 3 và 5 có số các giá trị tính được = φ(14) = 6 (số các lớp đồng dư). Vì thế 3 và 5 là căn nguyên thủy của 14.

Chỉ các số m mà có thể nâng lên lũy thừa cho kết quả là 1 (mod 14) là nguyên tố cùng nhau với 14. Tập hợp các số đó là S = (1, 3, 9, 13, 11, 5).

Từ công thức f(m, k) = m^k − 1 ≡ 0 (mod 14) chúng ta hiểu các căn (- nói rõ hơn là các căn của 1 theo modulo 14) là các số m thỏa mãn đồng dư thức trên với lũy thừa k > 0 nào đó.

Tập hợp S = {1, 3, 9, 13, 11, 5} chứa tất cả các căn, tập hợp R = {3, 5} là tập hợp các "căn nguyên thủy", mà các lũy thừa (mod 14) trong một chu kỳ phải trải qua tất cả các căn có thể được, hay, nói cách khác, tập R "sinh ra " tập hợp S. ---

Bảng dưới đây là bảng chỉ ra các căn nguyên thủy nhỏ nhất của một số giá trị modulo n. Có thể tìm thấy nhiều hơn trong (dãy số A046145 trong bảng OEIS):

n	2	3	4	5	6	7	8	9	10	11	12	13	14
căn nguyên thủy mod n nhỏ nhất	1	2	3	2	5	3	-	2	3	2	-	2	3

Tìm căn nguyên thủy modulo n

Chưa biết một công thức tổng quát cho các căn nguyên thủy modulo n. Tuy thế có một số phương pháp tìm căn nguyên thủy đã được giới thiệu. Nếu bậc của một số m modulo n bằng φ(n) (bậc của (Z/nZ)^×), thì m là một căn nguyên thủy của n. Ngược lại: Nếu m là một căn nguyên thủy modulo n thì bậc (nhân) của m modulo n là φ(n). Chúng ta có thể sử dụng điều này để kiểm tra các căn nguyên thủy.

Trước hết, tính φ(n). Sau đó kiểm tra các ước nguyên tố khác nhau của φ(n) chẳng hạn là p₁,...,p_k. Với mỗi m of (Z/nZ)^×, tính

m^{\phi (n)/p_{i}}\mod n\qquad {\mbox{cho}}\ i=1,\ldots ,k

bằng cách dùng thuật toán bình phương và nhân. Nếu với một số m nào đó cho k kết quả khác 1 thì nó là căn nguyên thủy.

Số các căn nguyên thủy modulo n, nếu có là

φ(φ(n))

vì, trong tường hợp tổng quát, một nhóm cyclic với r phần tử có φ(r) phần tử sinh.

Một số người quan tâm đến các căn nguyên thủy nhỏ. Chúng ta có kết quả sau đây:

Với mọi số ε>0 tồn tại hằng số dương C và p₀ sao cho, với mọi số nguyên tố p ≥ p₀, tồn tại một căn nguyên thủy modulo p nhỏ hơn

C p^1/4+ε.

Nếu giả thiết Riemann là đúng, thì với mọi số nguyên tố p, tồn tại một căn nguyên thủy modulo p nhỏ hơn

70 (ln(p))².

Sử dụng

Căn nguyên thủy modulo n được sử dụng thường xuyên trong mật mã học, trong hệ mật Diffie-Hellman Key Exchange.

Xem thêm

Tham khảo

Ore, Oystein (1988). Number Theory and Its History. Dover. tr. 284-302. ISBN 0-486-65620-9.