ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THÙY DUNG
CÁC THUẬT TOÁN CƠ BẢN
TRONG LÝ THUYẾT SỐ
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2014
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THÙY DUNG
CÁC THUẬT TOÁN CƠ BẢN
TRONG LÝ THUYẾT SỐ
Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP
Mã số : 60.46.01.13
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS. TS. TẠ DUY PHƯỢNG
Thái Nguyên - Năm 2014
i
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Mở đầu 1
Nội dung 3
1 Các thuật toán cơ bản trong lý thuyết số 3
1.1 Tìm thương và số dư . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thuật toán Euclid phân tích một số ra thừa số nguyên tố . 6
1.3 Thuật toán tìm ước số chung lớn nhất . . . . . . . . . . . . 8
1.4 Thuật toán tìm bội số chung nhỏ nhất . . . . . . . . . . . . 12
1.5 Thuật toán Lucas - Lehmer tìm số nguyên tố . . . . . . . . 15
1.6 Thuật toán Miller tìm số giả nguyên tố . . . . . . . . . . . 18
1.7 Một số thuật toán trong mật mã công khai . . . . . . . . . 23

Mở đầu
Cùng với sự phát triển của máy tính điện tử, tin học ngày càng
xâm nhập sâu hơn vào chương trình giảng dạy toán, thậm chí ở cấp phổ
thông. Một số thuật toán trong lý thuyết số đã được biết đến từ thời
Euclid. Tuy nhiên, thực thi chúng với các số lớn không dễ dàng nếu không
có máy tính điện tử. Cùng với sự phát triển của toán và tin học, nhiều
thuật toán mới ra đời, đáp ứng những đòi hỏi mới của thực tế (mật mã
hóa công khai, phân tích các số nguyên tố lớn, ). Vì vậy, ngành số học
thuật toán đã ra đời. Việc tổng hợp, nghiên cứu và xây dựng các chương
trình tính toán trong số học là một công việc thú vị và hữu ích. Để đáp
ứng nhu cầu học tập và giảng dạy, tác giả đã chọn đề tài “ Các thuật toán
cơ bản trong lý thuyết số”.
Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh
mục các tài liệu tham khảo.
Chương 1 Các thuật toán cơ bản trong lý thuyết số
Trình bày các thuật toán cơ bản trong Lý thuyết số (tìm ước số chung lớn
nhất, bội số chung nhỏ nhất, tìm số dư và thương khi chia một số nguyên
cho một số nguyên khác, thuật toán Euclid phân tích một số ra thừa số
nguyên tố, thuật toán Lucas- Lehmer tìm số nguyên tố, thuật toán Miller
tìm số giả nguyên tố).
2
Chương 2 Lập trình và thực thi trên máy tính điện tử một số
thuật toán số học
Trình bày các chương trình có sẵn hoặc tự lập trình cho các thuật toán
đã nêu trong chương 1. Thực thi trên máy tính điện tử khoa học (Vinacal
570ES Plus II), chương trình Pascal và chương trình tính toán trên Maple.
3
Chương 1
Các thuật toán cơ bản trong lý
thuyết số

Sự tồn tại
Xét tập hợp S = {a − nb, n ∈ Z}.
Ta khẳng định rằng S chứa ít nhất một số nguyên không âm. Có hai trường
hợp như sau.
Nếu b < 0, thì −b > 0, và theo tính chất Archimede, có một số nguyên n
sao cho −bn ≥ −a, nghĩa là a −bn ≥ 0.
Nếu b > 0, thì cũng theo tính chất Archimede, có một số nguyên n sao
cho bn ≥ −a, nghĩa là a −b (−n) = a + bn ≥ 0.
Như vậy S chứa ít nhất một số nguyên không âm. Theo nguyên lý sắp thứ
tự tốt, trong S có một số nguyên không âm nhỏ nhất, ta gọi số ấy là r.
Đặt q =
a −r
b
, thì q và r là các số nguyên và a = qb + r. Ta còn phải
5
chỉ ra rằng 0 ≤ r < |b|. Tính không âm của r là rõ ràng theo cách chọn r.
Ta sẽ chứng tỏ dấu bất đẳng thức thứ hai.
Giả sử ngược lại r ≥ |b|. Vì b = 0, r > 0 nên b > 0 hoặc b < 0.
Nếu b > 0, thì r ≥ b suy ra a −qb ≥ b. Từ đó a −qb −b ≥ 0, lại dẫn tới
a −(q + 1) b ≥ 0.
Đặt r

= a − (q + 1) b thì r

∈ S và r

= a − (q + 1) b = r − b < r, điều
này mâu thuẫn với tính chất r là phần tử không âm nhỏ nhất của S.
Nếu b < 0 thì r ≥ −b do đó a−qb ≥ −b. Từ đó suy ra rằng a−qb+b ≥ 0,
tiếp tục suy ra r


= r −r

.
Nếu b > 0 thì r

≤ r và r < b ≤ b + r

, và như vậy r − r

< b. Còn nếu
b < 0 thì r ≤ r

và r

< −b ≤ −b + r, và do đó −

r − r


< −b. Trong cả
hai trường hợp ta có


r − r



< |b|.
Mặt khác đẳng thức b


= 0. Nhưng vì


r − r



≤ |b|,
nên chỉ có thể r = r

. Thay vào đẳng thức b

q

− q

=

r − r


ta có
bq = bq

và vì b khác 0, nên q = q

. Tính duy nhất đã được chứng minh.
Thuật toán chia Để chia một số tự nhiên a cho một số tự nhiên d (a > d),
ta thực hiện theo ví dụ sau:

p
α
2
2
p
α
n
n
, trong đó p
1
, , p
n
là các số nguyên
7
tố, α
i
là các lũy thừa của p
i
.
Định lí 1.2 Mọi hợp số n đều có ước nguyên tố p ≤
√
n.
Thuật toán Thuật toán đơn giản nhất phân tích một số a ra thừa số
nguyên tố là ta lần lượt kiểm tra số đó có là bội của các số nguyên tố p
i
(p
i
lần lượt bằng 2, 3, 5, 7, 11, 13, 17, 19, 23, ) không. Nếu có, ta được
a = bp
α

13, 17, 19, 23 không. Cuối cùng ta được 29601 = 3
2
× 11 × 13 ×23.
Nhận xét Số 29601 không quá lớn và phân tích ra thừa số tương đối dễ
(vì 29601 có các ước số nhỏ, chỉ là 3, 11, 13, và 23). Tuy nhiên thuật toán
8
phân tích ra thừa số nguyên tố được thực hiện bằng tay cho số 29601 cũng
đã khá vất vả. Vì vậy hiện nay bài toán phân tích một số ra thừa số nguyên
tố, thường được thực hiện trên máy tính với những phần mềm dựa trên
các thuật toán phân tích nhanh một số ra thừa số nguyên tố.
1.3 Thuật toán tìm ước số chung lớn nhất
Nếu số nguyên a chia hết cho số nguyên d, a được gọi là bội của
d. Số nguyên dương d lớn nhất là ước của cả hai số nguyên a, b được gọi
là ước số chung lớn nhất, viết tắt là ƯSCLN, hay còn gọi tắt là ước chung
lớn nhất, viết tắt là ƯCLN, của a và b (tiếng Anh: Greatest Common
Divisor-GCD). Ta thường kí hiệu ƯCLN của a và b là (a, b). Trong trường
hợp cả hai số nguyên a và b đều bằng 0 thì chúng không có ƯCLN vì khi
đó mọi số tự nhiên khác 0 đều là ước chung của a và b. Nếu chỉ một trong
hai số a hoặc b bằng 0, số kia khác 0, thì ƯCLN của chúng bằng giá trị
tuyệt đối của số khác 0.
1.3.1 Thuật toán Euclid
Thuật toán Euclid là một giải thuật giúp tính ước số chung lớn nhất
(ƯSCLN) của hai số một cách hiệu quả. Giải thuật này đã được biết đến
từ khoảng năm 300 trước Công nguyên. Nhà toán học Hy Lạp Euclid đã
viết giải thuật này trong cuốn sách toán nổi tiếng Elements.
Trước tiên, ta nhớ lại tính chất sau. Với mọi số nguyên k ta có
(a, b) = (a + kb, b). (1.3.1)
Thật vậy, giả sử (a, b) = d. Suy ra a = k
1
d, b = k

0
, b = r
1
)
r
0
= r
1
q
1
+ r
2
, 0  r
2
< r
1
,
r
1
= r
2
q
2
+ r
3
, 0  r
3
< r
2
,

n
q
n
.
Các số r
2
, r
3
, , r
n
≥ 0 và giảm dần. Vì vậy cuối cùng số dư bằng 0.
Áp dụng công thức (1.3.1) ta có
(a, b) = (r
0
, r
1
) = (r
1
, r
2
) = (r
2
, r
3
) = = (r
n−1
, r
n
) = (r
n

2

. Lặp lại bước này cho đến
khi ít nhất một trong hai số a, b lẻ để tìm k là số mũ của 2.
4) Nếu a chẵn, b lẻ thì (a, b) =

a
2
, b

. Tương tự với trường hợp a lẻ, b chẵn.
5) Nếu a, b đều lẻ thì (a −b) chẵn và |a −b| < max(a, b).
a) Nếu a ≥ b thì (a, b) =

a −b
2
, b

,
b) Nếu a < b thì (a, b) =

b −a
2
, a

.
6) Lặp lại bước 4 và 5 đến khi a = b(= c) hoặc b = 0. Thuật toán kết thúc
và in ra: (a, b) = c. 2
k
.

b
2
= k
2
d

. Do đó
(a, b) = 2

a
2
,
b
2

. (1.3.3)
Nếu a chẵn, b lẻ thì (a, b) = d, a = 2k

1
d, b = k
2
d, suy ra
a
2
= k

1
d,
b = k
2

(32, 3) =
2
3
(16, 3) = 2
3
(8, 3) = 2
3
(4, 3) = 2
3
(1, 3) = 2
3
(1, 1) = 2
3
.1 = 8.
1.3.3 Thuật toán Euclid mở rộng
Thuật toán này không những cho ta tìm ước chung lớn nhất của hai số a
và b mà còn cho ta biểu diễn nó dưới dạng tổ hợp tuyến tính của a và b.
Nếu (a, b) = d, thì tồn tại hai số nguyên m, n sao cho d = ma + nb.
Bổ đề: ƯCLN của các số nguyên a và b là số nguyên dương d nhỏ nhất
biểu diễn được dưới dạng tổ hợp tuyến tính của a và b.
Chứng minh Giả sử d là số nguyên dương nhỏ nhất biểu diễn được dưới
dạng d = ma + nb. Ta cần chứng minh d là ƯCLN của a và b.
Thật vậy, xét phép chia a = dq + r( 0 ≤ r < d).
Suy ra
r = a −dq = a −(ma + nb)q = (1 −m)a − nqb.
Chứng tỏ r cũng là một tổ hợp tuyến tính của a và b. Vì 0 ≤ r < d nên
r = 0. Như vậy d là ước của a. Tương tự, d cũng là ước của b, suy ra d
là ước chung của a và b. Lấy ước chung tùy ý d

của a và b. Dễ thấy d

= =
mr
0
+ nr
1
= ma + nb.
Vậy ta có điều phải chứng minh.
Thuật toán Euclid mở rộng
Cho hai số nguyên không âm u, v tìm (u
1
, u
2
, u
3
) sao cho
(u, v) = u
3
= uu
1
+ vu
2
.
12
Trong tính toán ta thêm các ẩn phụ (v
1
, v
2
, v
3
), (t

, u
3
) ← (1, 0, u), (v
1
, v
2
, v
3
) ← (0, 1, v).
Bước 2. ( Kiểm tra v
3
= 0?) Nếu v
3
= 0 thuật toán kết thúc.
Bước 3. ( Chia, trừ) Nếu v
3
= 0, đặt q ←

u
3
v
3

, sau đó đặt
(t
1
, t
2
, t
3

3
) ← (t
1
, t
2
, t
3
),
và quay lại Bước 2.
Ví dụ 1.5 Cho a = 2013, b = 122. Dùng thuật toán Euclid mở rộng ta có
Bước 1. u
1
= 1, u
2
= 0, u
3
= 2013, v
1
= 0, v
2
= 1, v
3
= 122.
Bước 2. q =

2013
122

= 16, t
1

u
1
= 1, u
2
= −16, u
3
= 61, v
1
= 1, v
2
= 33, v
3
= 0.
Ta có biểu diễn 2013.1 −16.122 = 61 .
1.4 Thuật toán tìm bội số chung nhỏ nhất
Bội số chung nhỏ nhất, viết tắt là BSCNN, hay còn gọi tắt là
bội chung nhỏ nhất, viết tắt là BCNN (tiếng Anh: least common multiple
hoặc lowest common multiple-lcm) của hai số nguyên a và b là số nguyên
dương nhỏ nhất chia hết cho cả a và b. Bội số chung của hai số a và b được
kí hiệu là [a, b], BCNN(a, b) hoặc lcm(a, b).
Nếu a hoặc b bằng 0, thì không tồn tại số nguyên dương chia hết cho a và
b, khi đó quy ước rằng lcm (a, b) là 0.
13
Định nghĩa trên được tổng quát hoá cho nhiều số nguyên dương: Bội chung
nhỏ nhất của a
1
, a
2
, , a
n

hay nhiều số.
Ví dụ 1.6
LCM(88, 212) =
88.212
GCD(88, 212)
=
88.212
4
=
18656
4
= 4664.
Bởi GCD(a, b) là ước số của cả a và b, nên sẽ thuật lợi hơn nếu tính LCM
bằng cách chia trước khi nhân
LCM(a, b) =

|a|
GCD(a, b)

. |b| =

|b|
GCD(a, b)

. |a|.
Điều này làm giảm kích thước đầu vào, giảm bộ nhớ cho các giá trị trung
gian. Làm theo cách này thì ví dụ trên trở thành
LCM(88, 212) =
88
GCD(88, 212)

1
và 53
1
.
Do đó
LCM (212, 88, 2014) = 2
3
.11.19.53 = 88616.
Thuật toán này dựa trên thuật toán phân tích một số nguyên ra thừa số
nguyên tố, sau đó lấy tích của các thừa số nguyên tố với số mũ cao nhất.
Tuy nhiên, ta chưa có thuật toán hiệu quả để phân tích một số nguyên ra
thừa số nguyên tố, vì vậy, về mặt thực tế, thuật toán vừa nêu không thực
sự hiệu quả. Mặc dầu vậy, nó khá đơn giản để minh họa khái niệm.
15
1.5 Thuật toán Lucas - Lehmer tìm số nguyên tố
Trong số học thuật toán, kiểm tra Lucas–Lehmer là phép kiểm
tra tính nguyên tố đối với số tự nhiên n, nó đòi hỏi rằng có một thừa số
nguyên tố của n − 1 là đã biết. Nếu tồn tại số a nhỏ hơn n và lớn hơn 1
là số thoả mãn
a
n−1
≡ 1 (modn) và a
n−1
q
≡ 1(modn).
Với mọi ước nguyên tố q của n −1, thì n là số nguyên tố. Nếu không tìm
thấy số a như vậy thì n là hợp số.
Ví dụ 1.9 Với n = 71, n −1 = 70 = 2 × 5 × 7.
Lấy a = 11 trước hết: 11
70

19
− 1, 2
31
− 1, 2
61
− 1,
Năm 1953 lần đầu tiên máy tính giúp giải quyết một giả thuyết số học:
bằng máy tính người ta đã tìm ra được các số nguyên tố Mersenne có dạng
2
p
− 1 với p = 521, 607, 1279, 2203, 2281. Tuy nhiên giả thuyết có vô số
các số nguyên tố Mersenne dạng 2
p
− 1 cho tới nay vẫn chưa được chứng
minh. Các số Mersenne quan trọng ở chỗ nó liên quan mật thiết tới các
vấn đề khác của số học như số hoàn chỉnh (xem Mục 2.2.8).
16
Việc tìm ra số nguyên tố Mersenne được coi là rất khó khăn trước đây.
Phương pháp tốt nhất để kiểm tra tính nguyên tố của các số Mersenne
được dựa vào sự tính toán một dãy tuần hoàn, được phát biểu đầu tiên
bởi Lucas năm 1878 và chứng minh bởi Lehmer vào những năm 1930.
Kiểm tra Lucas-Lehmer với số Mersenne
Cho p là số nguyên tố lẻ, M
p
= 2
p
− 1, chuỗi S
i
với i ≥ 0 được xác định
bởi S

= 14
2
− 2(mod31) = 194(mod31) = 8,
S
4
= 8
2
− 2(mod31) = 62(mod31) = 0.
Vậy M
5
= 2
5
− 1 = 31 là số nguyên tố.
Ví dụ 1.11 Kiểm tra M
11
= 2
11
−1 = 2047 có là số nguyên tố hay không?
Ta có
S
1
= 4,
S
2
= 4
2
− 2(mod2047) = 14(mod2047) = 14,
S
3
= 14

2
− 2(mod2047) = 57598(mod2047) = 282,
17
S
10
= 282
2
− 2(mod2047) = 79522(mod2047) = 1736.
Vì S
10
> 0 nên M
11
= 2
11
− 1 = 2047 không là số nguyên tố Mersenne
(2047 = 23 ×89).
Đã có các thuật toán nhanh để tìm số nguyên tố Mersenne, do đó hiện nay
đã biết các số nguyên tố Mersenne rất lớn. Bốn số nguyên tố Mersenne
đầu tiên M
2
= 3, M
3
= 7, M
5
= 31 và M
7
= 127 đã được biết từ cổ xưa.
Số thứ năm, M
13
= 8191, được tìm thấy vào trước năm 1461. Hai số tiếp

, đã được
tìm thấy do Computer này sau gần hai giờ chạy máy. Ba số tiếp theo
M
1279
, M
2203
, M
2281
đã được tìm thấy với cùng chương trình trên sau
nhiều tháng nữa. M
4253
là số nguyên tố Mersenne đầu tiên là số nguyên
tố siêu lớn trên 1000 chữ số thập phân (Titanic). Và M
44497
là số nguyên
tố đầu tiên có trên 10.000 chữ số thập phân (Gigantic). Chưa khẳng định
được có số nguyên tố Mersenne nào nằm giữa số thứ 40 (M
20996011
) và
18
48 (M
57885161
) trong bảng mà chưa được phát hiện hay không, do đó thứ
tự các số đó là tạm thời. Một ví dụ là số thứ 29 được phát hiện ra sau
số thứ 30 và 31, số thứ 46 cũng được công bố trước số 45 chỉ có 2 tuần.
Đến tháng 2-2013, chỉ mới biết 48 số nguyên tố Mersenne. Số lớn nhất
đã biết là số M
57885161
với 17 425 170 chữ số. Cũng như nhiều số nguyên
tố Mersenne trước đó, nó được tìm ra nhờ dự án Distributed Computing


280
≡ 1(mod 3),
19
2
560
=

2
10

56
≡ 1(mod 11),
2
560
=

2
16

35
≡ 1(mod 17).
Từ đó suy ra 2
560
≡ 1(mod 561).
Theo [1], trong 10 tỷ số tự nhiên đầu tiên có 455052512 số nguyên tố nhưng
chỉ có 14884 số giả nguyên tố cơ sở 2. Như vậy tỉ lệ số giả nguyên tố là rất
ít. Tuy nhiên đối với mọi cơ sở tùy ý, các số giả nguyên tố là vô hạn.
Định lý 1.3 Có vô số số giả nguyên tố cơ sở 2.
Giả sử n là một số giả nguyên tố cơ sở 2, ta sẽ chứng minh N = 2

n
−1
− 1

= 2dn, ( do 2
n
− 1 ≡ 1 modn).
2
N−1
= 2
nd
= (2
n
)
2d
≡ 1(modN).
Vậy N là số giả nguyên tố cơ sở 2.
Như vậy, để kiểm tra một số có phải là số nguyên tố hay không,trước tiên
ta kiểm tra xem nó có là số giả nguyên tố cơ sở 2 hay không sau đó kiểm
tra tiếp tục với các cơ sở khác. Tuy nhiên, tồn tại các số giả nguyên tố với
mọi cơ sở, đó là các số Carmichael.
Số Carmichael Hợp số nguyên n là số giả nguyên tố Fermat với mọi cơ
số nguyên dương a sao cho (a, n) = 1 được gọi là số Carmichael.
Ví dụ 1.13 Số nguyên 561 = 3. 11. 17 là một số Carmichael.
Thật vậy,với a tùy ý, (a, 561) = 1 thì suy ra (a, 3) = (a, 11) = (a, 17) = 1.
20
Theo dịnh lý Fermat bé ta có
a
2
≡ 1(mod3), a

35
≡ 1(mod17).
Từ đó suy ra a
560
≡ 1(mod 561). Vậy 561 là số Carmichael.
Số Carmichael khá hiếm, chỉ có 7 số nhỏ hơn 10000: 561, 1105, 1729, 2465,
2821, 6601, 8911.
Kiểm tra Miller và số giả nguyên tố mạnh
Giả sử n là số nguyên dương lẻ, n − 1 = 2
s
t, trong đó s là số nguyên
không âm, t là số nguyên dương lẻ. Ta nói n trải qua được kiểm tra Miller
cơ sở a nếu a
t
≡ 1(mod n) hoặc a
2
j
t
≡ −1(modn), với 0 ≤ j ≤ s − 1.
Định nghĩa 1.2 Số nguyên n được gọi là số giả nguyên tố mạnh cơ sở a
nếu nó là hợp số và trải qua được kiểm tra Miller cơ sở a.
Ví dụ 1.14 2047 là số giả nguyên tố mạnh cơ sở 2.
Thật vậy, 2047 = 23. 89, n −1 = 2.1023, s = 1, t = 1023,
2
2046
≡ 1(mod2047)suyra 2
2
t
≡ 1(mod2047).
Như vậy 2047 trải qua được kiểm tra Miller cơ sở 2.