ĐẠI HỌC QUỐC GIA HÀ NÔI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRƯƠNG CÔNG QUYỀN

VẤN ĐỀ KIỂM TRA CÁC SỐ NGUYÊN TỐ LỚN

LUẬN VĂN THẠC SỸ

HÀ NỘI – 2011

LUAN VAN CHAT LUONG download : add


ĐẠI HỌC QUỐC GIA HÀ NÔI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
--------------------

TRƯƠNG CÔNG QUYỀN

VẤN ĐỀ KIỂM TRA CÁC SỐ NGUYÊN TỐ LỚN

Ngành: Công nghệ Thông tin
Chuyên ngành: Hệ thống Thông tin
Mã số: 60 48 05

LUẬN VĂN THẠC SỸ

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS Trịnh Nhật Tiến

HÀ NỘI – 2011

LUAN VAN CHAT LUONG download : add


MỤC LỤC
LỜI CAM ĐOAN ........................................................................................................2
LỜI CẢM ƠN ...............................................................................................................3
GIỚI THIỆU .................................................................................................................4
DANH MỤC TỪ VIẾT TẮT ...................................................................................7
Chương 1. CÁC KHÁI NIỆM CƠ BẢN ...............................................................8
1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC, ĐẠI SỐ ..................................8
1.1.1. Khái niệm trong số học ...............................................................................8
1.1.2. Khái niệm trong đại số ................................................................................9
1.1.3. Đồng dư và phương trình đồng dư tuyến tính .....................................12
1.1.4. Thặng dư thu gọn và phần tử nguyên thủy ..........................................15
1.1.5. Phương trình đồng dư bậc hai và thặng dư bậc hai ...........................17
1.2. MỘT SỐ THUẬT TOÁN ................................................................................20
1.2.1. Thuật tốn tính ước chung lớn nhất .......................................................20
1.2.2. Thuật tốn tính phần tử nghịch đảo theo Modulo ..............................24
1.2.3. Thuật tốn phân tích một số ra các thừa số ngun tố ......................25
1.3. ĐỘ PHỨC TẠP TÍNH TỐN .......................................................................30
1.3.1. Khái niệm về độ phức tạp tính tốn .......................................................30
1.3.2. Lớp phức tạp ................................................................................................33
1.3.3. Hàm một phía và cửa sập một phía ........................................................35
Chương 2. MỘT SỐ PHƯƠNG PHÁP KIỂM TRA SỐ NGUYÊN TỐ .....37
2.1. SỐ NGUYÊN TỐ ..............................................................................................37
2.1.1 Khái niệm số nguyên tố .............................................................................37
2.1.2. Tính chất của số nguyên tố ......................................................................37
2.1.3. Định lý cơ bản của số học ........................................................................38
2.1.4. Sự phân bố số nguyên tố ...........................................................................39

2.2. SỐ NGUYÊN TỐ CÓ DẠNG ĐẶC BIỆT .................................................41
2.2.1. Số nguyên tố Mersenne .............................................................................41

5

LUAN VAN CHAT LUONG download : add


2.2.2. Số nguyên tố Fermat ..................................................................................47
2.3. MỘT SỐ PHƯƠNG PHÁP KIỂM TRA SỐ NGUYÊN TỐ ..................49
2.3.1. Phương pháp cổ điển .................................................................................49
2.3.2. Phương pháp xác suất ................................................................................52
Chương 3. ỨNG DỤNG CỦA SỐ NGUN TỐ VÀ THỬ NGHIỆM
CHƯƠNG TRÌNH .....................................................................................................62
3.1. MÃ HĨA .............................................................................................................62
3.1.1 Hệ mã hóa RSA ...........................................................................................62
3.1.1 Hệ mã hóa Elgamal .....................................................................................63
3.1.1 Hệ mã hóa Rabin .........................................................................................64
3.2. KÝ SỐ ..................................................................................................................65
3.2.1. Chữ ký RSA ................................................................................................66
3.2.2. Chữ ký Elgamal ..........................................................................................67
3.2.3. Sơ đồ chuẩn chữ ký số DSS .....................................................................68
3.2.4. Chữ ký không thể phủ định ......................................................................69
3.3. CÁC GIAO THỨC THỎA THUẬN, PHÂN PHỐI KHÓA ..................71
3.3.1. Giao thức phân phối khoá Blom. ............................................................71
3.3.2. Giao thức phân phối khoá Diffie-Hellman. .........................................72
3.3.3. Giao thức thoả thuận khoá Diffie-Hellman. .......................................73
3.3.4. Giao thức thoả thuận khoá “Trạm tới Trạm”. ....................................74
3.3.5. Giao thức thoả thuận khoá MTI. ............................................................75
3.4. THỬ NGHIỆM CHƯƠNG TRÌNH ..............................................................76

3.4.1. Cấu hình hệ thống. .....................................................................................76
3.4.2. Chức năng chính. ........................................................................................76
3.4.3. Chương trình ................................................................................................77
KẾT LUẬN .................................................................................................................80
TÀI LIỆU THAM KHẢO .......................................................................................81

6

LUAN VAN CHAT LUONG download : add


DANH MỤC TỪ VIẾT TẮT
Gcd (Greatest Common Divisor)

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

Lcm (Least Common Multiple)

Bội số chung nhỏ nhất

Mod

Modulo

7

LUAN VAN CHAT LUONG download : add


Chương 1. CÁC KHÁI NIỆM CƠ BẢN

1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC, ĐẠI SỐ
1.1.1. Khái niệm trong số học
1). Ký hiệu chia hết
Cho a và b là hai số nguyên dương.
Số a chia hết cho số b ký hiệu là a  b  Tồn tại n  N sao cho:
a=b*n
Khi đó người ta nói b là ước của a và ký hiệu: b | a.
2). Ước số chung lớn nhất
Cho a và b là hai số nguyên dương.
Ước số chung lớn nhất của a và b là số tự nhiên m lớn nhất sao cho m | a và m | b.
Khi đó ký hiệu là gcd(a, b) = m.
3). Hai số nguyên tố cùng nhau
Cho a và b là hai số nguyên dương.
Số a và số b được gọi là 2 nguyên tố cùng nhau  gcd(a, b) = 1.
4). Đồng dư modulo
Cho n  N, n  0 và a, b  Z n* .
Ký hiệu a  b (mod n) nghĩa là a đồng dư với b theo mod n
 Tồn tại số nguyên k  Z n* sao cho a = b + k * n
Tức là (a - b) = k * n, như vậy n | (a - b).
5). Một số tính chất của đồng dư modulo
(a  b) (mod n)  [(a mod n)  (b mod n)] (mod n)
(a * b) (mod n)  [(a mod n) * (b mod n)] (mod n)

8

LUAN VAN CHAT LUONG download : add


1.1.2. Khái niệm trong đại số
1). Khái niệm nhóm

Nhóm là một cặp (G, *), trong đó G là tập hợp khác rỗng, * là phép tốn hai
ngơi trên G thoả mãn ba điều kiện sau:
1. Phép tốn có tính kết hợp:
(x * y) * z = x * (y * z) với mọi x, y, z G.
2. Có phần tử phần tử trung lập e  G:
x * e = e * x = x với mọi x  G.
3. Với mọi x  G, có phần tử nghịch đảo x’ G:
x * x’ = x’ * x = e
2). Nhóm con
Cho G là một Nhóm, cho S  G và S  . S được gọi là Nhóm con của G nếu:
1/. Phần tử trung lập e của G nằm trong S.
2/. S khép kín đối với luật hợp thành trong G (tức là x * y  S với mọi x, y S).
3/. S khép kín đối với phép lấy nghịch đảo trong G (tức x-1  S với mọi xS).
3). Nhóm Cyclic
a). Khái niệm Nhóm Cyclic
Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong
các phần tử của nó.
Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để
g n = g * g * … * g = a (Chú ý: g * g * … * g là g * g với n lần).
Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G.
Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g  G sao cho mọi
phần tử trong G đều là một luỹ thừa nguyên nào đó của g.

9

LUAN VAN CHAT LUONG download : add


Ví dụ: Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh
g = 1.

b). Cấp của Nhóm Cyclic:
Cho (G, *) là Nhóm Cyclic với phần tử sinh g và phần tử trung lập e. Nếu
tồn tại số tự nhiên nhỏ nhất n mà g n = e, thì G sẽ chỉ gồm có n phần tử khác nhau:
e, g, g2, g3, . . . , gn - 1 . Khi đó G được gọi là nhóm Cyclic hữu hạn cấp n.
Nếu khơng tồn tại số tự nhiên n để g n = e, thì G có cấp .
Ví dụ: (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1, e
= 0. Đó là Nhóm Cyclic vơ hạn, vì khơng tồn tại số tự nhiên n để g n = e,
c). Cấp của một phần tử trong Nhóm Cyclic:
Phần tử   G được gọi là có cấp d, nếu d là số nguyên dương nhỏ nhất sao
cho  d = e, trong đó e là phần tử trung lập của G.
Như vậy phần tử  có cấp 1, nếu  = e.
4). Tập Zn và Z*
Zn = 0, 1, 2, .. . , n - 1. Tức Zn là tập các số nguyên không âm < n.
Tập này cùng với phép cộng lập thành Nhóm Cyclic có phần tử sinh là 1. Đó là
Nhóm hữu hạn có cấp n.
Zn* = e  Zn, e là nguyên tố cùng nhau với n. Tức là e # 0.
Đó là tập các số nguyên dương < n, nhưng nguyên tố cùng nhau với n.
được gọi là tập Thặng dư thu gọn theo mod n, lập thành một Nhóm với phép nhân
mod n.
(n) là số các phần tử của tập Z n* .

10

LUAN VAN CHAT LUONG download : add


5). Một số kết quả
Những kết quả sau đã được chứng minh, nhắc lại để sử dụng:
* Định lý Lagrange: Cho G là nhóm Cấp n và g G. Khi đó cấp của g là
ước của n.

* Hệ quả: Giả sử g Z n* có Cấp m thì m là ước của  (n).
Nếu b  Z n* thì b (n)  1 (mod n).
Nếu p là số nguyên tố thì  (p) = p -1.
Do đó với mọi b  Z *p (tức b nguyên tố với p) thì b (p)  1 (mod n) hay
bp -1  1 (mod n).
* Định lý: Nếu p là số nguyên tố thì Z *p là Nhóm Cyclic.
Chú ý: Phần tử   Z n* có cấp d nếu d là số nguyên dương nhỏ nhất sao cho
d = e trong Z n* , tức là d  1 (mod n).
6). Khái niệm Logarit rời rạc
Cho p là số nguyên tố,  là phần tử nguyên thuỷ của Zp,  Z *p .
Logarit rời rạc chính là việc giải phương trình x = log  (mod p) với ẩn x.
Hay phải tìm số x duy nhất sao cho: x   (mod p).
- Bổ đề: Nếu (a, n) = 1 thì tồn tại a-1  Zn thoả mãn a * a-1  1 (mod n).
- Định lý (Euler tổng quát): Nếu (a, n) = 1 thì a(n) mod n = 1.
- Hệ quả: Với p là một số nguyên tố và (a, p) = 1 thì ap-1 (mod p) = 1.

11

LUAN VAN CHAT LUONG download : add


1.1.3. Đồng dư và phương trình đồng dư tuyến tính
Cho n là một số nguyên dương. Hai số nguyên a và b là đồng dư với nhau
theo mô đun n, và viết a  b (mod n), nếu n/a-b (tức cũng là nếu a – b chia hết cho
n, hay khi chia a và b cho n được cùng một số dư như nhau).
Ví dụ: 23  8 (mod 5), vì 23 – 8 = 5.3, -19  9 (mod 7) vì -19 – 9 = - 4.7
Quan hệ đồng dư (theo một môđun n) trên tập hợp các số ngun có các tính
chất phản xạ, đối xứng và bắc cầu, tức là một quan hệ tương đương, do đó nó tạo ra
một phân hoạch trên tập hợp tất cả các số nguyên Z thành ra các lớp tương đương:
hai số nguyên thuộc cùng một lớp tương đương khi và chỉ khi chúng cho cùng một

số dư nếu chia cho n. Mỗi lớp tương đương như vậy được đại diện bởi một số duy
nhất trong tập hợp Zn = {0, 1, 2, 3, ..., n-1}, là số dư chung khi chia các số trong lớp
đó cho n. Vì vậy, ta có thể đồng nhất Zn với tập hợp tất cả các lớp tương đương các
số nguyên theo mod n; trên tập đó ta có thể xác định các phép tính cộng, trừ và nhân
theo mod n.
Ví dụ: Z25 = {0, 1, 2, ...24}. Trong Z25, 15 +14 = 4, vì 15 + 14 = 29  4 (mod 25).
Tương tự, 15.14  10 trong Z25.
Cho a  Zn. Một số nguyên x  Zn được gọi là nghịch đảo của a theo modn,
nếu a.x  1 (modn). Nếu có số x như vậy thì ta nói a là khả nghịch, và ký hiệu x là
a-1 mod n. Thí dụ 22-1 mod 25 = 8, vì 22.8 = 186  1 (mod 25). Từ định nghĩa ta có
thể suy ra rằng a là khả nghịch theo mod n khi và chỉ khi gcd (a,n) = 1, tức là khi a
và n nguyên tố với nhau.
Dịnh nghĩa phép chia trong Zn như sau:
a : b (mod n) = a.b-1 mod n.
Phép chia chỉ thực hiện được khi b là khả nghịch theo mod n.
Ví dụ 15: 22 (mod 25) = 15 : 22-1 mod 25 = 20.

12

LUAN VAN CHAT LUONG download : add


Bây giờ xét các phương trình đồng dư tuyến tính
Phương trình đồng dư tuyến tính có dạng
a. x  b (mod n)

(1.1.3.1)

Trong đó a, b, n là các số nguyên, n > 0, x là ẩn số. Phương trình đó có nghiệm khi
và chỉ khi d = gcd (a,n) /b, và khi đó có đúng d nghiệm theo mod n. Thực vậy, đặt

a” = a/d, b’ = b/d, n’ = n/d ta thấy phương trình đồng dư (1.1.3.1) tương đương với
phương trình
a’x  b’ (mod n’)
Vì gcd(a’, n’) = 1, nên phương trình này có một nghiệm theo mod n’:
x = xo  b’. a’-1 (mod n’)
và do đó phương trình (1.2.1) có d nghiệm theo mod n là:
x = xo, xo + n’, ..., xo + (d - 1) n’ (mod n)
Tất cả d nghiệm đó khác nhau theo mod n, nhưng cùng đồng dư với nhau
theo mod n’.
Bây giờ ta xét hệ thống các phương trình đồng dư tuyến tính. Một hệ như
vậy có thể đưa về dạng
 x1  a1 (mod n1 )
 x  a (mod n )
 2
2
2

 .........................
 x k  a k (mod nk )

(1.1.3.2)

Ký hiệu: n = n1.n2...nk, Ni = n/ni. Có định lý sau đây:
Định lý về Số dư (định lý số dư Trung Quốc). Giả sử các số nguyên
n1, n2, ..., nk là từng cặp nguyên tố với nhau. Khi đó, hệ phương trình đồng dư tuyến
tính (1.1.3.2) có một nghiệm duy nhất theo mod n.

13

LUAN VAN CHAT LUONG download : add



Nghiệm duy nhất nói trong định lý 1.1.3.2 được cho bởi biểu thức:
x = ki=1 ai.Ni.Mi mod n,
trong đó Mi = Ni -1 mod ni (có Mi vì Ni và ni nguyên tố với nhau).
Nhận xét:
Định lý số dư Trung Quốc cho phép tính đồng dư theo modulo của một số
lớn (tích của nhiều số ngun tố cùng nhau), thơng qua tính tốn đồng dư theo
modulo các số nhỏ (từng thừa số).
Ví dụ: Tìm nghiệm của hệ phương trình:

 x  3118(mod 5353)

 x  139(mod 391)
 x  239(mod 247)

Vì các số 5353, 391, 247 nguyên tố cùng nhau, nên theo định lý Trung Quốc
về số dư hệ, có nghiệm duy nhất theo modulo m = 5353*391*247 = 516976681.
Để tìm x mod m ta tính:
m1 = m/5353 = 96577

→ y1 = 96577-1 mod 5353

m2 = m/391

= 1322191

→ y2 = 1322191-1 mod 391 = 16

m3 = m/247


= 2093023

→ y3 = 2093023-1 mod 247 = 238

= 5329

x = 31188.96577.5329 + 139.1322191.16 + 239.2093023.238 (mod m)
= 13824 (mod m)
Nếu (n1, n2) = 1, thì cặp phương trình x  a (mod n1) và x  a (mod n2) có
nghiệm duy nhất x  a (mod n) theo mod n với n = n1 n2.

14

LUAN VAN CHAT LUONG download : add


1.1.4. Thặng dư thu gọn và phần tử nguyên thủy
Tập Zn = {0, 1, 2, ..., n-1} thường được gọi là tập các thặng dư đầy đủ theo
mod n, vì mọi số ngun bất kỳ đều có thể tìm được trong Zn một số đồng dư với
mình (theo mod n). Tập Zn là đóng đối với các phép tính cộng, trừ và nhân theo
mod n, nhưng khơng đóng đối với phép chia, vì phép chia cho a theo mod n chỉ có
thể thực hiện được khi a và n nguyên tố với nhau, tức khi gcd(a,n) = 1.
Bây giờ ta xét tập Zn* = {a  Zn : gcd(a,n) = 1}, tức Zn* là tập con của Zn bao
gồm tất cả các phần tử nguyên tố với n. Ta gọi tập đó là tập các thặng dư thu gọn
theo mod n. Mọi số nguyên tố với n đều có thể tìm thấy trong Z n* một đại diện đồng
dư với mình theo mod n.
Chú ý rằng nếu p là một số nguyên tố thì Zp* = {1, 2, ..., p-1}.
Tập Zn* lập thành một nhóm con đối với phép nhân của Z n, vì trong Zn* phép
chia theo mod n bao giờ cũng thực hiện được, gọi Zn* là nhóm nhân của Zn.

Theo đại học số học, gọi số các phần tử trong một nhóm là cấp của nhóm đó.
Ký hiệu (n) là số các số nguyên dương bé hơn n và nguyên tố với n. Như vậy,
nhóm Zn* có cấp (n), và nếu p là số nguyên tố thì nhóm Zp* có cấp p-1.
Một phần tử g  Zn* có cấp m, nếu m là số nguyên dương bé nhất sao cho
gm = 1 trong Zn*. Theo một định lý trong Đại số, có m/(n). Vì vậy, với mọi b  Zn*
ln có b (n)  1 mod n.
Nếu p là số nguyên tố, thì do (p) = p – 1, có với mọi b  Zn*
bn-1  (mod p)

(1.1.4)

Nếu b có cấp p-1, tức p-1 là số mũ bé nhất thỏa mãn cơng thức (1.1.4) thì các
phần tử b, b2, ..., bp-1 đều khác nhau và theo mod p, chúng lập thành Zp*. Theo thuật
ngữ đại số, khi đó ta nói Zn* là một nhóm cyclic và b là một phần tử sinh, hay phần
tử nguyên thủy của nhóm đó. Trong lý thuyết số, người ta đã chứng minh được cái
tính chất sau đây của các phần tử nguyên thủy:

15

LUAN VAN CHAT LUONG download : add


1/. Với mọi số nguyên tố p, Zp* là nhóm cyclic, và có (p-1) phần tử nguyên
thủy
2/. Nếu p-1= p1a1. p2a2 ...psas là khai triển chính tắc của p – 1 và nếu
a

p 1
p1


 1(mod p) , …, a

p 1
ps

 1(mod p)

3/. Nếu g là phần tử nguyên thủy theo mod p, thì ß = gi mod p với mọi i mà
gcd (i, p-1)=1, cũng là phần tử nguyên thủy theo mod p.
Ba tính chất đó là cơ sở giúp ta tìm các phần tử nguyên thủy theo mod p, với
p là số nguyên tố bất kỳ. Ngoài ra, cũng chú ý một số tính chất sau đây, có thể được
sử dụng nhiều trong các chương trình sau:
a/. Nếu p là số nguyên tố và gcd(a,p) = 1, thì ap-1  1 (mod p) (định lý
Fermat).
b/. Nếu a  Zn*, thì a(n)  1(mod n). Nếu r  s (mod(n)) thì ar  as (mod n)
(định lý Euler).

16

LUAN VAN CHAT LUONG download : add


1.1.5. Phương trình đồng dư bậc hai và thặng dư bậc hai
Xét phương trình đồng dư bậc hai có dạng đơn giản sau đây:
x2  a (mod n)
Trong đó n là một số nguyên dương, a là số nguyên với gcd(a,n) = 1, và x là
ẩn số. Phương trình đó khơng phải bao giờ cũng có nghiệm, khi nó có nghiệm thì ta
nói a là một thặng dư bậc hai mod n; nếu khơng thì nói a là một bất thặng dư bậc
hai mod n. Tập các số nguyên nguyên tố với n được phân hoạch thành hai tập con:
tập Qn các thặng dư bậc hai mod n, và tập Qn các bất thặng dư mod n.

Khi n = p là số nguyên tố, ta có tiêu chuẩn Euler sau đây: Số a là thặng dư
bậc hai mod p nếu và chỉ nếu a(p-1)/2  1 (mod p). Tiêu chuẩn đó được chứng minh
như sau:
Giả sử có x sao cho x2  a (mod p), khi đó ta cũng sẽ có
a(p-1)/2  (x2)(p-1)/2  xp-1  1 (mod p).
Ngược lại, giả sử a(p-1)/2  1 (mod p). Khi đó a  Zn. Lấy b là một phần tử
nguyên thủy mod p, ắt có một số i nào đó sao cho a = bi mo p. Từ đó,
a(p-1)/2  bi(p-1)/2  1 (mod p).
Phần tử b có cấp p – 1, do đó (p-1) chia hết i(p-1)/2, i phải là số chẵn, i = 2j,
và a có căn bậc hai là  bj mod p.

Cho p là một số nguyên tố lẻ. Với mọi a ≥ 0 ta định nghĩa ký hiệu Legendre
a
  như sau:
 p

 0 khi a  0(mod p)
a 
  =  1 khi
a  Qp
 p   1 khi
a  Qp


Từ định nghĩa ta suy ra ngay a là thặng dư bậc hai mod p khi và chỉ khi
a
  = 1.
 p

17


LUAN VAN CHAT LUONG download : add


Theo tiêu chuẩn Euler nói trên, với mọi a ≥ 0, ta có:
a
   a(p-1)/2 (mod p).
 p

Bây giờ ta mở rộng ký hiệu Legengdre để được ký hiệu Jacobi đối với mọi
a
n

số nguyên lẻ n ≥ 1 và mọi số nguyên a ≥ 0, cũng được ký hiệu bởi   và được
định nghĩa như sau: Giả sử a có khai triển chính tắc thành thừa số ngun tố là

n  p1a1 . p2a2 ... pkak thì
 a   a 
  = 
 n   p1 

a1

a2

 a 
 a 
  .... 
 p2 
 pk 


ak

Khi n = p là số nguyên tố thì giá trị của các ký hiệu Legendre và Jacobi là
như nhau. Việc tính ký hiệu Legendre có thể phức tạp khi p rất lớn, trong khi việc
tính ký hiệu Jacobi có thể thuận lợi hơn do có thể sử dụng các tính chất 1-4 sau đây:
 m1   m2 
 =

 n   n 

1/. Nếu m1  m2 (mod n), thì 
2
n

 1, khi n  1(mod 8)
 1, khi n  3(mod 8)

2/.   = 

 m1.m2   m1   m2 
 =  .

 n   n   n 

3/. 

4/. Nếu m và n đều là số lẻ, thì
 n
  , khi n  3(mod 4) & m  3(mod 4)

 m    m 
  = 
 n    n , khi n  1(mod 4)  m  1(mod 4)

 m

Ví dụ: Dùng các tính chất đó, ta tính được:
 7411   9283   1872 

 =
 = 
 =
 9283   7411   7411 
 117 
 7411 
 40 
=
 =- 
 =- 

 7411 
 117 
 117 
 5   117   2 
=
 =
 =   = -1
 117   5   5 

 2  4  117 


 .

 7411   7411 
 2 3  5 
=- 
 .

 117   117 

18

LUAN VAN CHAT LUONG download : add


 7411 
 cũng
 9283 

9283 là một số nguyên tố. Do đó, giá trị -1 của ký hiệu Jacobi 

là giá trị của cùng ký hiệu Legendre đó, và ta kết luận được rằng 7411 là bất thặng
dư bậc hai mod 9283, hay phương trình x2  7411 (mod 9283) là vơ nghiệm.
Bây giờ xét việc giải phương trình đồng dư bậc hai
x2  a (mod n)

(1.1.5)

Trong một trường hợp đặc biệt khi n = p là số nguyên tố có dạng p = 4m + 3,
tức p đồng dư với 3 theo mod 4, và a là một số nguyên tố với p. Theo tiêu chuẩn

Euler ta biết phương trình (1.4.4) có nghiệm khi và chỉ khi a(p-1)2  (mod p). Khi đó
ta có:
a

p 1
1
2

 a(mod p)

a 2( m1)  a(mod p)

do đó x   am+1 (mod p) là hai nghiệm của phương trình (1.1.5)

19

LUAN VAN CHAT LUONG download : add


1.2. MỘT SỐ THUẬT TỐN
1.2.1. Thuật tốn tính ước chung lớn nhất
Ký hiệu Z là tập hợp các số nguyên, Z = { ..., -2, -1, 0, 1, 2, ...}, và Z+ là tập
hợp các số nguyên không âm, Z+ = {0, 1, 2, ...}. Trong mục này sẽ nhắc lại một số
kiến thức về số học của các số nguyên cần cho việc trình bày lý thuyết mật mã. Vì
để luận văn khơng q dài dịng, các kiến thức sẽ được nhắc đến chủ yếu là các khái
niệm, các mệnh đề sẽ được sử dụng, v.v..., còn các phần chứng minh sẽ được lược
bỏ.
Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân, nhưng khơng
đóng kín đối với phép chia: chia một số nguyên cho một số nguyên không phải bao
giờ cũng được kết quả là một số nguyên! Vì vậy, trường hợp chia hết, tức khi chia

số nguyên a cho số nguyên b được thương là một số nguyên q, a = b.q, có một ý
nghĩa đặc biệt. Khi đó, nói a chia hết cho b, a là bội số của b, b là ước số của a, và
ký hiệu là b|a. Dễ thấy ngay rằng số 1 là ước số của mọi số nguyên bất kỳ, số 0 là
bội số của mọi số nguyên bất kỳ, mọi số nguyên a đều là ước số, đồng thời là bội số
của chính nó.
Định lý 1.2
Nếu b > 0 và b|a thì gcd(a,b) = b.
Nếu a = bq +r thì gcd(a,b) = gcd(b,r).
Một số nguyên m được gọi là bội số chung của a và b nếu a|m và b|m. Số m
được gọi là bội số chung bé nhất của a và b và được ký hiệu là lcm(a,b), nếu m>0,
m là bội số chung của a và b, và mọi bội số chung của a và b đều là bội của m. Ví
dụ lcm(14,21) = 42.
Với hai số nguyên dương a và b bất kỳ ta có quan hệ
lcm(a,b).gcd(a,b) = a.b.

20

LUAN VAN CHAT LUONG download : add


Từ định lý 1.2 ta suy ra thuật toán sau đây thực hiện việc tìm ước số chung
lớn nhất của hai số ngun bất kỳ:
Thuật tốn Euclide tìm ước số chung lớn nhất:
INPUT: hai số nguyên không âm a và b, với a≥b.
OUTPUT: ước số chung lớn nhất của a và b
1. Trong khi còn b>0, thực hiện:
1.1. đặt r  a mod b,a  b, b  r.
2. Cho ra kết quả (a).

Ví dụ: Dùng thuật tốn Euclide tìm gcd(4864, 3458), lần lượt được các giá trị

gán cho các biến a, b và r như sau:
Bảng 1.2.1. Mô tả q trình tính tốn của thuật tốn Euclid
a

b

c

4864 = 1.3458 + 1406

4864

3458

3458 = 2.1406 + 646

3458

1406

1406

1406 = 2.646 + 114

1406

646

646


646 = 5.114 + 76

646

114

114

114 = 1.76 +38

114

76

76

76 = 2.38 +0

76

38

38

38

0

0


Cho hai số nguyên bất kỳ a và b, b > 1. Thực hiện phép chia a cho b ta sẽ
được hai số q và r sao cho
a = b.q + r, 0 ≤ r
21

LUAN VAN CHAT LUONG download : add


Số q được gọi là số thương của phép chia a cho b, ký hiệu a div b và số r
được gọi là số dư của phép chia a cho b, ký hiệu a mod b. Ví dụ: 25 div 7 = 3 và 25
mod 7 = 4, -25 div 7 = -4 và – 25 mod 7 = 3.
Một số nguyên d được gọi là ước số chung của hai số nguyên a và b nếu d/a
và d/b. Số nguyên d được gọi là ước số chung lớn nhất của a và b nếu d>0, d là ước
số chung của a và b, và mọi ước chung của a và b đều là ước số của d. Ký hiệu ước
số chung lớn nhất của a và b là gcd (a,b). Ví dụ gcd (12, 18) = 6, gcd (-18, 27) = 3.
Dễ thấy rằng với mọi số nguyên dương a ta có gcd (a, 0) = a, ta cũng sẽ qui
ước xem rằng gcd (0,0) = 0.
Một số nguyên a > 1 được gọi là số nguyên tố, nếu a khơng có ước số nào
ngồi 1 và chính a; và được gọi là hợp số, nếu không phải là nguyên tố. Ví dụ các
số 2, 3, 5, 7 là số nguyên tố; các số 6, 8, 10, 12, 14, 15 là hợp số. Hai số a và b được
gọi là ngun tố với nhau, nếu chúng khơng có ước số chung nào khác 1, tức là nếu
gcd (a,b) = 1. Một số nguyên n > 1 bất kỳ đều có thể viết dưới dạng:

n  p1a1 . p2a2 ... pkak
Trong đó p1, p2, ...,pk là các số nguyên tố khác nhau, a1, a2, ...ak là các số mũ
nguyên dương. Nếu không kể thứ tự các thừa số nguyên tố thì dạng biểu diễn đó là
duy nhất, ta gọi đó là dạng khai triển chính tắc của n. Ví dụ dạng khai triển chính
tắc của 1800 là 233252.
Các số nguyên tố và các vấn đề về số nguyên tố có một vai trò quan trọng

trong số học và trong ứng dụng vào lý thuyết mã hóa, sẽ xét riêng trong chương sau.
Thuật toán cho kết quả: gcd (4864, 3458) = 38.
Biết rằng nếu gcd (a,b) = d, thì phương trình bất định
a.x + b.y = d
có nghiệm nguyên (x,y), và một nghiệm ngun (x,y) như vậy có thể tìm
được bởi thuật toán Euclide mở rộng như sau:

22

LUAN VAN CHAT LUONG download : add


Thuật tốn Euclide mở rộng:
INPUT: hai số ngun khơng âm a và b với a ≥b.
OUTPUT: d = gcd (a,b) và hai số x, y sao cho a.x +b.y = d
1. Nếu b = 0 thì đặt d  a, x  1, y  0 và cho ra (d, x, y).
2. Đặt x2 = 1, x1 = 0, y2 = 0, y1 = 1.
3. Trong khi còn b > 0 thực hiện:
3.1 q  a div b, r  a mod b, x  x2 – qx1, y  y2 – qy1.
3.2 a  b, b  r, x2  x1, x1  x, y2  y1 và y1  y.
4. Đặt d  a, x  x2, y  y2, và cho ra kết quả (d, x, y)

Ví dụ: Dùng thuật toán Euclide mở rộng cho các số a = 4864 và b = 3458,
lần lượt được các giá trị sau đây cho các biến a, b, q, r, x, y, x1, x2, y1, y2 (sau mỗi
chu trình thực hiện hai lệnh 3.1 và 3.2).
Bảng 1.2.2. Mô tả q trình tính tốn của thuật tốn Euclid mở rộng
a

b

q

r

x

4864

3458

3458

1406

1

1406

1

1406

646

2

646

646

114

2

114

76

76
38

y

x1

x2

y1

y2

0

1

1

0

-1

1

0

-1

1

-2

3

-2

1

3

-1

114

5

-7

5

-2

-7

3

5

76

-27

38

-27

5

38

-7

38

1

38

32

-45

32

-27

-45

38

0

2

0

-91

128

-91

32

128

-45

Dễ thử lại rằng sau mỗi lần thực hiện chu trình gồm hai lệnh 3.1 và 3.2 các
giá trị x, y, r thu được luôn thỏa mãn 4864. x + 3458.y = r, và do đó khi kết thúc các
vịng lặp (ứng với giá trị b = 0), thực hiện tiếp lệnh 4 ta được kết quả d = 38 và

y = -45, cặp số (32, -45) thỏa mãn: 4864.32 + 3458. (-45) = 38.

23

LUAN VAN CHAT LUONG download : add


1.2.2. Thuật tốn tính phần tử nghịch đảo theo Modulo
* Định nghĩa:
Cho a  Zn , nếu tồn tại b  Zn sao cho a.b  1 (mod n), ta nói b là phần tử
nghịch đảo của a trong Zn và ký hiệu a-1.
Một phần tử có phần tử nghịch đảo, gọi là khả nghịch.
* Định lý: gcd (a, n) = 1  Phần tử a  Zn có phần tử nghịch đảo.
Chứng minh:
Nếu a.a-1 ≡ 1 (mod n) thì a.a-1 = 1 + kn ↔ a.a-1 - kn = 1 → (a, n) =1.
Nếu (a, n) = 1, ta có a.a-1 + kn = 1 → a.a-1 = 1 + kn, do đó a.a-1 ≡ 1 (mod n).
* Hệ quả: Mọi phần tử trong Zn* đều có phần tử nghịch đảo.
* Tìm phần tử nghịch đảo bằng Thuật tốn Euclid mở rộng.
Input: a  Zn , n
Output: Phần tử nghịch đảo của a.
Procedure
Invert(a, n);
Begin
g0:=n; g1:=a; u0:=1; u1:=0; v0:=0;
i:=1;
while gi  0 do
begin
y:= gi-1 div gi; gi+1 := gi+1 ui+1 := ui+1 - y.ui; vi+1 := vi+1
i:= i+1;
end;

t := vi+1;
if t > 0 then a-1 := t else a-1:=t
End;

v1:=1;

y.gi;
- y.vi;

+ n;

Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7
Tức là phải giải phương trình 3.x ≡ 1(mod 7), x sẽ là phần tử nghịch đảo
của 3.

24

LUAN VAN CHAT LUONG download : add


I

gi

ui

vi

y

1

7

1

0

1

3

0

1

2

2

1

1

-2

3

3

0

Vì t = v2 = -2 < 0 do đó x = a-1 := t + n = -2 + 7 = 5.
Vậy 5 là phần tử nghịch đảo của 3 trong Z7
Chú ý
Định lý (Euler tổng quát): Nếu (a, n) = 1 thì a(n) mod n = 1
Hệ quả: Nếu p là số nguyên tố và (a, p) = 1, thì ap-1 (mod p) = 1
1.2.3. Thuật tốn phân tích một số ra các thừa số nguyên tố
Đặt vấn đề: Có một khối lượng khổng lồ các tài liệu về các thuật tốn phân
tích thừa số. Tuy vậy, trong phần này chỉ đưa ra một cái nhìn khái quát bao gồm
việc thảo luận sơ lược về các thuật toán phân tích thừa số tốt nhất hiện thời và cách
sử dụng chúng trong thực tế. Ba thuật toán hiệu quả nhất trên các số thật lớn là:
sàng bậc hai, thuật toán đường cong Elliptic và sàng trường số. Các thuật toán nổi
tiếng khác bao gồm: phương pháp p và thuật toán (p – 1) của Pollard, thuật toán (p
+ 1) của Williams, thuật toán liên phân số và dĩ nhiên là cả phép chia thử.
1.2.3.1. Phương pháp Pollard
Thuật toán (p – 1) của Pollard (đưa ra vào năm 1975) là một ví dụ về một
thuật tốn đơn giản khi được áp dụng đối với các số nguyên lớn.
Inputs: n, số nguyên cần phân tích; và f(x), hàm tạo số giả ngẫu nhiên
modulo n.
Output: một nhân tử không tầm thường (khác 1 và n) của n, hoặc không
thực hiện được.

25

LUAN VAN CHAT LUONG download : add


x ← 2, y ← 2; d ← 1
While d = 1:

x ← f(x)
y ← f(f(y))
d ← GCD(|x − y|, n)
If d = n, return không thực hiện được
Else return d.
Hình 1. 2: Thuật tốn phân tích thừa số p - 1
Chú ý rằng thuật tốn có thể khơng tìm thấy nhân tử và trả về kết quả không
thực hiện được với một hợp số n. Trong trường hợp này sử dụng hàm f(x) khác và
thử lại. Thuật toán cũng không làm việc khi n là số nguyên tố, trong trường hợp
này d sẽ luôn là 1.
Đối với hàm f, chúng ta chọn đa thức với hệ số nguyên. một trong những
dạng chung nhất đó là: f(x) = x2 + c mod n, c ≠ 0, -2.
Ví dụ: Cho n = 8051 và f(x) = x2 + 1 mod 8051.
i

xi

yi

gcd(|xi – yi|, 8051)

1

5

26

1

2

26

7474

1

3

677

871

97

97 là một nhân tử không tầm thường của 8051. Nhân tử còn lại là thương của
phép chia n cho 97 bằng 83.

26

LUAN VAN CHAT LUONG download : add


1.2.3.2. Thuật toán đường cong Elliptic
Thuật toán đường cong Elliptic mạnh hơn (được Lenstra xây dựng vào
những năm 80) trên thực tế là sự tổng quát hóa của phương pháp p - 1. Ta sẽ không
thảo luận về mặt lý thuyết ở đây mà chỉ nhấn mạnh rằng, thành công của phương
pháp đường cong Elliptic tuỳ thuộc vào một tình huống tương tự: một số nguyên
“gần với” p chỉ có các thừa số nguyên tố bộ. Trong khi phương pháp p - 1 phụ
thuộc vào quan hệ trong Zp thì phương pháp đường cong Elliptic phụ thuộc vào các

Nhóm xác định trên các đường cong Elliptic theo modulo n.
1.2.3.3. Thuật toán kiểu Las Vegas
Thuật toán được xây dựng trên cơ sở một số nguyên tố nhất định liên quan
tới các căn bậc hai của 1 theo modulo n, trong đó n = p * q là tích của hai số nguyên
tố lẻ phân biệt.
1. Chọn w là ngẫu nhiên và 1  w  n – 1
2. Tính x = gcd (w, n)
3. Nếu 1 < x < n thì thốt (thành cơng: x = p hoặc x = q)
4. Tính a = A (b)
5. Viết ab - 1 = 2sr, r lẻ
6. Tính v = wr mod n
7. Nếu v = 1 (mod n) thì thốt (khơng thành cơng)
8. Trong khi v  1 (mod n) thì thực hiện
9. v0 = v
10. v = v2 mod n
11. Nếu v0  -1 (mod n) thì thốt (khơng thành cơng)
ngược lại
tính x = gcd (v0 + 1, n)
(thành công: x = p hoặc x = q)
Hình 1. 3: Thuật tốn phân tích thừa số (cho trước số mũ giải mã a)

27

LUAN VAN CHAT LUONG download : add