ĐẠ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


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

1.8

Một số thuật toán khác . . . . . . . . . . . . . . . . . . . . 28


2.6

Tìm số nguyên tố đứng sau hoặc đứng trước một số tự nhiên 74

2.7

Một số ứng dụng trong lý thuyết mật mã . . . . . . . . . . 75

2.8

Maple và một số giả thuyết về số nguyên tố . . . . . . . . . 77

Kết luận

82

Tài liệu tham khảo

84


ii

LỜI CẢM ƠN
Với lòng kính trọng và biết ơn sâu sắc em xin chân thành cảm
ơn thày PGS. TS. Tạ Duy Phượng đã hướng dẫn và chỉ bảo tận tình cho
em trong suốt quá trình làm luận văn. Thầy không chỉ truyền thụ những
tri thức khoa học mà còn chỉ dẫn cho em những phương pháp làm việc tốt
cùng những lời động viên khuyến khích kịp thời.
Em cũng xin gửi lời cảm ơn chân thành đến Ban giám hiệu, phòng

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ố
Chương này trình bày một số thuật toán cơ bản liên quan đến
ước chung lớn nhất, bội chung nhỏ nhất, tìm số nguyên tố, phân tích một
số ra thừa số nguyên tố. . . Các vấn đề trình bày trong chương này được
tham khảo và trích dẫn chủ yếu từ một số tài liệu [4], [5], [6].

1.1

Tìm thương và số dư
Cơ sở lý thuyết của phép chia với dư là định lý về phép chia có

dư. Định lý này được ứng dụng trong giải thuật Euclid tìm ước chung lớn
nhất của hai số nguyên khác 0.
Định lý về phép chia với dư: Với hai số tự nhiên a và b bất kì (a > b),

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.
a−r
Đặt q =
, thì q và r là các số nguyên và a = qb + r. Ta còn phải
b


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 = a−(q − 1) b ≥ 0. Do đó, r ∈ S và vì r = r+b với b < 0
ta có r = a − (q − 1) b < r, mâu thuẫn với giả thiết r là số nguyên không
âm nhỏ nhất trong S . Như vậy ta đã chứng minh sự tồn tại của q và r.
Tính duy nhất
Giả sử rằng tồn tại q , q , r, r với 0 ≤ r, r < |b| sao cho a = q + r và

a = q + r . Không mất tính tổng quát giả sử q ≤ r .
Từ hai đẳng thức trên ta có b q − q = 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

301. Chia 301 (3010) cho 135 được 2 dư 31 (310). Hạ nốt 4 được 314 chia
135 được 2 dư 44.
Vậy a = 1542014 = 135 × 11422 + 44.
Thuật toán chia được thực hiện trong Bảng 1 dưới đây. Thuật toán này
đã được lập trình để máy tính tự động thực hiện tính toán.

1 5 4 2 0 1 4 1 3 5
1 9 2
1 1 4 2 2
5 7 0
3 0 1
3 1 4
4 4
Bảng 1

1.2

Thuật toán Euclid phân tích một số ra thừa số
nguyên tố
Số nguyên tố là số nguyên lớn hơn 1, không chia hết cho số

nguyên dương nào ngoài 1 và chính nó. Số nguyên lớn hơn 1 không phải
là số nguyên tố được gọi là hợp số.
Định lí 1.1 Mọi số tự nhiên đều có duy nhất một phân tích thành tích
của các thừa số nguyên tố, tức là mọi số tự nhiên a đều có thể viết được
duy nhất dưới dạng a = pα1 1 pα2 2 ...pαnn , trong đó p1 , ..., pn là các số nguyên


7


Vì 299 không chia hết cho 11 nên ta kiểm tra tiếp xem 299 có chia hết cho
13, 17, 19, 23 không. Cuối cùng ta được 29601 = 32 × 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 đã


r2 = r3 q3 + r4 ,

0

r4 < r3 ,

...

...

rn−2 = rn−1 qn−1 + rn ,

0

rn < rn−1 ,

rn−1 = rn qn .
Các số r2 , r3 , ..., rn ≥ 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) = (r0 , r1 ) = (r1 , r2 ) = (r2 , r3 ) = ... = (rn−1 , rn ) = (rn , 0) = rn .
Do đó, ước chung lớn nhất của a và b là số dư cuối cùng khác 0 trong quá
trình chia lặp đi lặp lại ở trên.Thuật toán kết thúc và in ra kết quả là rn .
Ví dụ 1.3 Tìm ước chung lớn nhất của 330 và 140.
Theo thuật toán Euclid ta có

330 = 140.2 + 50,
140 = 50.2 + 40,
50 = 40.1 + 10,

b−a
b) Nếu a < b thì (a, b) =
,a .
2
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
3) Nếu a, b là các số chẵn thì (a, b) = 2

và in ra: (a, b) = c. 2k .
Chứng minh
Giả sử (a, b) = d, suy ra a = k1 d, b = k2 d trong đó (k1 , k2 ) = 1.
Áp dụng (1.3.1) ta có:

(a, b) = (a − b, b) .

(1.3.2)

Nếu a, b là các số chẵn thì (a, b) = d = 2d , suy ra a = 2k1 d , b = 2k2 d
b
a
hay = k1 d , = k2 d . Do đó
2
2
a b
(a, b) = 2
,
.
(1.3.3)
2 2
a
Nếu a chẵn, b lẻ thì (a, b) = d, a = 2k 1 d, b = k2 d, suy ra = k 1 d,

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 là
ước của d. Vậy d chính là ƯCLN của a và b.
Ngược lại, (a, b) = d, a = r0 , b = r1 . Theo thuật toán Euclid ta có

(r0 , r1 ) = rn = rn−2 − rn−1 qn−1 = rn−2 − (rn−3 − rn−2 qn−2 )qn−1 = .... =
mr0 + nr1 = 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 (u1 , u2 , u3 ) sao cho

(u, v) = u3 = uu1 + vu2 .


12

Trong tính toán ta thêm các ẩn phụ (v1 , v2 , v3 ), (t1 , t2 , t3 ) sao cho luôn có:

ut1 + vt2 = t3 , uv1 + vv2 = v3 , uu1 + vu2 = u3 .

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 a1 , a2 , ..., an là số nguyên dương nhỏ nhất là bội số của

a1 , a2 , ..., an . Kí hiệu tương tự cho bội số chung nhỏ nhất của a1 , a2 , ..., an
là lcm(a1 , a2 , ..., an ).

Tìm bội chung nhỏ nhất bằng cách tính qua ước chung lớn nhất
Quan hệ giữa bội số chung nhỏ nhất (LCM) và ước số chung lớn nhất
(GCD) của hai số tự nhiên a và b được mô tả theo công thức sau
LCM (a, b) =

a×b
.
GCD (a, b)

Như vậy, trước tiên ta tìm ước số chung lớn nhất của a và b. Sau đó tìm
bội số chung nhỏ nhất của a và b theo công thức trên.

88
88
.212 = .212 = 22.212 = 4664.
GCD(88, 212)
4


14

Tìm bội chung nhỏ nhất bằng cách phân tích ra thừa số nguyên tố
Định lý cơ bản của số học nói rằng mọi số nguyên dương lớn hơn 1 có thể
biểu diễn một cách duy nhất dưới dạng tích các số nguyên tố (nếu không
kể đến thứ tự của các thừa số). Như vậy, có thể coi hợp số cấu thành từ
các số nguyên tố.
Ví dụ 1.7 1988 = 2.2.7.71 = 22 . 7. 71.
Ở đây chúng ta có hợp số 1988 tạo thành bởi hai thừa số nguyên tố 2,
một thừa số nguyên tố 7 và một thừa số nguyên tố 71. Kiến thức này giúp
chúng ta tìm bội chung nhỏ nhất của một tập hợp các số.
Ví dụ 1.8 Tìm bội chung nhỏ nhất của ba số 212, 88 và 2014.
Đầu tiên, ta phân tích từng số thành tích lũy thừa của các số nguyên tố.

212 = 22 .53; 88 = 23 .11; 2014 = 2.19.53.
Với mỗi số nguyên tố, chọn lũy thừa cao nhất, tích của chúng cho ta giá
trị bội chung nhỏ nhất cần tìm. Bốn thừa số nguyên tố 2, 11, 19 và 53 có
bậc cao nhất lần lượt là 23 , 111 , 191 và 531 .
Do đó
LCM (212, 88, 2014) = 23 .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

1110 ≡ 31 ≡ 1 (mod 71).
Vậy 71 là số nguyên tố.
Số Mersenne và kiểm tra Lucas- Lehmer
Số Mersenne là số có dạng 2p − 1, trong đó p là số nguyên tố.
Người ta đã tìm thấy khá nhiều số nguyên tố Mersenne: 22 − 1, 23 − 1,

25 − 1, 27 − 1, 213 − 1, 217 − 1, 219 − 1, 231 − 1, 261 − 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

2p − 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 2p − 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ẻ, Mp = 2p − 1, chuỗi Si với i ≥ 0 được xác định
bởi S1 = 4, ...Si+1 = Si 2 − 2(modMp ).

Mp là số nguyên tố ⇔ Sp−1 = 0.
Ví dụ 1.10 Kiểm tra M5 = 25 − 1 = 31 có là số nguyên tố hay không?
Ta có



M31 được kiểm tra bởi Euler vào năm 1750. Số tiếp theo (trong Lịch sử
không theo thứ tự số ) là M127 do Lucas tìm thấy vào năm 1876, sau đó

M61 do Pervushin tìm vào năm 1883. Hai số nữa M89 và M107 được tìm
thấy vào thế kỷ 20, bởi Powers vào năm 1911 và 1914.
Việc tìm các số nguyên tố Mersenne thực sự được cách mạng bởi các
máy tính điện tử số. Thành công đầu tiên của tư tuởng này thuộc về số
nguyên tố Mersenne, M521 , nhờ nỗ lực khéo léo vào lúc 10:00 P.M. ngày
30-1, 1952 khi sử dụng máy tính tự động Western U.S. National Bureau of
Standards (SWAC) tại Institute for Numerical Analysis thuộc University
of California, Los Angeles, dưới sự điều khiển trực tiếp của Lehmer, sử
dụng chương trình viết và chạy bởi Prof. R.M. Robinson. Nó là số nguyên
tố Mersenne đầu tiên tìm thấy sau 38 năm. Số tiếp theo, M607 , đã được
tìm thấy do Computer này sau gần hai giờ chạy máy. Ba số tiếp theo

M1279 , M2203 , M2281 đã được tìm thấy với cùng chương trình trên sau
nhiều tháng nữa. M4253 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à M44497 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 (M20996011 ) và


18

48 (M57885161 ) 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ố M57885161 với 17 425 170 chữ số. Cũng như nhiều số nguyên


2560 = 210

56

≡ 1(mod 11),

2560 = 216

35

≡ 1(mod 17).

Từ đó suy ra 2560 ≡ 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 = 2n − 1
cũng là số giả nguyên tố cơ sở 2.
Ta có n = km, 1 < k, m < n và 2n − 1 ≡ 1(mod n).

N = 2n − 1 = 2km − 1 = 2k − 1 . 2k

(m−1)

+ ... + 1 .

Dễ thấy N là hợp số. Lại có


≡ 1(mod11),

a560 = a16

35

≡ 1(mod17).

Từ đó suy ra a560 ≡ 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 = 2s 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
j

cơ sở a nếu at ≡ 1(mod n) hoặc a2 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,
t

22046 ≡ 1(mod2047)suyra 22 ≡ 1(mod2047).
Như vậy 2047 trải qua được kiểm tra Miller cơ sở 2.
Định lý 1.4 Có vô số số giả nguyên tố mạnh cơ sở 2.
Thật vậy, giả sử n là số giả nguyên tố cơ sở 2. Đặt N = 2n − 1, khi đó

N − 1 = 2n − 2 = 2(2n − 1) = 2s t, s = 1, t = 2n − 1.