Phát triển thuật toán của Danied Shank để giải bài toán logarit rời rạc trên vành Zn

i gian và không gian của bộ nhớ là O( ). 
Để minh hoạ cho thuật toán Baby-step Giant-step của Danied Shanks giải bài 
toán logarit rời rạc trên trường Zp, xét một ví dụ sau: Giả sử G= Z19
*=. Giả sử 
cần giải bài toán logarit rời rạc k= log26. Theo thuật toán 3.1, việc tìm k được thực 
hiện như sau: 
Bước 1: q= = 5. 
Bước 2: Với mỗi i, 0 ≤ i < 5 tính (i,6.2i mod 19 ), ta có S={(0, 6), (1, 12) (2, 5), 
(3, 10), (4,1)}, sau khi sắp xếp cho dãy S ={(4,1), (5,2), (2, 5), (0, 6), (3,10), (1, 12)}. 
Bước 3: Với mỗi j, 0 ≤ j 5 tính (5.j,25j mod 19 ), ta có T= {(0,1), (5,13), 
(10,17), (15,12), (20,4)}, sau khi sắp xếp cho dãy T ={(0,1), (20,4), (15,12), (5,13), 
(10,17)} 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 133
Bước 4: So sánh giữa S và T cho thấy giá trị 12 là giá trị chung cho hai dãy S và 
T, khi đó k= q.j-i=15-1=14. 
3.2. Thuật toán Polig-Hellman[5][6] 
Trong trường hợp chỉ có các thừa số nguyên tố bé, bài toán logarit rời rạc 
sẽ giải được bởi thuật toán của Polig-Hellman. Thuật toán mô tả như sau: 
Thuật toán 3.2: 
Input: Nhóm cyclic G= = Zp
* có bậc p-1, b G. 
Output: k= mod p-1 
Bước 1. Phân tích ra thừa số nguyên tố của p-1 
(Ri là các số nguyên tố khác nhau). 
Bước 2. Đặt gi= và bi= ni= và tính ki là logarit rời rạc cơ số i = của bi 
Bước 3. Áp dụng công thức 2.4 và công thức 2.5, tính k từ các phương trình sau: 
k= mod R1
c1 
k= mod R2
c2 
.... 
k= mod Rh
ch 
Áp dụng định lý 2.2 xác định được k= mod p-1. 
Bước 4. Đưa ra giá trị của x; 
Để minh hoạ thuật toán Pohlig-Hellman, xét ví dụ sau: Giả sử p=31. Ta có 31-
1=30= 5.3.2. Giả sử cần tìm x, x=y mod 31, với =3, y=26, ta có phương trình ẩn 
x, 3x=26 mod 31. Áp dụng thuật toán 3.2 ta có: 
n1 = = 6; 1= = mod 31=16; y1= =26
6 mod 31= 1 
n2 = = 10; 2= = mod 31= 25; y2= =26
10 mod 31= 5 
n3 = = 15; 3= = mod 31=30; y3= =26
15 mod 31= 30 
Tính x là logarit rời rạc của y, ký hiệu là x= ta tính logarit rời rạc x từ hệ 
phương trình sau: 
x= = mod 5 (*) 
x= = mod 3(**) 
x= = mod 2(***) 
Từ (*)(**)(***) ta có hệ phương trình: 
Do các số 5, 3, 2 là nguyên tố cùng nhau, áp dụng định lý Trung quốc về đồng 
dư, tìm ra x = 5 mod 5.3.2. Tương đương với phương trình x = 5 mod 30 là giá trị 
cần tìm. Kiểm tra lại dễ thấy 35 = 26 mod 31. 
4. PHÁT TRIỂN THUẬT TOÁN DANIED SHANKS GIẢI BÀI TOÁN 
LOGARIT RỜI RẠC TRÊN VÀNH Zn[7] 
Thuật toán 3.1 và thuật toán 3.2 áp dụng giải bài toán logarit rời rạc trên trường 
Zp, trong đó, thuật toán 3.2 phụ thuộc hoàn toàn vào bậc của nhóm cyclic G= 
Zp
* (p nguyên tố), chính vì thế, không thể áp dụng để giải bài toán logarit rời rạc 
trên vành Zn. Thuật toán 3.1 có thể phát triển để giải bài toán logarit rời rạc trong 
một đoạn nào đó trên vành Zn, mà không cần dựa trực tiếp vào bậc của nhóm nhân 
cyclic G= Zn
*. Giả sử nhóm cyclic G= là nhóm con của nhóm nhân 
Công nghệ thông tin & Cơ sở toán học cho tin học 
L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 134 
và cỡ bậc của G là m bit, khi đó thuộc đoạn [2m-1,2
m-1] và giá trị logarit rời 
rạc loggb sẽ thuộc đoạn [0,2
m-1]. Trong phần này, chúng tôi phát triển thuật toán 
Baby-step Giant-step của Danied Shanks để tìm logarit rời rạc trong nửa đoạn 
[0,2m-1) trên vành Zn. 
4.1. Thuật toán 
Input: Vành Zn và nhóm cyclic G= Zn
*, bậc của g, ký hiệu là là 
một số m bit (m=bitlength( )), b G 
Output: k= loggb. 
Bước 1: q ← // q nhận giá trị là cận trên của 
Bước 2: Với mỗi i, 0 ≤ i < q tính (i,b.gi mod n ), lưu trữ trong danh sách S và 
sắp xếp (Baby step) 
Bước 3: Với mỗi j,0 ≤ j < q tính (q.j, gq.j mod n ), lưu trữ trong danh sách T và 
sắp xếp (Giant step) 
Bước 4: Duyệt danh sách S và danh sách T, và kiểm tra hai điều kiện: 
- Giá trị b.gi trong S bằng với giá trị gq.j trong T và qj-i<2m-1, thì giá trị logarit 
rời rạc cần tìm, k= qj-i. 
- Nếu không thoả mãn một trong hai điều kiện trên thì giá trị logarit rời rạc 
không nằm trong khoảng tìm kiếm của thuật toán. 
4.2. Tính đúng đắn của thuật toán 
Do cấp của nhóm G= là m bít, nên logarit rời rạc cơ số g của b là nghiệm k từ 
phương trình gk = b mod n sẽ thuộc khoảng [0,2m-1]. Danh sách tạo ra trong bước 
nhỏ (Baby step) chứa đựng các cặp (i,bgi), 0 ≤ i < q), danh sách tạo ra trong bước lớn 
chứa đựng các cặp (jq, gqj), 1≤ j ≤ q). Quá trình tạo ra danh sách bước lớn mà phát 
hiện giá trị gqj bằng gi trong danh sách được tạo ra ở bước nhỏ, tức là ta có phương 
trình bgi= gqj mod n. Do g Zn
*, nên (g, n)=1, khi đó, tồn tại g-1 và từ kết quả gqj= 
bgi mod n ta có g-igjq=b mod n hay có g-i+jq=b mod n. Nếu giá trị jq- i< 2m-1, theo 
định lý 2.1 thì k là giá trị duy nhất thuộc khoảng [0, 2m-1) thoả mãn g-i+jq=b mod n 
nên giá trị logarit rời rạc cần tìm là k= jq- i. 
Để minh họa cho thuật toán tìm logarit rời rạc trên vành Zn, xét vành Z77 và 
nhóm G= Z77
* và Z77
* có bậc cỡ 5 bít. Giả sử cần giải bài toán logarit rời rạc 
k= log39. Việc tìm k được thực hiện như sau: 
Bước 1: q= = 6. 
Bước 2: Với mỗi i, 0 ≤ i <6 tính (i,9.3i mod 77 ), ta có S={(0, 9), (1, 27) (2, 4) 
(3, 12), (4, 36), (5, 31)}, sau khi sắp xếp cho dãy S ={(2, 4), (0, 9), (3, 12) (1, 27), 
(5, 31), (4, 36)}. 
Bước 3: Với mỗi j, 0≤ j 6 tính (6.j, 36j mod 77 ), ta có T={(0,1), (6,36), 
(12,64), (18,71), (24,15), (30,1)}, sau khi sắp xếp cho sãy T ={(0,1), (30,1), (24, 
15), (6,36), (12,64), (18,71), }. 
Bước 4: So sánh giữa S và T cho thấy giá trị 36 thuộc cả hai dãy S và T, khi đó, 
k= q.j-i=5-3=2 .[0,24). 
4.3. Độ phức tạp của thuật toán 
Nếu không tính đến thừa số của logarit thì thuật toán 4.1 có độ phức tạp tính 
toán về thời gian là O( ) phép tính số học và yêu cầu về không gian của bộ nhớ là 
O( ), so với phương pháp vét cạn có độ phức tạp về thời gian và không gian của 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 135
bộ nhớ đã giảm đi một nửa. Chính vì thế, thuật toán này chỉ áp dụng được với bài 
toán tìm logarit rời rạc trên nhóm G có bậc đủ nhỏ. 
Dựa trên thuật toán, 4.1, chúng tôi đã viết chương trình chạy thủ nghiệm trên 
ngôn ngữ lập trình Visual studio 2008, chạy trên máy tính sony vio core i3. Màn 
hình giao diện chương trình trong hình 4.1. 
Hình 4.1. Giao diện chương trình chạy thử nghiệm. 
Bảng 4.1 đã thống kê kết quả chạy thử nghiệm tìm logarit rời rạc trên một số 
vành Zn. Kết quả chạy thử nghiệm luôn cho kết quả và có độ chính xác tuyệt đối. 
Bảng 4.1. Kết quả thử nghiệm tìm logarit rời rạc trên vành Zn. 
STT Vành Zn Cơ số(g) Giá trị tìm logarit rời rạc (b) Kết quả k 
1 Z1739 2 427 25 
2 Z2173 5 829 185 
3 Z2479 2 2048 11 
4 Z3713 3 3354 10 
5 Z7387 3 6118 13 
6 Z8989 3 6510 23 
7 Z8453 5 3797 4096 
8 Z10807 8 719 57 
9 Z10807 10 4252 97 
10 Z13081 97 8344 2091 
11 Z24047 139 14776 6095 
5. KẾT LUẬN 
Trên cơ sở nghiên cứu hai thuật toán của Poling Hellman và thuật toán của 
Danied Shanks để giải bài toán logarit rời rạc trên trường Zp, tác giả đã phát triển 
thuật toán Baby-step Giant-step của Danied Shanks để tìm logarit trên vành Zn, 
trong điều kiện biết cỡ bậc của nhóm nhân cyclic là m bít. Thuật toán luôn cho kết 
quả chính xác nếu giá trị logarit cần tìm thuộc nửa đoạn [0,2m-1). Để tìm các giá trị 
logarit rời rạc thuộc đoạn [2m-1,2m-1], cần xây dựng một thuật toán riêng. Thuật 
toán được viết trên ngôn ngữ lập trình visual studio 2008 và được áp dụng để tính 
toán logarit rời rạc trên một số vành Zn trong bảng 4.1. Kết quả thử nghiệm cho 
thấy chương trình chạy cho kết quả chính xác, điều đó chứng tỏ thuật toán đảm bảo 
Công nghệ thông tin & Cơ sở toán học cho tin học 
L.V. Tuấn, B.T. Truyền, “Phát triển thuật toán của Danied Shank rời rạc trên vành Zn.” 136 
tính đúng đắn, tính dừng. Kết quả nghiên cứu làm cơ sở để xây dựng hệ tiêu chuẩn 
về tham số cho hệ chữ ký số mới trên vành Zn. 
TÀI LIỆU THAM KHẢO 
[1]. Nguyễn xuân Quỳnh, Nguyễn Hồng Quang, “Báo cáo khoa học về độ mật 
chống lại đối phương tích cực của giao thức thiết lập khóa dựa theo ID”, Hội 
nghị toàn quốc lần thứ V về tự động hóa 24-26/10/2002, Hà nội. 
[2] Daniel Shank, “Class number, a theory of factorization, and genera”, 
Symposium Pure Mathematics, 1972. 
[3] Douglas R. Stinson, “Cyptography theory and practice”, 2003 
[4] OKAMOTO E, (1987), “Key distribution systems based on identification 
information”. Proc. Of Crypto. 
 [5].[Pohlig&Hellman] Stephen C. Pohlig and Martin E. Hellman, “An improved 
algoritm for computing logarithms over GF(p) and its cryptographic 
significance”, IEEE Transaction Theory IT-24 (1979), no. 1, 106-110. 
[6] Song Y. Yan, “Number Theory for Computing”, page 244-267, spring - 2001 
[7] Steven D Galbraith, John M, Pollard, and Ramindern S. Ruprai. “Computing 
discrete logarithms in an interval” 
[8] C Meshram. “Discrete Logarithm and Integer Factorization using IBE”. ISSN: 
2089-3191, Bulletin of Electrical Engineering and Informatics Vol. 4, No. 2, 
June 2015, pp. 160~168 
[9]. FIPS PUB 186-3,“Digital Sinature Standrd (DSS)”, 2009. 
[10]. https://vi.wikipedia.org/wiki/Logarit rời rạc 
[11]. https://vi.wikipedia.org/wiki/đinh lý Trung quốc về đồng dư. 
ABSTRACT 
DEVELOPING SHANK’S ALGORITHM 
FOR SOLVING THE DISCRETE LOGARITHM PROBLEM IN RING Zn 
In this submission, some computing methods for discrete logarithm 
problem of Danied Shanks and Polig-Hellman in finite field Zp have been 
introduced. Based on Danied Shanks's algorithm, we developed it to solve 
the discrete logarithm problem on the Zn ring. The results are able to apply 
on problem for analysing security of digital signature schemes, which are on 
basis of discrete logarithm problem in ring Zn. 
Keywords: Finite ring, Finite field, Discrete Logarithm Problem. 
Nhận bài ngày 27 tháng 02 năm 2017 
Hoàn thiện ngày 27 tháng 03 năm 2017 
Chấp nhận đăng ngày 05 tháng 4 năm 2017 
Địa chỉ: 1 Học viện Khoa học quân sự; 
 2 Học viện Kỹ thuật quân sự. 
 * Email: levantuan71@yahoo.com