1

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

NGUYỄN THANH BẰNG

VỀ CÁC DÃY SỐ
NGUYÊN TỐ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGHỆ AN - 2013


2

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

NGUYỄN THANH BẰNG

VỀ CÁC DÃY SỐ
NGUYÊN TỐ VÀ ỨNG DỤNG

CHUYÊN NGÀNH: ĐẠI SỐ VÀ LÝ THUYẾT SỐ

Mã số: 60 46 05

LUẬN VĂN THẠC SĨ TOÁN HỌC


12

1.3

Phương trình Fermat với số mũ của ẩn là số nguyên tố………

14

CHƯƠNG 2
MỘT SỐ BÀI TOÁN VỀ SỐ NGUYÊN TỐ
CÓ ỨNG DỤNG TRONG LÝ THUYẾT MẬT MÃ

19

2.1

Bài toán kiểm tra số nguyên tố lớn………….…..……………

19

2.2

Bài toán phân tích thành thừa số nguyên tố...……...…………

27

2.3

Hệ mã mũ của Pohlig và Hellman………………….…………


Trùm lên trên các số nguyên tố dường như có một sự huyền bí nào đó. Sự phân
bố của các số nguyên tố tỏ ra rất phức tạp và không có quy luật. S.G. Telang
(xem [8]) viết: Chưa ai có thể đưa ra lý do phân tích được sự phân bố không
quy luật của các số nguyên tố (Nobody has been able to put forward any reason
which will account for this extreme irregularity in the distribution of primes).
Việc tìm các số nguyên tố lớn trong một thời gian dài là sự quan tâm của
nhiều nhà toán học. Cho phép chúng tôi nhắc lại ở đây một vài tên tuổi của các
nhà toán học lớn trong lịch sử nhân loại gắn liền với các kết quả nghiên cứu về
số nguyên tố: Euclid, Euler, Goldbach, Fermat, Dirichlet, Waring, Wilson,
Leibniz, Vinogradov, Brun, J. R. Chen, P. M. Ross, … . Tuy nhiên, đến nay
trong Số học vẫn còn tồn tại nhiều giả thuyết mở về số nguyên tố.
Hơn nữa, trong thời đại công nghệ thông tin ngày nay việc nghiên cứu về
số nguyên tố càng được kích thích bởi sự kiện là các số nguyên tố tỏ ra rất có ích
trong việc mã hóa và giải mã các thông tin. Tính bảo mật và an toàn của hệ mật
mã RSA (do ba nhà khoa học của Học viện Công nghệ Massachusetts công bố
năm 1978) được đảm bảo bằng độ phức tạp của bài toán số học phân tích một số
nguyên thành tích các thừa số nguyên tố. Nói khác đi, vấn đề thời gian tiêu tốn


5
cho việc chạy máy tính để thực hiện bài toán phân tích một số nguyên đủ lớn
thành tích các thừa số nguyên tố, được sử dụng làm chỉ tiêu định lượng đánh giá
độ an toàn của hệ mã RSA. Vì vậy, hệ mật mã này hiện được cộng đồng quốc tế
chấp nhận rộng rãi trong việc thực thi mật mã khóa công khai.
Nhân được đọc và dịch một phần của cuốn sách về Số học bằng tiếng Anh
được viết bởi của S.G.Telang – Giáo sư Trường Đại học Bombay, Ấn độ ([8]),
với mục đích tìm hiểu sâu hơn về ứng dụng của Số học trong lĩnh vực công nghệ
thông tin, chúng tôi tập trung tìm hiểu các vấn đề xung quanh số nguyên tố, dãy
số nguyên tố và ứng dụng của chúng trong Lý thuyết mật mã. Vì vậy, mục đích
chính của bản luận văn này là:

đã động viên và giúp đỡ tôi hoàn thành nhiệm vụ học tập.
Mặc dù đã có nhiều cố gắng, song luận văn vẫn còn nhiều thiếu sót, tác giả
mong nhận được sự đóng góp của thầy cô giáo và các đồng nghiệp.
TÁC GIẢ


7

CHƯƠNG 1
PHÂN BỐ SỐ NGUYÊN TỐ

1.1. Dãy số nguyên tố
Lý thuyết số có thể được cắt nghĩa ngắn gọn như là sự nghiên cứu các tính
chất của các số nguyên, trong đó có các số nguyên tố. Các số nguyên tố đóng một
vai trò rất quan trọng trong Lý thuyết số. Dù khái niệm về số nguyên tố rất đơn giản
nhưng các vấn đề liên quan đến chúng lại là rất khó. Thật ngạc nhiên khi định lý
đầu tiên quan trọng liên quan đến các số nguyên tố lại được chứng minh một cách
dễ dàng. Điều này liên quan đến câu hỏi: Có bao nhiêu số nguyên tố trong tập hợp
vô hạn các số nguyên dương? Một định lý nổi tiếng của Euclid khẳng định rằng có
vô hạn các số nguyên tố. Chứng minh của Euclid đơn giản một cách đáng ngạc
nhiên mà không cần một sự trợ giúp nào ngoài định nghĩa số nguyên tố. Đó là một
chứng minh tuyệt đẹp, dù rằng cho đến ngày nay nhân loại đã tìm được rất nhiều
cách chứng minh khác. Bài toán xác định các tập hợp con vô hạn của tập hợp các số
nguyên tố là những bài toán khó, thậm chí đã trở thành những giả thuyết lớn của Số
học mà hiện nay vẫn chưa có lời giải và được nhiều người trong và ngoài ngành
toán quan tâm.
1.1.1. Định nghĩa. 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ận xét rằng, mỗi số nguyên lớn hơn 1 luôn có ít nhất một ước nguyên tố.

3001-4000
4001-5000
106 - 106 +100
106+101-106+ 200
106+201-106+ 300
106+301-106+ 400
106+401-106+ 500

Số các số nguyên tố
168
135
127
120
113
6
10
8
8
7


9
Nhà toán học nổi tiếng Dirichlet (1805-1859) người Đức đã chứng minh
được định lý sau đây.
1.1.5. Định lý (Dirichlet [8]). Giả sử a, b là các số nguyên dương và nguyên tố
cùng nhau. Khi đó, tồn tại vô hạn các số nguyên tố có dạng ak + b, k Î ¥ .
Một số trường hợp riêng của Định lý Dirichlet có thể chứng minh dễ dàng
bằng cách sử dụng các kiểu lý luận áp dụng cho Định lý Euclid:
- Tồn tại vô hạn các số nguyên tố có dạng 4k + 3, k Î ¥ .
- Tồn tại vô hạn các số nguyên tố có dạng 6k + 5, k Î ¥ .

n −1
Chứng minh. (i) Từ k =   , ta suy ra k = hoặc k =
. Dẫn đến
2
2
2
n = 2k hoặc n = 2k + 1, tức là n ≥ 2k với mọi n.
n
(ii) Giả sử n ≥ 8. Khi đó k =   > 3 .
2
Nếu n = 2k + 1, thì theo Định lý 1.1.7, có n – (k – 1) = k + 2 < pk.
Nếu n = 2k, thì n – (k – 1) = k + 1 < pk . ■
2
1.1.9. Định lý (Bất đẳng thức Bonse). Nếu n > 3 thì pn+1 < p1 p2 L pn .

Chứng minh. Với n = 4, 5, 6, 7 kiểm tra trực tiếp và Bất đẳng thức Bonse
n
đúng. Với n ≥ 8 và k =   theo Hệ quả 1.1.8 ta có:
2
pk > n - (k - 1)
n ≥ 2k
và
Ta ký hiệu u = p1 p2 ... pk - 1 . Xét tập hợp

(1)
(2)

S = { u - 1, 2u - 1, ..., pk u - 1} .
Nhận thấy rằng không có số nguyên tố nào trong các số:
pk , pk +1 , ..., pn

ph+1 ≥ ph + 2 > 2h + 3 + 2 = 2(h + 1) + 3.
Như vậy định lý đúng với n = h + 1 . Theo quy nạp định lý đúng với n ≥ 9 . ■
n
1.1.11. Định lý. Giả sử k =   . Khi đó ta có:
3
(i) 3k £ n £ 3k + 2, " n ;
(ii) n - (k - 1) < pk , n ³ 27.
n
n
n −1
n−2
Chứng minh. (i) Từ k =   , ta suy ra k = hoặc k =
hoặc k =
.
3
3
3
3
Dẫn đến n = 3k, hoặc n = 3k + 1, hoặc n = 3k + 2. Vì vậy:
3k £ n £ 3k + 2, " n
n
(ii) Giả sử n ≥ 27. Khi đó k =   ≥ 9 .
3
Theo Định lý 1.1.10, có
n - (k - 1) £ 3k + 2 - (k - 1 )= 2k + 3 < pk . ■


12
3
1.1.12. Định lý. Nếu n > 4 , thì pn+1 < p1 p2 L pn .

và 30.


13
Chứng minh. Giả sử số nguyên N >1 thoả mãn tính chất P. Khi đó, mỗi
hợp số không vượt quá N, sẽ không nguyên tố cùng nhau với N.
Ta có nhận xét rằng, mỗi số nguyên N lớn hơn 3 hoặc là bình phương, hoặc
là nằm giữa các bình phương của hai số nguyên tố liên tiếp:
pn2 £ N < pn2+1
với n nào đó và pn là số nguyên tố thứ n. Từ đó suy ra rằng, mỗi số nguyên tố
p £ pn là ước của N, hay nói cách khác p 2 £ N là một hợp số và nguyên tố
cùng nhau với N. Điều này mâu thuẫn với giả thiết N là số có tính chất P. Vì
vậy, tất cả các số nguyên tố p1 , p2 ,..., pn là ước của N hay tích p1 p2 L pn cũng
là ước của N. Do đó, ta có
p1 p2 L pn £ pn2+1.
Mặt khác, theo Bất đẳng thức Bonse:
p1 p2 L pn > pn2+1 ; n > 3 .
Kiểm tra được rằng bất đẳng thức
p1 p2 L pn £ pn2+1.
2
2
đúng với n = 1, 2, 3. Từ đó suy ra n £ 3 . Kết hợp với pn £ N < pn+1 ta có

N < pn2+1 £ p42 = 7 2 = 49 .
Kiểm tra trực tiếp một cách khá đơn giản với những số nguyên bé hơn 49 ta
suy ra những số thoả mãn tính chất P chỉ là: 2, 3, 4, 6, 8, 12, 18, 24 và 30. ■
1.1.15. Giả thuyết Bertrand. Nếu n > 3 thì tồn tại ít nhất một số nguyên tố
giữa n và 2n – 2
Rõ ràng giả thuyết Bertrand mạnh hơn rất nhiều so với bất đẳng thức
Bonse. Còn có một giả thuyết khác nổi tiếng như sau:

phẳng phức ngoại trừ tại điểm s = 1 (simple pole).
Thật ra hàm zeta đã được nghiên cứu trước đó bởi Euler và một số người
khác, nhưng chỉ như một hàm với biến số thực. Nói riêng, Euler chỉ ra rằng
trong đó tích vô hạn (gọi là tích Euler) lấy trên tất cả các số nguyên tố. Tích này
hội tụ khi phần thực của s lớn hơn 1. Đây là một phiên bản giải thích cho Định
lý cơ bản của số học, rằng mỗi số nguyên có thể phân tích một cách duy nhất
thành các thừa số nguyên tố. Euler đã dùng tích này để chứng minh rằng tổng
nghịch đảo của các số nguyên tố là không bị chặn. Chính tích Euler đã thu hút
sự quan tâm của Riemann tới hàm zeta: khi đó ông đang cố gắng chứng minh
một giả thuyết của Legendre và trong một dạng chính xác hơn phát biểu bởi
Gauss:
t

p( x) ~ ò
2

dt
logt


15
trong đó p( x) là số các số nguyên tố nhỏ hơn x.
Riemann đã tạo ra một bước tiến lớn tới giả thuyết của Gauss. Ông nhận ra
rằng số phân bố các số nguyên tố phụ thuộc vào sự phân bố các không điểm của
hàm zeta.
Giả thuyết Riemann: Mỗi không điểm của hàm V đều nằm trên trên đường
1
thẳng Im(z)= .
2


n
1.2.4. Hệ quả. f ( n) = 2 - 1 là số nguyên tố chỉ khi n là số nguyên tố.

Như vậy, bài toán tìm hàm nguyên tố là chưa giải quyết được triệt để. Hiện
vẫn chưa tìm được một công thức f ( n) sao cho
f ( n ) = pn
với pn là số nguyên tố thứ n.
1.2.5. Giả thuyết Mersenne. Giả sử n £ 257. Khi đó, 2n - 1 là số nguyên tố chỉ
khi
n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.


17

1.3. Phương trình Fermat
với số mũ các ẩn là số nguyên tố
Trong tiết này của luận văn, nhờ công cụ số nguyên tố, chúng tôi diễn đạt
và kiểm tra sự tương đương về một dạng phát biểu đơn giản nhất của Định lý
sau cùng của Fermat mà A. Wiles đã sử dụng trong lời giải của mình.
1.3.1. Định lý sau cùng của Fermat
Ta thấy rằng phương trình có vô hạn nghiệm nguyên ( x, y, z ) .
Các bộ số Pythagorean cũng cho ta vô hạn nghiệm nguyên của phương
trình x 2 + y 2 = z 2 .
Tình hình sẽ như thế nào nếu số mũ của các ẩn tăng lên? Nói cách khác,
các phương trình
x n + y n = z n với n ≥ 3
có nghiệm nguyên hay không? Nếu có thì số nghiệm là hữu hạn hay vô hạn?
Đó chính là nội dung của Định lý sau cùng Fermat nổi tiếng, một trong
những câu hỏi lớn nhất của Toán học và chỉ mới nhận được câu trả lời trong thời
gian gần đây:

chứng minh của A. Wiles là đúng.
1.3.3. Mệnh đề. Nếu phương trình x n + y n = z n có nghiệm nguyên dương thì
phương trình x p + y p = z p cũng có nghiệm nguyên dương, với p là ước của n.
Chứng minh. Giả sử phương trình x n + y n = z n với n ≥ 3 , n ∈ Z có một
nghiệm nguyên (a, b, c ) , khi đó ta có: a n + bn = c n . Ta viết đẳng thức này lại như
sau:
p

p

p

 np   np   np 
 a ÷ + b ÷ = c ÷ .
     
n

n

n

Do đó, phương trình x p + y p = z p có nghiệm nguyên dương (a p , b p , c p ) . ■


19
1.3.4. Mệnh đề. Nếu Định lý sau cùng của Fermat đúng với n = 4 và với mọi số
nguyên tố lẻ thì Định lý này đúng với mọi số nguyên n ≥ 3 .
Chứng minh. Từ giả thiết của bài toán ta chỉ cần xét Định lý sau cùng của
Fermat với những hợp số n > 4 .
1) Nếu n > 4 là số lẻ thì tồn tại ước nguyên tố lẻ p của n. Do đó, nếu


2 2
0

= z02 ,

tức là { x02 , y02 , z0 } là một bộ số Pythagorean. Hơn nữa, ( x02 , y02 ) = 1, vì nếu p là số
2
2
nguyên tố, mà p x0 , p y0 thì p x0 , p y0 , mâu thuẫn với ( x0 , y0 ) = 1. Như vậy,

{x , y , z }
2
0

2
0

0

là một bộ số Pythagorean nguyên thuỷ và do đó tồn tại các số

nguyên dương m, n với ( m, n ) = 1, m ≡ n ( mod 2 ) và
x02 = m2 − n 2
y02 = 2mn
z0 = m2 + n 2 ,
trong đó ta có thể xem y 2 là số chẵn (nếu cần thì đổi kí hiệu x02 và y02 ).
Từ đẳng thức của x02 ta được
x02 + n2 = m2 .
Do ( m, n ) = 1 nên { x0 , n, m} là một bộ số Pythagorean nguyên thuỷ và do

2

có nghiệm nguyên dương (a, b, c 2 ) . Điều này mâu thuẫn với Định lý 1.3.5.

■

Như vậy, theo Định lí 1.3.5 và Hệ quả 1.3.6, chúng ta có thể phát biểu Định
lý Fermat dưới dạng đơn giản hơn như sau:
Phương trình x n + y n = z n , với n là số nguyên tố lẻ, không có nghiệm
nguyên dương.
Vào ngày 23 tháng 6 năm 1993, A. Wiles đã viết trên một bảng đen trước
các diễn giả tại Viện Newton ở Cambridge, nước Anh rằng: Nếu p là một số
nguyên tố, u, v và w là các số hữu tỉ và u p + v p + w p = 0 thì uvw = 0 . Như vậy,
A. Wiles đã lần đầu tiên thông báo rằng, ông ta có thể chứng minh được Định lý
sau cùng của Fermat.


23

CHƯƠNG 2
MỘT SỐ BÀI TOÁN VỀ SỐ NGUYÊN TỐ
CÓ ỨNG DỤNG TRONG LÝ THUYẾT MẬT MÃ
Chương này xét ba bài toán có vai trò quan trọng trong lý thuyết mật mã:
Kiểm tra số nguyên tố, phân tích một số nguyên thành tích của các thừa số
nguyên tố, tính lôgarit rời rạc của một số theo modulo nguyên tố.

2.1. Bài toán kiểm tra số nguyên tố lớn
Cho n là số nguyên bất kỳ. Làm thế nào để biết n là số nguyên tố hay
không? Bài toán được đặt ra từ những buổi đầu của Số học và trải qua hơn 2000
năm đến nay vẫn là một bài toán chưa có được những cách giải dễ dàng. Bằng

k =0
while k < sqrt(n) {
i=k+1
while Prime[i]=False i :=i+1
k=i
j =2
while k*j