Trường hữu hạn

Nhóm

Cho một tập các phần tử hoặc “số” và một phép toán hai ngôi, mà kết quả cũng là một phần tử của tập hợp đó. Tức là ứng với mỗi cặp phần tử trên tập đó, kết quả của phép toán cũng là một phần tử xác định của tập đã cho. Tính chất này ta gọi là tính đóng của phép toán trên tập đang xét.

Định nghĩa nhóm. Tập hợp G đó với phép toán . đã cho được gọi là nhóm, nếu nó thỏa mãn các tính chất sau với mọi phần tử a, b, c thuộc G:

• Tính kết hợp (a.b).c = a.(b.c)
• Có đơn vị e: e.a = a.e = a
• Có nghịch đảo a-1: a.a-1 = e

Nếu có thêm tính giao hoán a.b = b.a, thì gọi là nhóm Aben hay nhóm giao hoán.

Định nghĩa nhóm xiclic.

• Định nghĩa lũy thừa như là việc áp dụng lặp phép toán:

a3 = a.a.a

• Và đơn vị e=a0

• Một nhóm được gọi là xiclic nếu mọi phần tử đều là lũy thừa của một phần tử cố định nào đó. Chẳng hạn b = ak đối với a cố định và mỗi b trong nhóm.
• Khi đó a được gọi là phần tử sinh của nhóm.

Vành

Cho một tập R các “số” với hai phép toán được gọi là cộng và nhân. Ở đây “số” được hiểu là phần tử của tập hợp và hai phép toán trên xác định trên tập hợp đó. Tập với hai phép toán trên được gọi là vành, nếu hai phép toán thoả mãn các tính chất sau

• Với phép cộng, R là nhóm Aben
• Với phép nhân, có

- tính đóng và

- tính kết hợp

- tính phân phối đối với phép cộng a(b+c) = ab + ac

Nếu phép nhân có tính giao hoán thì tạo thành vành giao hoán.

Nếu phép nhân có nghịch đảo và không có thương 0 (tức là không có hai phần khác 0 mà tích của chúng lại bằng 0), thì nó tạo thành miền nguyên

Trường

Là một tập hợp F với hai phép toán cộng và nhân, thoả mãn tính chất sau:

• Với phép cộng F là nhóm Aben
• Với phép nhân F trừ phần tử 0 là nhóm Aben.
• F là một vành

Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0. Phép trừ được coi như là cộng với số đối của phép cộng và phép chia là nhân với số đối của phép nhân:

a – b = a + (-b)

a / b = a.b-1

Định nghĩa Modulo.

Cho số tự nhiên n và số nguyên a. Ta định nghĩa: a mod n là phần dư dương khi chia a cho n.

Định nghĩa quan hệ tương đương trên tập số nguyên

a ≡ b mod n

khi và chỉ khi a và b có phần dư như nhau khi chia cho n.

• Trong Modulo 7 ta có các lớp tuơng đương viết trên các hàng như sau:

Các phần tử cùng cột là có quan hệ đồng dư vói nhau. Tập các đại diện của các số nguyên theo Modulo n gồm n phần tử ký hiệu như sau:

Zn = { 0, 1, 2, 3, …, n-1 }.

Ước số

• Số b không âm được gọi là ước số của a, nếu có số m sao cho: a = mb

trong đó a, b, m đều nguyên.

• Tức là a chia hết cho b, ký hiệu là b|a

Các phép toán số học trên Modulo

Cho trước một số n. Ta muốn thực hiện các phép toán theo Modulo của n. Ta có thể thực hiện các phép toán trên các số nguyên như các phép cộng, nhân các số nguyên thông thường sau đó rút gọn lại bằng phép lấy Modulo hoặc cũng có thể vừa tính toán, kết hợp với rút gọn tại bất cứ thời điểm nào:

(a+b) mod n = [a mod n + b mod n] mod n (*)

(a.b) mod n = [a mod n . b mod n] mod n (**)

Như vậy khi thực hiện các phép toán ta có thể thay các số bằng các số tương đương theo Modulo n đó hoặc đơn giản hơn có thể thực hiện các phép toán trên các đại diện của nó: Zn = { 0, 1, 2, 3, …, n-1 }.

• Zn với các phép toán theo Modulo tạo thành vành giao hoán có đơn vị. Thực vậy tính đóng của các phép cộng và nhân dựa trên hai công thức (*) và (**). Các tính chất kết hợp, giao hoán và nghịch đảo được suy ra từ các tính chất tương ứng của các số nguyên.
• Các chú ý về tính chất rút gọn:

- nếu (a+b)≡(a+c) mod n, thì b≡c mod n

- Nhưng (ab)≡(ac) mod n, thì b≡c mod n chỉ khi nếu a là nguyên tố cùng nhau với n

Ước số chung lớn nhất.

• Bài toán. Cho hai số nguyên dương a và b. Bài toán tìm ước chung lớn nhất của hai số nguyên dương là bài toán chung của lý thuyết số. Ta ký hiệu GCD(a,b) là ước số chung dương lớn nhất của a và b, tức là số nguyên dương vừa là ước của a vừa là ước của b và là số nguyên dương lớn nhất có tính chất đó.

• Nguyên tố cùng nhau. Ta thấy 1 bao giờ cũng là ước số chung của hai số nguyên dương bất kỳ. Nếu GCD(a, b) = 1, thì a, b đựơc gọi là hai số nguyên tố cùng nhau:

• Tìm ước chung lớn nhất. Bây giờ chúng ta xét bài toán tìm ước số chung lớn nhất của hai số nguyên dương cho trước. Dễ dàng chứng minh được tính chất sau:

GCD(a,b) = GCD(b, a mod b)

Như vậy để tìm ước số chung của một cặp số cho trước, ta đưa về bài toán tìm ước chung của cặp số gồm số nhỏ hơn trong hai số đó và phần dư của số lớn khi chia cho số nhỏ hơn. Thuật toán Ơcơlít tạo nên vòng lặp, ở mỗi bước ta áp dụng tính chất trên cho đến khi phần dư đó còn khác 0.

• Thuật toán Ơcơlit tìm GCD(a, b)

A=a, B=b

while B>0•R = A mod B A = B, B = R

return A

Trường Galoa GL(p), với p là số nguyên tố.

• GL(p) gồm tập {0,1, … , p-1}
• Với các phép toán cộng và nhân Modulo, như ta đã biết GL(p) tạo thành một vành giao hoán. Vì p là số nguyên tố nên mọi số khác 0 nhỏ hơn p đều nguyên tố cùng nhau với p.

- GL(p) tạo thành trường vì mọi a thuộc {1, … , p-1} đều có phần tử nghịch đảo a-1: a . a-1 = 1. Thực vậy vì a và p nguyên tố cùng nhau nên theo thuật toán tìm nghịch đảo dưới đây ta sẽ tìm được nghịch đảo của a.

Như vậy trên GL(p) ta có thể thực hiện các phép toán cộng, trừ, nhân, chia.

Tìm số nghịch đảo

Bây giờ ta xét bài toán: nếu GCD(m, b) = 1, thì tìm nghịch đảo của b theo Modulo m.

Ta mở rộng thuật toán Ơcơlit vừa tìm ước chung lớn nhất của m và b, vừa tính nghịch đảo trong trường hợp GCD(m, b) = 1.

Thuật toán Euclid mở rộng:

EXTENDED EUCLID(m, b)

1.(A1, A2, A3)=(1, 0, m); (B1, B2, B3)=(0, 1, b)

2. if B3 = 0

return A3 = gcd(m, b); no inverse

3. if B3 = 1

return B3 = gcd(m, b); B2 = b–1 mod m

4. Q = A3 div B3

5. (T1,T2,T3)=(A1- Q*B1,A2 - Q*B2, A3- Q*B3)

6. (A1, A2, A3)=(B1,B2,B3)

7. (B1, B2, B3)=(T1,T2,T3)

8. goto 2

Thực vậy, các quan hệ sau là bất biến:

mA1 + bA2 = A3; (1) mB1+ bB2 = B3 (2) mT1 + bT2 = T3; (3)

Vì ban đầu: m.1 + b.0 = m; m.0 +b.1 = b, nên ta có (1) và (2) đúng. Và ta chứng minh trong một bước lặp từ (1) và (2) suy ra (3). Từ thuật toán ta có :

T1 = A1 – Q.B1

T2 = A2 – Q.B2

T3 = A3 – Q.B3

Nên ta sẽ chứng minh đẳng thức (3) còn lại

mT1 + bT2 = m(A1 – Q.B1) + b (A2 – Q.B2)

= (mA1 + bA2) - Q(mB1+ bB2)

= A3- Q.B3

=T3

Khi sang bước lặp tiếp theo đổi vai trò B sang A và T sang B, thì các công thức đối (1) và (2) đối với A, B sẽ đúng, và do đó theo chứng minh trên (3) sẽ đúng trong bước lặp tiếp theo. Vậy (1), (2), (3) là các bất biến của vòng lặp.

Cuối cùng khi B3 = 1, thì từ các bất biến ta có:

mB1+ bB2 = 1 bB2 = 1- mB1 bB2 = 1 mod m

Do đó: B2 = b-1 mod m

Ví dụ. Tìm nghịch đảo của 550 trong GL(1759).

Mỗi bước thực hiện thuật toán Ơcơlit mở rộng sẽ được mô tả bởi một hàng trong bảng sau.

Sau 4 bước. ta có B3 = 1, khi đó thuật toán dừng, GCD(1759, 550) = 1 và 550−1 size 12{"550" rSup { size 8{ - 1} } } {}mod 1759 = 355.

Số học đa thức

Ta xét tập các đa thức Pn có bậc nhỏ hơn hoặc bằng n:

Trên tập các đa thức đó ta có thể có một số cách khác nhau thực hiện các phép toán cộng và nhân đa thức:

• Có thể thực hiện các phép toán thông thường trên đa thức
• Các phép toán trên đa thức với các hệ số trên Modulo p
• Các phép toán trên đa thức với các hệ số trên Modulo p và sau đó lầy Modulo theo đa thức m(x)

- Phép toán đa thức thông thường

• Cộng trừ các hệ số tương ứng
• Nhân mọi hệ số với cùng một số.

- Phép toán đa thức với Modulo hệ số

• Cho số nguyên tố p tùy ý
• Tính các hệ số theo Modulo p. Khi đó tập các hệ số được lấy từ trường GL(p). Còn phép nhân đa thức có thể nhận được kết quả là đa thức bậc lớn hơn n.
• Ta thường quan tâm đến Mod 2, tức là mọi hệ số là 0 hoặc 1

Sau đây ta xét riêng trường hợp khi các phép tóan cộng, nhân đa thức được thực hiện với phép lấy Modulo theo một đa thức nào đó.

Phép toán đa thức với Modulo đa thức

• Cho đa thức g(x) bậc n và các hệ số của các đa thức xét trong mục này lầy trong trường Galoa GF(p) với p là số nguyên tố. Viết đa thức f(x) dưới dạng:

f(x) = q(x) g(x) + r(x)

trong đó r(x) là phần dư khi chia f(x) cho g(x). Rõ ràng bậc của r(x) sẽ nhỏ hơn bậc của g(x).

Ta viết r(x) = f(x) mod g(x)

• Nếu không có phần dư, tức là r(x) = 0, ta nói g(x) là ước của f(x) hay g(x) chia hết f(x) hay f(x) chia hết cho g(x).
• Trong trường hợp g(x) không có ước ngoài 1 và chính nó, thì ta nói g(x) là đa thức nguyên tố hoặc không rút gọn được.

• Việc tìm ước chung lớn nhất của hai đa thức được trình bày trong thuật toán tương tự như Ơcolit như sau:

Tìm đa thức ước chung lớn nhất GCD(a(x), b(x))

- c(x) = GCD(a(x), b(x)) nếu c(x) là đa thức bậc lớn nhất mà chia hết cả a(x), b(x)

- Có thể điều chỉnh thuật toán Euclid’s Algorithm để tìm nó: EUCLID[a(x), b(x)]

1. A(x) = a(x); B(x) = b(x)

2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]

3. R(x) = A(x) mod B(x)

4. A(x) ¨ B(x)

5. B(x) ¨ R(x)

6. goto 2

Thuật toán tìm nghịch đảo của một đa thức theo một đa thức nguyên tố cùng nhau với nó, được trình bày tương tự như Ơcolit mở rộng.

• Phép toán đa thức với Modulo đa thức.

Cho g(x) là đa thức nguyên tố bậc n. Khi đó tập các đa thức bậc nhỏ hơn bằng n với các phép toán cộng và nhân đa thức theo Modulo của đa thức nguyên tố g(x) tạo thành trường hữu hạn, gọi là trường Galoa và ký hiệu là GL(pn).

Sau đây ta xét trường GF( 2n size 12{2 rSup { size 8{n} } } {}), tức là xét tập các đa thức với các hệ số Modulo 2 và bậc nhỏ hơn bằng n và phép toán nhân có thể rút gọn theo Modulo của đa thức g(x) nguyên tố bậc n. Có thể tìm được nghịch đảo nhờ thuật toán Euclide mở rộng.

Tuy nhiên để thuận tiện trong việc biểu diễn đa thức, ta sẽ xây dựng song ánh từ tập các đa thức bậc nhỏ hơn n vào các dãy n bit là dãy các hệ số thể hiện sự có mặt của các lũy thừa tương ứng, và xây dựng các phép toán cộng và nhân các dãy bit sao cho nhận được kết quả tương tự như cộng và nhân các đa thức tương ứng cùng với việc rút gọn theo đa thức nguyên tố. Để đơn giản ta minh họa qua ví dụ cụ thể trên GL( 23 size 12{2 rSup { size 8{3} } } {}).

• Bảng trên có thể xây dựng bằng cách tính trực tiếp trên các phép toán cộng và nhân đa thức sau đó lấy Modulo theo đa thức nguyên tố x3 + x + 1.
• Tuy nhiên có thể thực hiện các phép toán trên dãy 3 bit như sau;

o Vì các hệ số là 0, 1 nên các đa thức có thể biểu diễn như các xâu bit

o Phép cộng hai đa thức trở thành XOR (cộng cơ số 2) trên các xâu bit tương ứng với hai đa thức đó.

o Nhân một đa thức với x trở thành Shift sang trái 1 đơn vị của dãy .bit tương ứng với đa thức đó.

o Phép tính Modulo theo đa thức nguyên tố của một đa thức cùng bậc n được thực hiện bằng cách tính hiệu hay cũng là tổng của hai đa thức đó, mà đó cũng chính là lấy dãy bit của đa thức đó XOR với dãy bit của đa thức nguyên tố.

o Phép nhân và tính Modulo được kết hợp bằng phép lặp giữa Shìt và XOR.

Như vậy trường Galoa GL(2n) bao gồm 2n phần tử. Muốn trường Galoa có số phần tử lớn tuỳ ý, ta chỉ việc tăng và lấy n thích hợp. Đặc biệt việc tính toán các phép toán cộng trừ, nhân, chia trên đó rất nhanh và hiệu quả trên các thao tác của các thiết bị phần cứng. Chính vì vậy trường Galoa đóng vai trò quan trọng trong lý thuyết mã mà chúng ta sẽ thấy rõ qua các chương tiếp theo.

Các số nguyên tố

Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước số là 1 và chính nó. Chúng không thể được viết dưới dạng tích của các số khác. 1 là số nguyên tố, nhưng không quan tâm đến nó. Xét các số nhỏ hơn 10 ta có: 2, 3, 5, 7 là số nguyên tố, vì chúng không có ước số khác 1 và chính nó; 4, 6, 8, 9, 10 không phải là số nguyên tố. Có thể nói 2 là số chẵn duy nhất là số nguyên tố. Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là vô hạn.

Ví dụ.

Phân tích ra thừa số nguyên tố

Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố. Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận được tích.

Ta có kết luận, mọi số nguyên dương đều có phân tích duy nhất thành tích các lũy thừa của các số nguyên tố:

Thông thường để tìm phân tích trên, ta phải kiểm tra tính chia hết cho các số nguyên tố từ nhỏ đến lớn và thực hiện phép chia liên tiếp cho các số nguyên tố, rồi gộp thành lũy thừa của các số nguyên tố.

Các số nguyên tố cùng nhau và GCD

Hai số nguyên dương a và b không có ước chung nào ngoài 1, được gọi là nguyên tố cùng nhau.

Ngược lại có thể xác định ước chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó.

Định lý Ferma (Định lý Ferma nhỏ)

trong đó p là số nguyên tố và a là số nguyên bất kỳ khác bội của p: GCD(a, p) = 1. Hay với mọi số nguyên tố p và số nguyên a không là bội của p, ta luôn có

ap size 12{a rSup { size 8{p} } } {}= a mod p

Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn p.

Kết quả trên được dùng trong khoá công khai. Nó cùng được sử dụng để kiểm tra tính nguyên tố của một số nguyên p nào đó, bằng cách lấy ngẫu nhiên các số a và kiểm tra xem có tính chất nêu trên không, kết luận là p nguyên tố càng thuyết phục nếu phép thử trên đúng với nhiều lần chọn ngẫu nhiên các số a.

Hàm Ole

Cho n là một số nguyên dương. Khi thực hiện phép tính đồng dư n của mọi số nguyên khác ta nhận được tập đầy đủ các phần dư có thể có là:

0, 1, 2,…, n-1

Từ tập trên ta tìm tập rút gọn bao gồm các số nguyên tố cùng nhau với n và quan tâm đến số lượng các phần tử như vậy đối với số nguyên dương n cho trước.

- Muốn tính Ф(n) việc đếm số các số ngưyên tố cùng nhau với n và nhỏ hơn n được loại bỏ vì đây là bài toán tốn nhiều công sức.

- Nói chung có thể tính hàm Ơle của một số dựa trên biểu thức phân tích ra thừa số của số đó.

• Dễ dàng thấy, nếu p là số nguyên tố Ф(p) = p-1
• Nếu p và q là hai số nguyên tố khác nhau, thì có thể chứng minh được rằng:
• Ф(p.q) = (p-1)(q-1)
• Nếu p là số nguyên tố, thì Ф( pn size 12{p rSup { size 8{n} } } {}) = pn−pn−1 size 12{p rSup { size 8{n} } - p rSup { size 8{n - 1} } } {}
• Nếu s và t là hai số nguyên tố cùng nhau, thì Ф(s.t) = Ф(s).Ф(t)

Định lý Ole

Định lý Ole là tổng quát hoá của Định lý Ferma

với mọi cặp số nguyên dương nguyên tố cùng nhau a và n: gcd(a,n)=1.

Kiểm tra tính nguyên tố

Giả sử cần phải tìm một số nguyên tố rất lớn. Lấy ngẫu nhiên một số đủ lớn, ta cần phải kiểm tra xem số đó có phải là số nguyên tố không. Phương pháp truyền thống là thử bằng phép chia như sau:

• Chia cho tất cả các số (chỉ cần nguyên tố) nhỏ hơn hoặc bằng căn bậc hai của số đó. Nếu nó không chia hết cho số nào, thì đó là số nguyên tố.
• Chỉ hiệu quả khi xét các số nhỏ.

Có phương pháp khác, mà ta sẽ xét ở đây, sử dụng các phép kiểm tra tính nguyên tố thống kê dựa trên các tính chất

• Mà mọi số nguyên tố phải thỏa mãn
• Nhưng có một số số không nguyên tố, gọi là giả nguyên tố cũng thoả mãn tính chất đó.

Cụ thể là phép kiểm tra dựa trên Định lý Ferma như sau: nếu số n cần kiểm tra tính nguyên tố là số nguyên tố, thì nó sẽ thoã mãn định lý Ferma đối với mọi số a nhỏ hơn nó an−1 size 12{a rSup { size 8{n - 1} } } {} mod n = 1. Như vậy, lấy ngẫu nhiên số a và kiểm tra xem nó có tính chất trên không.

Nếu có thì n có thể là số nguyên tố, nếu cần độ tin cậy lớn hơn, thì ta kiểm tra liên tiếp nhiều lần như vậy với các số ngẫu nhiên a được chọn. Sau mỗi lần qua được phép thử, xác suất để n là số nguyên tố lại tăng lên.

Kiểm tra số n có là số nguyên tố không, ta chỉ cần xét n là lẻ, khi đó n-1 là chẵn và biểu diễn nó dạng (n–1)= 2 k size 12{2 rSup { size 8{k} } } {} .q

Khi đó để tính a n − 1 size 12{a rSup { size 8{n - 1} } } {} , ta tính a q size 12{a rSup { size 8{q} } } {} , sau đó bình phương liên tiếp k lần.

Thuật toán Miller - Rabin

- Thuật toán như sau:

TEST (n) is:

1. Find integers k, q, k > 0, q odd, so that (n-1)=

2k size 12{2 rSup { size 8{k} } } {}

.q

2. Select a random integer a, 1<a<n-1

3. if aq mod n = 1 then return ("maybe prime");

4. for j = 0 to k - 1 do

5. if (

a2j size 12{a rSup { size 8{2j} } } {}

q mod n = n-1)

then return(" maybe prime ")

1. return ("composite")

Các xem xét về mặt xác suất

Nếu thuật toán Miller Rabin trả về số “composite” thì số đó chắc chắn không là số nguyên tố, vì khi đó số n và số a < n không thoả mãn định lý Fecma, tức là an−1 size 12{a rSup { size 8{n - 1} } } {} mod n ≠ 1.

Ngược lại số đó có thể là số nguyên tố hoặc giả nguyên tố theo nghĩa nó thoả mãn định lý Fecma với số a < n. Người ta chứng minh được rằng xác suất để số giả nguyên tố đó không là số nguyên tố là là ¼. Suy ra nếu lặp t phép thử với các lựa chọn ngẫu nhiên khác nhau của số a, thì khi đó xác suất để số n sau t phép thử là số nguyên tố là: 1−(1/4)t size 12{1 - ( 1/4 ) rSup { size 8{t} } } {}

Phân bố nguyên tố.

Định lý về số nguyên tố khẳng định số nguyên tố xuất hiện trung bình sau mỗi khoảng ln n số nguyên (nếu xét các số trong kích thước n). Như vậy bỏ qua số chẵn và các bội số của 5, ta cần kiểm tra 0.4ln n số trong kích thước n để tìm được 1 số nguyên tố. Chẳng hạn n=1024, thì 0.4*ln 1024 = 0.4*10 = 4, nghĩa là trong 1024 số đầu, thì trung bình cứ 4 số lại có một số nguyên tố. Lưu ý đây chỉ là trung bình, vì có lúc các số nguyên rất gần nhau và có lúc lại rất xa nhau.

Định lý phần dư Trung Hoa

Trong nhiều trường hợp ta muốn tìm cách để tăng tốc độ tính toán Modulo. Các phép toán trên modulo các số nhỏ tính nhanh nhiều so với các số lớn. Chính vì vậy nếu số lớn phân tích được thành tích của các số nhỏ, từng cặp nguyên tố cùng nhau, thì ta sẽ có cách tính hiệu quả nhờ vào định lý Phần dư Trung hoa.

Tính toán trên modulo của một tích các số mod M với M= m1m2..mk, trong đó GCD(mi, mj) = 1, với mọi i khác j. Định lý phần dư Trung Hoa cho phép làm việc trên từng modulo mi riêng biệt. Vì thời gian tính toán các phép toán trên modulo tỷ lệ với kích thước của số lấy modulo nên điều đó sẽ nhanh hơn tính toán trên toàn bộ M.

Có thể triển khai Định lý Trung Hoa theo một số cách như sau:

• Tính toán theo modulo số lớn. Để tính A mod M, với M khá lớn và A là biểu thức số học nào đó. Trước hết ta cần tính tất cả ai = A mod mi. Sau đó sử dụng công thức

trong đó Mi = M/mi

- Giải hệ phương trình modulo. Cho ai = x mod mi, với GCD(mi, mj) = 1, với mọi i khác j. Khi đó ta cũng áp dụng Định lý phần dư Trung Hoa để tìm x.

Căn nguyên tố

Từ Định lý Ole ta có , với a và n là nguyên tố cùng nhau. Nếu không có số mũ dương nào nhỏ hơn Ф(n), mà có tính chất như vậy đối với a, thì khi đó ta gọi a là căn nguyên tố của n. Cụ thể như sau:

- Xét m để am size 12{a rSup { size 8{m} } } {}mod n = 1, GCD(a,n)=1

Theo Định lý Ơle ta có m = Ф(n) thỏa mãn hệ thức trên, nhưng có thể cũng có giá trị nhỏ hơn của m < Ф(n) cũng thoả mãn. Khi đạt được m như vậy, thì nó cũng thoả mãn với bội của m, tức là sẽ có vòng lặp.

- Nếu giá trị m = Ф(n) là số dương nhỏ nhất thoả mãn công thức trên thì a được gọi là căn nguyên tố của n.

- Nếu p là số nguyên tố và a là căn nguyên tố của p, thì các luỹ thừa của a:

a0,a1,a2,...,ap−2 size 12{a rSup { size 8{0} } ,a rSup { size 8{1} } ,a rSup { size 8{2} } , "." "." "." ,a rSup { size 8{p - 2} } } {},sẽ sinh ra nhóm modulo p.

Việc tìm các căn nguyên tố a của n sẽ có ích trong việc xét mã công khai.

Logarit rời rạc

Bài toán ngược của bài toán lũy thừa là tìm logarit rời rạc của một sô modulo p, tức là tìm số nguyên x sao cho

ax size 12{a rSup { size 8{x} } } {} = b mod p

Hay còn được viết là .Nếu a là căn nguyên tố của p và p là số nguyên tố, thì luôn luôn tồn tại logarit rời rạc, ngược lại thì có thể không ?

Ta nhận thấy, trong khi bài toán lũy thừa là dễ dàng, thì bài toán logarit rời rạc là rất khó. Đây cũng là một cơ sở của mã công khai.

Bài tập

• 8 mod 9 + 7 mod 9
• 8 mod 9* 7 mod 9
• 5 mod 11- 9 mod 11
• 53 size 12{5 rSup { size 8{3} } } {}mod 7
• 520 size 12{5 rSup { size 8{"20"} } } {} mod 7
• 5/6 mod 7

• (-546) mod 13 - 347 mod 11
• (1234 + 2345) mod 17
• (213 * 345) mod 19
• 15−1 size 12{"15" rSup { size 8{ - 1} } } {}mod 101
• 14−1 size 12{"14" rSup { size 8{ - 1} } } {} mod 100
• 1435 size 12{"14" rSup { size 8{"35"} } } {} mod 11
• (235*126/13) mod 19
• 31130 size 12{"31" rSup { size 8{"130"} } } {} mod 23
• ( 23525 size 12{"235" rSup { size 8{"25"} } } {} /17 + 12619 size 12{"126" rSup { size 8{"19"} } } {}. 397 size 12{"39" rSup { size 8{7} } } {} /13) mod 29

• 12, 17, 21, 32, 36, 40, 72, 256.

• x mod 11 = 3; x mod 13 = 6
• y mod 51 = 11; y mod 100 = 15