Căn nguyên thủy modulo n

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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[sửa | sửa mã nguồn]

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 Zn*. Nhóm này là nhóm cyclic nếu và chỉ nếu n bằng 1, 2, 4, pk, hoặc 2 pk 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 Zn*.

Nói cách khác, một căn nguyên thủy modulo n là một số nguyên g mà mọi số nguyên không có ước chung với n ngoài các lũy thừa của g (modulo n).

Ví dụ[sửa | sửa mã nguồn]

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.

trong đó 3 là một căn nguyên thủy modulo 14,và ta có 32 ≡ 9, 33 ≡ 13, 34 ≡ 11, 35 ≡ 5 và 36 ≡ 1 (mod 14). chỉ còn một căn nguyên thủy modulo 14 là 5.

 m     mk (mod 14) – (chỉ liệt kê khoảng đầu tiên của mỗi chu kỳ)
 1 :   1,
 2 :   2,  4,  8 
 3 :   3,  9, 13, 11,  5,  1 
 4 :   4,  2,  8 
 5 :   5, 11, 13,  9,  3,  1
 6 :   6,  8
 7 :   7,
 8 :   8,
 9 :   9, 11,  1
10 :  10,  2,  6,  4, 12,  8
11 :  11,  9,  1
12 :  12,  4,  6,  2, 10,  8
13 :  13,  1
14 :   0, 

Chỉ các số m mà có thể nâng lên kũ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(mk) = nk − 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 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 A046145 trong 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[sửa | sửa mã nguồ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ì nó là một căn nguyên thủy. 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 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à p1,...,pk. 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 Cp0 sao cho, với mọi số nguyên tố pp0, tồn tại một căn nguyên thủy modulo p nhỏ hơn
C p1/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 mhỏ hơn
70 (ln(p))2.

Sử dụng[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

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