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

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 129
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 
Lê Văn Tuấn1*, Bùi Thế Truyền2 
Tóm tắt: Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường 
hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của 
Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. 
Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của lược đồ chữ ký số 
trên bài toán logarit rời rạc trong vành Zn 
Từ khoá: Vành hữu hạn, Trường hữu hạn, Bài toán logarit rời rạc. 
1. MỞ ĐẦU 
Tương tự bài toán phân tích số nguyên lớn ra thừa số, bài toán logarit rời rạc 
thuộc lớp bài toán khó giải. Hiện nay, một lớp hệ mật khóa công khai và biến thể 
của nó được xây dựng dựa trên độ khó của bài toán này. Tuy nhiên, bài toán logarit 
rời rạc không phải khó giải trong mọi trường hợp. Chính vì thế, các nhà khoa học 
đã lợi dụng những trường hợp không khó của bài toán để xây dựng các thuật toán 
giải bài toán logarit rời rạc. Một thực tế cho thấy, đa số các thuật toán giải bài toán 
logarit rời rạc hiện nay, chỉ áp dụng được trên trường hữu hạn Zp. Trong khi đó, 
một số hệ mã khóa công khai và các biến thể của nó được xây dựng trên cấu trúc 
vành Zn. Với mục tiêu nhằm loại bỏ những mầm mống không an toàn cho các hệ 
mật khoá công khai và các hệ chữ ký số dựa trên độ khó của bài toán logarit rời rạc 
trên vành Zn, trên cơ sở tìm hiểu những thuật toán giải bài toán logarit rời rạc đã 
được công bố trên thế giới[2][3][5] và một số công trình liên quan đến bài toán 
logarit rời rạc trên vành Zn,[1][4][8], chúng tôi phát triển thuật toán Baby step 
Giant Step của Danied Shanks để giải được bài toán logarit rời rạc trên vành Zn. 
Giả sử nhóm cyclic G= là nhóm con của nhóm nhân và cỡ bậc của g là m 
bit. Khi đó bậc của g thuộc đoạn [2m-1,2
m-1] và khoảng tìm giá trị logarit rời rạc 
thuộc đoạn [0,2m-1]. Trong bài viết 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. Việc tìm logarit rời rạc thuộc đoạn [2
m-1,2m-1] nằm ngoài phạm vi nghiên 
cứu trong bài báo này. Kết quả nghiên cứu là cơ sở để xây dựng tiêu chuẩn tham số 
an toàn [9] cho hệ chữ ký số, hoặc các biến thể của nó dựa vào độ khó của bài toán 
logarit rời rạc trên vành Zn. 
2. CƠ SỞ TOÁN HỌC 
2.1. Một số ký hiệu, định nghĩa và tính chất 
Bitlength(M): Hàm trả về số bít của số nhị phân biểu diễn M. 
#G: Chỉ bậc của nhóm G. 
OrdG(g): Chỉ bậc của phần tử g thuộc tập G. 
Định nghĩa 2.1: Cho G là một nhóm nhân với phần tử đơn vị là 1 và g ∈ G. 
Nếu tồn tại số tự nhiên d sao cho 
 = 1 (2.1) 
thì g được gọi là “có cấp hữu hạn” và giá trị d nhỏ nhất thỏa mãn đẳng thức (2.1) 
được gọi là “cấp của g trong G” và ký hiệu là ord(g) mod G hay .■ 
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.” 130 
Lưu ý. Nếu G là nhóm hữu hạn thì mọi phần tử trong G đều có cấp hữu hạn và 
 luôn là ước bậc của nhóm G, ký hiệu |#G, ngoài ra, nếu số tự nhiên d 
thỏa mãn (2.1) thì cũng là ước của d. 
Định lí 2.1: Cho G= Zn
*(n= pxq), [2m-1,2m-1], 1 k1,k2 2
m-1, thoả 
mãn: 
 gk1=b mod n (2.2) 
và gk2=b mod n (2.3) 
thì k1=k2. 
Chứng minh: Giả sử k1 k2 không giảm tổng quát, giả sử k1>k2, từ (2.2) và (2.3) 
ta có = 1 mod n, khi đó (k1-k2), nghĩa là k1-k2 2
m-1, điều này mẫu 
thuẫn với giả thiết 1 k1,k2 2
m-1■ 
Định lý 2.2 [11]: 
Giả sử Γ...m1m là các số nguyên dương nguyên tố cùng nhau từng đôi một và 
cho Γ...a1a là các số nguyên. Khi đó, hệ r đồng dư thức )i(modmiax (1<=i<=r) 
sẽ có một nghiệm duy nhất theo modulo M= Γ1 m...m được cho theo công thức: 
x= iii
Γ
1i
yMa
 mod M, trong đó và yi= M
-1 mod mi với 1<=i<=r. 
Bổ đề 2.1. Cho nhóm cyclic G= có bậc M, M= RS và k=loggx mod M ta có: 
k= S
g
xlog S mod R
 (2.4)
k= R
g
xlog R mod S (2.5) 
Bổ đề 2.2. Cho G= có bậc M=Rc, i=loggx=i0+i1R+...+ic-1R
c-1 ta có: 
i0=
1
c-1R
log ( )
cR
g
x
. (2.6) 
it= ))xg((log
1tc1t
1t0 RRi...i
g
1-cR
 (t=1,...,c-1). (2.7) 
2.2. Logarit rời rạc và ứng dụng 
Định nghĩa 2.2: Cho G= bậc M, khi đó  G,  duy nhất ZM sao cho 
=g . Giá trị được gọi là logarit rời rạc [10]cơ số g của  và ký hiệu logg. Cho 
trước phần tử g G, khi đó, với mọi  G= việc tìm logg được gọi là bài toán 
logarit rời rạc trên G. 
Định nghĩa 2.3: 
Cho p là số nguyên tố lẻ, G==Z*p , g là phần tử nguyên thuỷ của Z
*
p và  
Z*p. tồn tại duy nhất ,0 p-1 sao cho g
  mod p. Giá trị được gọi là logarit 
rời rạc [10] cơ số g của , ký hiệu là logg. Cho trước phần tử g Z
*
p, khi đó, với 
mọi  Z*p, tìm logg gọi là bài toán logarit rời rạc[10] trên trường Zp. 
Tính chất 2.1: 
log(1.2. . . .k )log1+log 2+ . . + log k(mod p-1). (2.8) 
Tính chất 2.2: 
log
.log(mod p-1) (2.9) 
Ứng dụng bài toán logarit rời rạc: 
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 131
Một lớp các hệ mã khoá công khai và biến thể quan trọng mà độ an toàn của nó 
dựa trên tính khó giải của bài toán logarit rời rạc, chẳng hạn như hệ mã khóa công 
khai của Elgamal, giao thức trao đổi khóa Diffie-Hellman v.v... Trong phần này, 
bài báo sẽ trình bày ứng dụng bài toán logarit rời rạc trong xây dựng hệ mật khóa 
công khai Elgamal và hệ chữ ký số Elgamal. Giả sử một hệ thống truyền tin sử 
dụng hệ mã khóa công khai Elgamal trên trường Zp để bảo mật thông tin. Khóa của 
hệ mã xây dựng theo các bước như sau: 
Thuật toán 2.1: 
+ Bước 1: Chọn số nguyên tố p đủ lớn sao cho bài toán logarith trong pZ là khó giải. 
+ Bước 2: Chọn *pZα là phần tử nguyên thủy. 
+ Bước 3: Chọn x là số ngẫu nhiên sao cho 1<x<p. 
+ Bước 4: Tính giá trị y thỏa mãn công thức: modxy p 
Khóa bí mật là x, còn khóa công khai là bộ gồm 3 số (y, p, ). 
Để mã hóa bản rõ R bên gửi sử dụng khóa công khai của bên nhận là bộ ba số 
(y,p, ). Tiếp theo chọn số ngẫu nhiên k và tính 
 pmodkαC' ( 2.10) 
 pRmodkyC" ( 2.11) 
Sau đó gửi bản mã gồm CC , đến bên nhận. 
Một ứng dụng khác của bài toán logarit rời rạc là xây dựng lược đồ chữ ký số 
Elgamal. Quá trình tạo khóa giống như qúa trình tạo khóa của hệ mật Elgamal, tức 
là chọn số nguyên tố p đủ lớn để bài toán logarith rời rạc trên Zp là khó giải, và 
chọn 
*
pZα là phần tử nguyên thủy, chọn 1px A là số nguyên làm khóa bí mật 
và tính khóa công khai yA= (modp)α A
x . Để ký lên bức điện m
*
pZ bên ký tạo ra 
số ngẫu nhiên k thỏa mãn 1pk và UCLN(k, p-1)=1 và hình thành nên chữ ký 
là cặp (r,s), ở đây r và s tính như sau: 
Thuật toán 2.2: 
.1)r)(modpx(mks
(modp),αr
A
1
k
 

( 2.12) 
(2.13) 
Xác nhận chữ ký (r,s) trên bức điện m, bên nhận thực hiện như sau: 
Thuật toán 2.3: 
Verify( ,yA,p)(m,(r,s))=TRUE, nếu như r < p và p) (modαry
msr
A  ( 2.14) 
Verify( ,yA,p)(m,(r,s))=FALSE, nếu r>p hoặc p) (modαry
msr
A ( 2.15) 
3. GIẢI BÀI TOÁN LOGARIT RỜI RẠC 
Việc tấn công các hệ mã khóa công khai hoặc biến thể của nó dựa trên độ khó 
của bài toán logarit rời rạc đều phải giải bài toán này. Chẳng hạn kẻ tấn công 
muốn khám phá bản mã (C”,C’) được tạo ra trong thuật toán 2.1, để tìm ra bản rõ 
R, đầu tiên cần phải xác định khóa bí mật x từ phương trình . Từ giá 
trị x tìm được, với biểu hình mã (C”,C’) ta dễ dàng khôi phục bản rõ R theo công 
thức sau đây: 
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.” 132 
Tính giá trị: '
x xk kxZ C (2.16) 
Tính gía trị nghịch đảo của Z: 1 modkxZ p (2.17) 
Tính R = C”. Z-1 (modul p) (2.18) 
Một trong các kiểu tấn công hệ chữ ký số là giả mạo chữ ký được tạo ra trong 
thuật toán 2.2, muốn vậy kẻ tấn công phải có khóa bí mật xA, tức là phải giải 
phương trình yA= (modp)α A
x , đây là bài toán khó giải nếu tham số của hệ chữ ký 
được xây dựng an toàn[9]. Trên thực tế, bài toán tìm logarit rời rạc không phải khó 
giải trong mọi trường hợp, chẳng hạn như bậc của trường hữu hạn Zp không đủ 
lớn, hoặc p-1 có các ước số nguyên tố nhỏ thì bài toán logarit rời rạc trên đó sẽ 
không khó. Dựa vào những trường hợp không khó của bài toán mà các nhà khoa 
học đã phát minh ra một số thuật toán để giải nó. Trong phần này, bài báo sẽ trình 
bày một số thuật toán giải bài toán logarit rời rạc trên trường Zp. 
3.1. Thuật toán Baby-step Giant-step của Danied Shanks [2][3][6] 
Nếu số nguyên tố p không đủ lớn, một thuật toán có độ phức tạp về thời gian và 
không gian tính toán là O( ) có thể tính khóa bí mật x. Dưới đây giới thiệu một 
thuật toán Baby-step Giant-step của Danied Shanks. 
Giả sử cho G= = Zp
* là một nhóm cyclic bậc p-1 sinh bởi g và b G. Bài 
toán đặt ra là tìm k sao cho gk = b. Thuật toán Baby-step Giant-step của Danied 
Shanks được miêu tả như sau: 
Thuật toán 3.1: 
Input: Nhóm cyclic G= = Zp
* có bậc p-1, b G. 
Output: k= loggb. 
Bước 1: q ← // q nhận giá trị là cận trên của 1p 
Bước 2: Với mỗi i, 0 ≤ i < q tính (i,b.gi), 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), lưu trữ trong danh sách T và sắp xếp 
(Giant step) 
Bước 4: Tìm trong danh sách S giá trị b.gi bằng với giá trị gq.j trong T, khi đó k= qj-i. 
Độ phức tạp về thời gian và không gian nhớ là O( 1p ), 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 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