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

NGUYỄN THỊ BÌNH

MỘT SỐ THUẬT TOÁN
PHÂN TÍCH SỐ NGUYÊN HIỆN ĐẠI
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Ị BÌNH

MỘT SỐ THUẬT TOÁN
PHÂN TÍCH SỐ NGUYÊN HIỆN ĐẠI
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

12

1.3

Phân tích Pollard p − 1 . . . . . . . . . . . . . . . . . . . . . . .

17

Chương 2. Một số thuật toán hiện đại phân tích số nguyên

20

2.1

Sự kiểm tra ước . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.2

Thuật toán phân tích ρ của Pollard . . . . . . . . . . . . . . . . .

21

2.3

Phương pháp phân tích Brent . . . . . . . . . . . . . . . . . . . .

24


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 đã dành nhiều
công sức hướng dẫn để tác giả hoàn thành 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 B, cao
học Toán khóa 9 (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 Nguyễn
Đức Cảnh, Huyện Kiến Thụy, 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

Z

vành các số nguyên

Q


gcd(a, b)

ước chung lớn nhất của a và b

a|b

a là ước của b

N

sàn của số N

F[α]

trường mở rộng của trường F


6

Mở đầu
Trước những năm 70 của thế kỷ XX, Số học thường được xem là một
trong những ngành toán học thuần tuý, chỉ có ý nghĩa lý thuyết. Đối tượng
nghiên cứu của Số học là các quy luật trong tập hợp số nguyên; các giả
thuyết lớn tồn tại trong Số học thường là các giả thuyết về số nguyên tố.
Thậm chí, có những nhà toán học cho rằng, vẻ đẹp của số học có được nhờ
sự xa rời thực tiễn của nó.
Ngày nay, những ứng dụng lớn lao và bất ngờ của Số học vào mật mã
cho ta thấy rằng quan niệm trên đã hoàn toàn thay đổi. Vẻ đẹp của Số học
không chỉ thể hiện trong ý nghĩa “thuần tuý” của nó, mà cả trong những

Tác giả

Nguyễn Thị Bình


8

Chương 1

Thám mã và một số thuật toán cổ điển
phân tích số nguyên

1.1

Thám mã và phân tích số nguyên

Phần này em sẽ trình bày về thám mã. Thám mã là một vấn đề phức tạp
nên trong luận văn này em xin phép chỉ đề cập những vấn đề đơn giản nhất.
Phần đầu trong trình bày chúng tôi dựa vào [2].
Thám mã (hay phân tích mã - cryptanalysis) là việc nghiên cứu các
phương pháp “phá vỡ” bức màn ngụy trang văn bản (do việc mã hóa tạo
nên) để có thể hiểu được nội dung văn bản.
Hiện nay, trên quan điểm thám mã, người ta phân các hệ mã thành ba
loại:

• Loại đã bị phá;
• Loại chưa được nghiên cứu phân tích (vì còn mới, hoặc vì chưa được
dùng rộng rãi);




Bây giờ ta sẽ liệt kê các phương pháp thám mã

1. Thám mã tích cực là việc thám mã sau đó tìm cách làm sai lạc các dữ
liệu truyền, nhận hoặc các dữ liệu lưu trữ phục vụ mục đích của người
thám mã.
2. Thám mã thụ động là việc thám mã để có được thông tin về bản tin rõ
phục vụ mục đích của người thám mã.
3. Thám mã affine. Trong mật mã affine, đầu tiên bảng chữ cái của thông
điệp cần mã hóa có kích thước m sẽ được chuyển thành các con số
tự nhiên từ 0, . . . , m − 1. Sau đó dùng một hàm modulo để mã hóa và
chuyển thành bản mã. Hàm mã hóa cho một ký tự như sau:
e(x) = (ax + b) (mod m)
với m là kích thước của bảng chữ cái, a và b là khóa mã. Giá trị a được
chọn sao cho a và m là nguyên tố cùng nhau.
Giả sử Trudy đã lấy được bản mã sau đây:


11
FMXVEDKAPHFERBNDKRXRSREFMORUD
SDKDVSHVUFEDKAPRKDLYEVLRHHRH
Trudy thống kê tần suất xuất hiện của 26 chữ cái như trong bảng sau:
A 2 N 1
B 1 O 1
C 0

P

3



0

Các chữ cái trong bản mã xuất hiện tổng là 57 lần, nhưng phương pháp
này tỏ ra hiệu quả để thám mã affine. Ta thấy tần suất xuất hiện các
chữ cái theo thứ tự là: R là 8, D là 6, E, H, K là 5 và F, S, V là 4. Vì
vậy dự đoán đầu tiên của ta có thể là R là mã của e, D là mã của t.
Theo đó, eK (4) = 17 và eK (19) = 3. Mà ta có eK (x) = ax + b. Để tìm


12
K = (a, b) ta giải hệ phương trình:



4a + b ≡ 17 (mod 26)


19a + b ≡ 3 (mod 26) .
Giải hệ phương trình này ta được a = 6, b = 19. Đây không phải là
khóa vì gcd(a, 26) = 2 > 1. Ta lại tiếp tục phỏng đoán rằng R là mã
của e, E là mã của t. Ta nhận được a = 13, chưa thỏa mãn. Tiếp tục với
H, ta có a = 8. Cuối cùng, với K ta tìm được K = (3, 5). Sử dụng khóa
mã này ta có được bản tin rõ là
algorithmsrequiregeneraldefinitionsofarithmeticprocesses
(algorithms require general definitions of arithmetic processes)

1.2

Phân tích Fermat

Ta hãy xem xét một lý do dẫn đến việc làm này.
Định lý cơ bản của số học kéo theo nhận xét rằng mọi số nguyên đều
có thể được phân tích thành tích .


14
Xét số
N = 25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357.
Số nguyên này được biết như là RSA-2048. Vào tháng 3/1991, Phòng thí
nghiệm RSA (RSA Laboratories) đã thông báo giải thưởng USD 200.000
cho sự phân tích thành công số nguyên này. Tính đến tháng 11/2004, số
này vẫn chưa được phân tích.
Nếu biết trước hai số nguyên tố lớn thì ta sẽ có một thuật toán nhanh
để nhân chúng với nhau. Tuy nhiên, trong tình huống ngược lại, nếu cho
tích của hai số nguyên tố, rất khó phân tích ngược lại để tìm ra hai số như
vậy. Thuật toán nhanh nhất được biết đến hiện nay có tên gọi Sàng trường



Cũng vậy, x = (s + t)/2 ≤ 2t/2 ≤ N.
Đối với thuật toán này, ta chọn x1 =

√
N, và xi+1 = xi + 1. Với mỗi i, ta


16
kiểm tra khi nào thì yi =

xi2 − N là một số nguyên và khi nào thì (xi + yi ),

(xi − yi ) là các nhân tử không tầm thường N. Nếu cả hai điều kiện đó xảy
ra, ta có được một phân tích không tầm thường. Nếu không, ta tiếp tục với
i tiếp theo.
Dưới đây là thuật toán.

function fermatFactor(N)
for x from ceil(sqrt(N)) to N
ySquared := x * x - N
if isSquare(ySquared) then
y := sqrt(ySquared)
s := (x - y)
t := (x + y)
if s 1 and s N then
return s, t
end if
end if
end for
end function

/ {1, N} thì rk là
một nhân tử không tầm thường và ta hoàn thành công việc cần làm.


18
• Ta có thể viết 2k! ≡ (2(k−1)! )k (mod n), sao cho nếu 2(k−1)! là đã biết
theo (mod n), thì 2k! có thể tính được chỉ với một phép toán lũy thừa
modulo một số.

Ta trình bày thuật toán.

function pollard_p1(N)
# Initial value 2^(k!) for k = 0.
two_k_fact := 1
for k from 1 to infinity
# Calculate 2^(k!) (mod N) from 2^((k-1)!).
two_k_fact := modPow(two_k_fact, k, N)
rk := gcd(two_k_fact - 1, N)
if rk 1 and rk N then
return rk, N/rk
end if
end for
end function

Trong đó modPow(a, b, m) lại là số nguyên nhỏ nhất không âm sao cho
ab ≡ y (mod m). Hàm này được gọi là “số mũ modular”.
Ta trình bày thuật toán hiệu quả đối với số mũ modular. Ta viết b trong
hệ nhị phân dưới dạng
b = b0 20 + b1 21 + . . . + bn−1 2n−1


n−1

bn−1

.

k

là 1 nếu bk = 0 và a2 nếu ngược lại. Do đó ta có
n−1

b

a =

∏

k

a2 .

k=0, bk =0

Chú ý rằng a2

k+1

k

= a2·2 = a2

Trong Chương 2 này, chúng tôi sẽ thảo luận về một số thuật toán hiện
đại phân tích số nguyên.

2.1

Sự kiểm tra ước

Sự kiểm tra ước là thuật toán đơn giản nhất để phân tích số nguyên. Giả
sử rằng s và t là các nhân tử không tầm thường của N sao cho st = N và
s ≤ t. Để thực hiện thuật toán kiểm tra ước, một cách đơn giản là kiểm tra
√
xem s | N với s = 2, . . . , N . Khi một nhân tử như vậy s được tìm thấy
thì t = N/s cũng là một nhân tử, và một phép phân tích đã được tìm thấy
cho N. Ràng buộc trên s ≤ N được cung cấp bởi định lí sau đây:
Định lí 2.1.1. Nếu N có nhân tử không tầm thường s, t với st = N và s ≤ t,
√
thì s ≤ N.
Chứng minh. Do s là nhân tử của N nên ta có s > N. Khi đó t ≥ s >

√
N,


21
và st > N, mà điều này lại mâu thuẫn với giả thiết rằng st = N. Do đó
s ≤ N.
Thuật toán như sau
function trialDivision(N)
for s from 2 to floor(sqrt(N))
if s divides N then

bài toán phân tích số nguyên.
Giả sử rằng s và t là các nhân tử không tầm thường của N thỏa mãn
st = N và s ≤ t. Bây giờ giả sử rằng ta đã tìm được các số nguyên không
âm i và j với i < j sao cho xi ≡ x j (mod s) nhưng xi ≡ x j (mod n). Do
s | (xi − x j ) và s | N, ta có s | gcd(xi − x j , N). Bởi giả thiết s ≥ 2, ta có
gcd(xi −x j, N) ≥ 2. Bởi định nghĩa, ta có gcd(xi −x j , N) | N. Ngoài ra, ta có
N | (xi − x j ) và do đó N | gcd(xi − x j , N). Chúng ta cũng có N | gcd(xi −
x j , N), gcd(xi − x j , N) > 1 và gcd(xi − x j , N) | N. Như vậy, gcd(xi − x j , N)
là một nhân tử không tầm thường của N.
Bây giờ ta phải tìm i, j sao cho xi ≡ x j (mod s) và xi ≡ x j (mod n).
Nhận thấy rằng các dãy xn (mod s) là tuần hoàn với độ dài của chu trình
tỷ lệ với s. Pollard đã đề xuất là xn được so sánh với x2n , với n = 1, 2, 3, . . ..
Với mỗi n, ta kiểm tra xem d(xn − x2n , N) có là một nhân tử không tầm
thường của N hay không, ta lặp lại quá trình cho đến khi một nhân tử được
tìm thấy. Nếu không có nhân tử được tìm thấy, thuật toán sẽ không chấm


23
dứt.
Thuật toán là

function pollardRho(N)
# Initial values x(i) and x(2*i) for i = 0.
xi := 2
x2i := 2
do
# Find x(i+1) and x(2*(i+1))
xiPrime := xi ^ 2 + 1
x2iPrime := (x2i ^ 2 + 1) ^ 2 + 1
# Increment i: change our running values

Thuật toán là

function brentFactor(N)
# Initial values x(i) and x(m) for i = 0.
xi := 2
xm := 2
for i from 1 to infinity
# Find x(i) from x(i-1).
xi := (xi ^ 2 + 1) % N
s := gcd(xi - xm, N)
if s 1 and s N then


25
return s, N/s
end if
if integralPowerOf2(i) then
xm := xi
end if
end do
end function

trong đó hàm integralPowerOf2(z) đúng nếu z là một lũy thừa nguyên
của 2 và sai nếu ngược lại. Việc triển khai hiệu quả cho hàm này có thể
được thực hiện bằng cách kiểm tra các lũy thừa kế tiếp của 2 cho đến khi
lũy thừa của 2 bằng hoặc vượt quá z

function integralPowerOf2(z)
pow2 := 1
while pow2