ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ MINH HUỆ

SỐ GIẢ NGUYÊN TỐ VÀ ỨNG DỤNG

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

THÁI NGUYÊN - 2017


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN THỊ MINH HUỆ

SỐ GIẢ NGUYÊN TỐ VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số:

60 46 01 13

NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TSKH. HÀ HUY KHOÁI

THÁI NGUYÊN - 2017




Vấn đề lấy căn bậc hai modulo n . . . . . . . . . . .

10

1.1.3

Độ khó của việc tìm số không chính phương modulo p 11

Vấn đề sinh số nguyên tố lớn . . . . . . . . . . . . . . . . .

Chương 2. Một số loại số giả nguyên tố
2.1

11
14

Số giả nguyên tố . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.1

Khái niệm . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.2

Số Carmichael . . . . . . . . . . . . . . . . . . . .

4

Lời cảm ơn
Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học
Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Hà Huy
Khoái (Trường Đại học Thăng Long, Hà Nội). Tác giả xin được bày tỏ
lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình,
người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình
giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn.
Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học
- Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng
viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập
và nghiên cứu.
Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể lớp Cao học
Toán khóa 9B (2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong
suốt quá trình học tập.
Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào
tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Quang
Trung, Huyện Thủy Nguyên, Thành phố Hải Phòng đã tạo điều kiện cho
tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình.
Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố
mẹ và đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả
hoàn thành tốt luận văn này.


5

Danh sách kí hiệu
 
b


∏ bi
i=1

ký hiệu tổng a1 + a2 + · · · + am
ký hiệu tích b1 b2 · · · bm


6

Mở đầu
Có thể nói, Lý thuyết số là một ngành khoa học sớm nhất của nhân loại.
Trước những năm 70 của thế kỷ XX, Lý thuyết số được coi là một ngành
thuần túy lý thuyết, và thậm chí người ta còn ca ngợi vẻ đẹp của nó vì nó
xa rời thực tiễn!
Tuy nhiên, như Issac Newton từng nói : “Không có gì gần với thực tiễn
hơn là một lý thuyết đẹp”, Lý thuyết số lại trở thành một ngành gần thực
tiễn nhất, ứng dụng nhất, vì những ảnh hưởng lớn lao và bất ngờ của nó đến
nhiều ngành, chẳng hạn như Lý thuyết mật mã. Trong lĩnh vực Lý thuyết
mật mã, mật mã hóa khóa công khai là một dạng mật mã cho phép người
sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa
chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp
khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay
khóa bí mật). Các kiến thức toán học được sử dụng ở đây là các mối quan
hệ, các tính chất của số nguyên tố (prime), số giả nguyên tố (pseudoprime)
và nhiều khía cạnh khác của Lý thuyết số.
Trong Lý thuyết số, số giả nguyên tố là một hợp số nguyên dương thỏa
mãn nhiều quan hệ như các số nguyên tố. Nếu ta tìm được một quan hệ nào
đó (ví dụ như đồng dư thức trong định lý Fermat bé) sao cho số các hợp số
thoả mãn quan hệ đó là "rất ít" so với các số nguyên tố, thì những số giả


8

Chương 1

Số giả nguyên tố trong
lý thuyết mật mã khóa công khai
1.1

Cơ sở toán học của lý thuyết mật mã khoá công khai

Trong mục này, chúng ta sẽ thảo luận về việc áp dụng phân tích nhân tử và
kiểm tra tính nguyên tố trong mật mã.
Trong mật mã chúng ta tìm cách truyền một tin nhắn bí mật m, chẳng
hạn từ Alice cho Bob theo cách mà Oscar là người chặn tín hiệu không thể
đọc được tin. Ý tưởng là phải đưa ra một khoá mã hoá Φ, là một hàm toán
học biến m thành r := Φ(m) để gửi. Số r là những ký tự mà dường như vô
nghĩa để cho Oscar không thể thông dịch và Bob có thể giải mã bằng cách
tính Ψ(r), trong đó Ψ = Φ−1 . Cho tới gần đây (trước 1977), hiểu biết về
khoá mã hoá Φ có thể cho phép Oscar xác định khoá giải mã Ψ, và do đó
việc giữ bí mật khoá mã hoá Φ là một việc vô cùng quan trọng và thường
là một nhiệm vụ khó khăn.
Nếu Oscar được cho một khoá mã hoá thì anh ta dễ dàng xác định khoá
giải mã bằng cách đảo ngược những gì đã làm để mã hoá. Tuy nhiên, năm
1976, Diffie và Hellman , bằng cách đưa ra hệ mã mũ, dường như đã tạo
ra khoá công khai Φ, theo đó Oscar có thể nhìn thấy nhưng không thể xác


9
định Ψ = Φ−1 . Nếu việc này khả thi, Alice có thể quên đi khó khăn của

nhiều hơn 200 chữ số. Ta sẽ thấy rằng, việc tìm số nguyên tố (xác suất) lớn
như vậy rất dễ dàng bằng cách sử dụng các số giả nguyên tố, vấn đề sẽ thảo
luận trong luận văn.

1.1.2

Vấn đề lấy căn bậc hai modulo n

Từ Định lý Euler ta biết rằng, nếu ta có thể tìm được căn bậc hai b của 1
mod n mà khác ±1, thì điều này chứng tỏ rằng n là hợp số. Thực vậy, từ b
suy ra phép phân tích nhân tử của số lẻ n với:
gcd(b − 1, n) gcd(b + 1, n) = gcd(b2 − 1, n) = n

(1.1)

(do b2 ≡ 1 (mod n)) trong đó gcd(b − 1, n) và gcd(b + 1, n) nhỏ hơn n (vì
b ≡ 1 hay −1 (mod n)), kéo theo 1 < gcd(b − 1, n), gcd(b + 1, n) < n và
do đó (1.1) là phép phân tích nhân tử không tầm thường của n.
Một cách tổng quát hơn ta giả sử rằng cho trước hợp số lẻ n với ít nhất
hai nhân tử nguyên tố phân biệt, Oscar có một hàm fn sao cho nếu a là
một bình phương (mod n), thì fn (a)2 ≡ a (mod n). Sử dụng fn , Oscar
có thể dễ dàng phân tích nhân tử n (với thời gian đa thức ngẫu nhiên), vì
nếu ông lấy các số nguyên b trong khoảng [1, n − 1] một cách ngẫu nhiên
thì gcd( fn (b2 ) − b, n) là một nhân tử không tầm thường của n với điều
kiện b ≡ fn (b2 ) hay − fn (b2 ) (mod n); vì có ít nhất bốn căn bậc hai của
b2 (mod n), xác suất đây là một phép phân tích nhân tử của n là lớn hơn
hoặc bằng 1/2.
Sử dụng ý tưởng này, Rabin xây dựng một hệ thống mật mã khoá công
khai mà về bản chất việc phá khoá khó như tìm phân tích nhân tử của n.


số đối với các máy tính thông thường.


12
Nhắc lại, một số nguyên dương p > 1 được gọi là một số nguyên tố nếu
p không chia hết cho số nguyên dương nào ngoài 1 và p. Ngược lại, số p
được gọi là hợp số.
Ta ký hiệu π(n) là số các số nguyên tố nhỏ hơn hoặc bằng n, và gọi nó
là hàm phân phối của các số nguyên tố.
Ví dụ 1.2.1. π(10) = 4 vì có bốn số nguyên tố nhỏ hơn 10 là 2, 3, 5, 7.
Ta có định lý sau đây về ước lượng xấp xỉ hàm số học π(·):
Định lí 1.2.2. Ta có
π(n)
= 1.
n→∞ n/ ln n
lim

Nói cách khác, giá trị π(n) xấp xỉ bằng n/ ln n khi n vô cùng lớn.
Ví dụ 1.2.3. Với n = 109 , ta có
π(n) = 50847534

và

n/ ln n = 48254942.

Sai số ở đây là 6%.
Vậy ta lấy ngẫu nhiên một số nguyên dương k bit, xác suất để số này
là số nguyên tố bằng 1/ ln 2k . Vậy về trung bình, ta cần ln 2k lần thử để lấy
được một số nguyên tố k bit.
Ví dụ 1.2.4. Nếu k = 3072 thì trung bình lấy ngẫu nhiên ln 23072 ≈ 2130


Bây giờ ta sẽ trình bày khái niệm về các số giả nguyên tố. Theo định lý
Fermat, nếu n là số nguyên tố và b là số nguyên tuỳ ý, thì bn ≡ b (mod n).
Do đó nếu tồn tại số b sao cho bn ≡ b (mod n) thì n phải là hợp số. Trong
nhiều ứng dụng, chúng ta lại cần đến các thuật toán để chỉ ra một số n là số
nguyên tố. Trong trường hợp này, ta không thể dùng Định lý Fermat nhỏ,
vì định lý ngược của nó không đúng. Tuy nhiên, nếu một số nguyên thoả
mãn các giả thiết của Định lý Fermat nhỏ thì “có nhiều khả năng” nó là
một số nguyên tố ! Ta có định nghĩa sau đây.
Định nghĩa 2.1.1. Giả sử b là một số nguyên dương. Nếu n là hợp số
nguyên dương và bn ≡ b (mod n) thì n được gọi là số giả nguyên tố cơ sở
b.
Trong trường hợp (n, b) = 1, ta thường dùng định nghĩa tương đương,
là
bn−1 ≡ 1 (mod n).
Trường hợp này, n được gọi là một số giả nguyên tố Fermat.


15
Ví dụ 2.1.2. Số nguyên 561 = 3 · 11 · 17 là số giả nguyên tố cơ sở 2. Thật
vậy, áp dụng Định lý Fermat nhỏ, ta có
2560 = (22 )280 ≡ 1 (mod 3),
2560 = (210 )56 ≡ 1 (mod 11),
2560 = (216 )35 ≡ 1 (mod 17).
Từ đó suy ra 2560 ≡ 1 (mod 561).
Nói chung các số giả nguyên tố ít hơn nhiều so với các số nguyên tố.
Chẳng hạn, có tất cả 455052512 số nguyên tố bé hơn 1010 nhưng chỉ có
14884 số giả nguyên tố cơ sở trong khoảng đó. Sự kiện này giải thích cách
nói ở trên: Các số thoả mãn Định lý Fermat nhỏ có nhiều khả năng là số
nguyên tố. Tuy nhiên đối với mọi cơ sở tuỳ ý, số các số giả nguyên tố là vô

lý Fermat nhỏ, ta có
b2 ≡ 1 (mod 3),

b10 ≡ 1 (mod 11),

b16 ≡ 1 (mod 17).

Do đó, viết 560 = 2 · 280 = 10 · 56 = 16 · 35 ta được
b560 = b2
b560 = b10
b560 = b16

280
56
35

≡ 1 (mod 3),
≡ 1 (mod 11),
≡ 1 (mod 17).

Từ đó suy ra b560 ≡ 1 (mod 561).
Giả thuyết sau đây đã được chứng minh trong W. R. Alford, A. Granville
& C. Pomerance [4] : tồn tại vô hạn số Carmichael.
Chính xác hơn, như trong [4, Abstract], các tác giả nói rằng sẽ chứng
minh có khoảng x2/7 số Carmichael nhỏ hơn x, với x đủ lớn.
Ta điểm qua một số cột mốc chính trong lịch sử phát triển của các
nghiên cứu về số giả nguyên tố Fermat và số Carmicheal.
Vào ngày 18/10/1640, Fermat viết trong một bức thư gửi đến Frenicle,
rằng p chia hết a p − a với mọi số nguyên a, với p là một số nguyên tố.
Câu hỏi tự nhiên nảy sinh là : Liệu các số nguyên tố có là tất cả những số

Giá trị chính xác của α phụ thuộc vào hai hằng số khác xuất hiện trong Lý
thuyết số giải tích. Bây giờ chúng ta mô tả những hằng số này.
Giả sử π(x) là số các số nguyên tố p ≤ x, và giả sử π(x, y) là số các số
trong số đó mà p − 1 không có các nhân tử nguyên tố vượt quá y. Giả sử E
là ký hiệu tất cả các số E trong miền 0 < E < 1 mà tồn tại x1 (E), γ1 (E) > 0
sao cho
π(x, x1−E ) ≥ γ1 (E)π(x)

(2.1)

với mọi x ≥ x1 (E). Năm 1935, Paul Erd¨os chỉ ra sự tồn tại một số nguyên
dương nhỏ trong E . Các giá trị lớn hơn sau đó được tìm thấy bởi Wooldridge,
Goldfeld, Pomerance, Fouvry và Grupp, Balog và Friedlander. Kết quả tốt
√
nhất được biết đến (xem [4]) là bất kỳ số dương nào nhỏ hơn 1 − (2 e)−1
đều thuộc E .
Erd¨os có giả thuyết nói rằng mỗi số dươngnhỏ hơn 1 đều thuộc E , nghĩa
là E là khoảng mở (0, 1).
Ta nhận xét rằng nếu E ∈ E , thì (0, E] ∈ E . Thêm nữa, có thể chứng
minh rằng (sử dụng Bất đẳng thức Brun-Titchmarsh) rằng nếu E ∈ E thì
E ∈ E với E > E nào đó. Do vậy, E là một khoảng mở.
Định nghĩa π(x; d, a) là số các số nguyên tố nhỏ hơn hay bằng x thuộc
cấp số cộng a modulo d. Định lý số nguyên tố đối với cấp số cộng phát
biểu rằng
π(x; d, a) ∼

π(x)
ϕ(d)

với x → ∞,

π(y)
2ϕ(d)

(2.3)

mỗi khi d không chia hết cho bất kỳ phần tử nào của DB (x), là một tập
hợp có không quá DB số nguyên, mỗi số vượt quá log x.
Trong [4], các tác giả cũng chứng minh rằng (0, 5/12) ∈ B và chứng
minh một định lý khá mạnh đối với các số trong khoảng này.
Định lý về số Carmichael phụ thuộc nhiều vào tập E và B.
Định lí 2.1.6. Với mỗi E ∈ E và B ∈ B tồn tại một số x0 = x0 (E, B) sao


20
cho C(x) ≥ xEB với mọi x ≥ x0 .
√
Do 0, 1 − (2 e)−1 ⊂ E và (0, 5/12) ⊂ B, ta kết luận rằng C(x) ≥
xβ −ε với mỗi ε > 0 và mọi x lớn phụ thuộc việc chọn ε, trong đó
√
5
β = (1 − (2 e)−1 ) = 0.290306 . . .
12
Lập luận của bài báo dựa vào lập luận độc đáo của Erd¨os với những
sửa đổi nhất định. Ý tưởng là xây dựng một số nguyên L mà với nó tồn tại
rất nhiều số nguyên tố p sao cho p − 1 chia hết L. Giả sử rằng tích của một
số trong những số nguyên tố đó C = p1 . . . pk là đồng dư với 1 mod L. Khi
đó C là một số Carmichael, do mỗi p j − 1 chia hết L, mà L chia hết C − 1,
và ta có thể áp dụng tiêu chuẩn Korselt như trên. Thật ra, càng có nhiều
tích như vậy chúng ta có thể tìm thấy càng nhiều số Carmichael. Ta cần có
tập các số nguyên tố p như vậy lớn đến mức nào để đảm bảo sự tồn tại của

Prachar là lấy một số L mà là tích của tất cả các số nguyên tố lớn đến một
điểm nào đó và chứng minh rằng có một số nguyên k với k < Lc và với
m = kL có nhiều ước có dạng p − 1. Với mục đích này, ta cần λ (kL) là nhỏ
so với kL. Nhưng việc đưa vào nhân tử k bí ẩn đó có thể làm hỏng mọi việc,
bởi vì không có nguyên nhân nào cho thấy λ (kL) không thể lớn tuỳ ý, ngay
cả khi ta xuất phát từ một L mà với nó λ (L) là rất nhỏ so với L.
Trong bài báo [4] các tác giả đã sửa đổi phương pháp của Prachar, để
khi cho L, ta có thể tìm một số nguyên k nguyên tố cùng nhau với L sao
cho có nhiều số nguyên tố p ≡ 1 mod k mà p − 1 chia hết kL.
Trong [4, Section 6] các tác giả cũng trình bày chứng minh cho Định lý
sau:
Định lí 2.1.8. Với mỗi B ∈ B, (0, B) ⊂ E .
Định lí 2.1.9. Cho ε > 0. Giả sử tồn tại một số xε sao cho
π(x; d, 1) ≥

π(x)
2ϕ(d)

với mọi số nguyên dương d ≤ x1−ε , x ≥ xε . Khi đó tồn tại một số xε sao


22
cho C(x) ≥ x1−2ε với mọi x ≥ xε . Đặc biệt, nếu một số xε như vậy tồn tại
với mỗi ε > 0, thì C(x) = x1−o(1) khi x → ∞.
Chứng minh của Định lí 2.1.6 là hiệu quả theo ý nghĩa nếu các giá trị
bằng số được cho với γ1 (E), x1 (E), và x2 (B), thì giá trị bằng số đối x0 (E, B)
có thể tính được. Tuy nhiên, giá trị lớn của E mà ngày nay chúng ta biết
là thuộc E đã được chứng minh thuộc E thông qua định lý không hiệu
quả Bombieri-Vinogradov. Rất có thể, Định lý Friedlander nói rằng mọi số
√



23
Vì n là số nguyên tố nên x0 ≡ 1 (mod n). Do đó x12 ≡ 1 (mod n), tức
là x1 ≡ 1 (mod n) hoặc x1 ≡ −1 (mod n). Tiếp tục quá trình như vậy
ta sẽ đi đến kết luận rằng, hoặc xk ≡ 1 (mod n) với k = 0, 1 · · · s, hoặc
xk ≡ −1 (mod n) với một số nguyên k nào đó. Như vậy n trải qua được
kiểm tra Miller cơ sở b.
Dễ thấy rằng, nếu n trải qua được kiểm tra Miller cơ sở b thì n sẽ là số
giả nguyên tố cơ sở b. Ta có định nghĩa sau.
Định nghĩa 2.2.2. Số nguyên n được gọi là số giả nguyên tố mạnh cơ sở b
nếu nó là hợp số và trải qua được kiểm tra Miller cơ sở b.
Như vậy các số giả nguyên tố mạnh lại còn ít hơn các số giả nguyên tố.
Tuy nhiên, ta có định lý sau.
Định lí 2.2.3. Tồn tại vô số số giả nguyên tố mạnh cơ sở 2.
Chứng minh. Thật vậy, giả sử n là một số giả nguyên tố cơ sở 2. Khi đó,
với số nguyên lẻ k nào đó, ta có 2n−1 − 1 = nk. Đặt N = 2n − 1, khi đó nó
có ước là 2d − 1, với d là ước số nào đó của n. Mặt khác,
N − 1 = 2n − 2 = 2(2n−1 − 1) = 2nk,

2

N−1
2

= 2nk = (2n )k ≡ 1 (mod N).

Vậy với mỗi số giả nguyên tố n, ta xây dựng được số giả nguyên tố mạnh
N với các số n khác nhau cho ta các số N khác nhau. Như vậy định lý được
chứng minh, bởi vì có vô số giả nguyên tố cơ sở 2.

1
.
4k

Khi k đủ lớn, ví dụ k = 20,

xác suất đó quá nhỏ, nên với n trải qua với 20 cơ sở ngẫu nhiên thì có thể
tin “hầu chắc chắn” rằng n là số nguyên tố. Từ đó ta có thuật toán xác suất
sau đây.
Thuật toán (Rabin-Miller 1980). Cho N ≥ 3 lẻ, thuật toán sau đây xác
định rằng N là một hợp số, hoặc in ra thông báo N là số nguyên tố với xác
suất lớn hơn 1 − 4120 .
RM1 (Xuất phát). Đặt q ← N −1,t ← 0, và nếu q chẵn đặt q ← q/2, t ← t +1
(bây giờ ta có N − 1 = 2t q, với q lẻ). Sau đó đặt c ← 20


25
RM2 (Chọn a mới). Chọn ngẫu nhiên số a trong khoảng 1 < a < N. Đặt
e ← 0, b← aq (mod N). Nếu b =1, chuyển sang RM4.
RM3 (Bình phương). Nếu b ≡ ±1 (mod n) và e < t −2, ta đặt b ← b2 (mod N),
e ← e + 1. Nếu b = N − 1, in ra thông báo “n là hợp số” và kết thúc
thuật toán.
RM4 Đặt c ← c − 1. Nếu c > 0, chuyển sang RM2. Nếu c = 0, in ra thông
báo “N là số nguyên tố”.

2.3

Số giả nguyên tố Euler

Giả sử p là số nguyên tố lẻ và b là số nguyên dương không chia hết cho p.