Phương pháp xây dựng tập Slist các logarit có trọng số thấp

 THUẬT TOÁN MỚI XÂY DỰNG TẬP Slist 
3.1. Thuật toán 
Thuật toán xây dựng tập Slist đưa ra ở đây được trình bày như việc tính hàm 3 biến đầu 
vào MakeSlist(g,m,k) được thực hiện như sau. Ý tưởng của thuật toán 1 là tách số mũ ℓ 
thành hai thành phần ℓ1, ℓ2 sao cho weight(ℓ1)=1, weight(ℓ2)=weight(ℓ)-1 và ℓ= 
ℓ1+ℓ2, việc này dễ dàng thực hiện bằng việc tách 1 bit cao nhất bên trái khỏi ℓ. Các tập 
số mũ có trọng số thấp sẽ được xây dựng từ S1, và tập mới tính được sẽ bao trùm tập trước 
đó. Việc phân tích cụ thể thuật toán 1 được trình bày ở mục 3.2. 
3.1.1. Thuật toán tính hàm MakeSlist(g,m,k) 
Thuật toán 1. 
Input: k, g trong đó, k là một số nguyên dương còn # g là số m-bits. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 151
Output: Slist = {(b,ℓ): b = gℓ, weight(ℓ)  k, len(ℓ ) m }. 
1 Sindex[w]  {ℓ: ℓ[0, # g ) and weight(ℓ) = w} with 2wk; 
2 Slist  {(1,0)}; 
3 ℓ  1; 
4 b  g; 
5 S1 {(b,ℓ)}; 
6 while (ℓ<# g ) do { 
 6.1 b  b*b; //Phép * ở đây là phép toán nhóm. 
6.2 ℓ  2*ℓ; //Phép * ở đây là phép nhân thông thường. 
6.3 S1  S1{(b,ℓ)}; 
} 
7 Snew  S1; 
8 Slist  Slist  Snew; 
9 for w from 2 to k do { 
9.1 Sold  Snew; 
9.2 Snew  {}; 
9.3 ℓ  Fist(Sindex[w]); 
9.4 while (ℓ  Null) { 
9.4.1 (ℓ1,ℓ2)  Div(ℓ); 
9.4.2 (b1,ℓ1)  Search((.,ℓ1),S1); 
9.4.3 (b2,ℓ2)  Search((.,ℓ2),Sold); 
9.4.4 b  b1*b2; //* là phép toán nhóm 
9.4.5 Snew  Snew{(b,ℓ)}; 
9.4.6 ℓ  Next(ℓ,Sindex[w]); 
} 
9.5 Slist  Slist  Snew;} 
10 return Slist. 
3.1.2. Định nghĩa một số hàm sử dụng trong thuật toán 
Search((x,.),S); 
Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ nhất 
của S. 
Output: (x,b) trong S. 
Search((.,x),S); 
Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ hai 
của S. 
Output: (a,x) trong S. 
Div(x): 
Input: x  [0, 2m). 
Output: (x1,x2)  [0, 2m)[0, 2m) thỏa mãn weight(x1) = 1, weight(x1) + 
weight(x2) = weight(x) và x = x1 + x2. 
3.2. Phân tích thuật toán 1 
Trước hết, ta chứng tỏ tính đúng đắn của thuật toán 1. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 152 
Kết quả 2. Tập Slist tại đầu ra của thuật toán chứa tất cả các cặp (b,ℓ) với weight(ℓ)  k. 
Nói một cách khác thì tập này chính là tập cần xây dựng. 
Chứng minh: 
Sau bước 2 thì Slist chứa cặp (1,0) tức là tập cần lập ứng với k=0. Các bước từ 3 đến 6 
chính là tạo tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1, do đó, Slist sau bước 8 sẽ 
chứa các cặp (b,ℓ) với weight(ℓ)1. 
Giả sử quy nạp rằng tập Snew trước bước 9.1 của vòng lặp thứ w chứa tất cả các cặp 
(b,ℓ) với weight(ℓ) = w1 (điều này đã đúng với w=2), ta sẽ chứng tỏ tập này sau bước 
9.4 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w. Quả vậy, từ định nghĩa hàm Div(x) nên 
cặp (ℓ1,ℓ2) thu được trong bước 9.4.1 thỏa mãn: 
 weight(ℓ1) = 1 nên (b,ℓ1) trong bước 9.4.2 sẽ khác Null. (3.1) 
weight(ℓ1) + weight(ℓ2) = weight(ℓ) hay weight(ℓ2) = w1. (3.2) 
ℓ1+ℓ2 =ℓ. (3.3) 
Như đã chỉ ra ở trên tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1 nên với (3.1) 
cặp (b1,ℓ1), do đó, tìm được trong 9.4.2 sẽ khác "Failure" điều này có nghĩa 
b1 = 1g (3.4) 
Từ 9.1 ta có Sold chính là Snew trước bước này nên theo giả thiết quy nạp tập này chứa 
tất cả các cặp (b,ℓ) với weight(ℓ) = w1, cùng với (3.2) nên cặp (b2,ℓ2) do đó tìm được 
trong 9.4.3 sẽ khác "Failure" điều này có nghĩa 
b2 = 2g (3.5) 
Từ (3.4) và (3.5) nên giá trị b trong bước 9.4.4 sẽ là: 
b = b1*b2
)5.3(&)4.3(
 1g * 2g 
= 21g   
)3.3(
 gℓ. (3.6) 
Trong vòng lặp này duyệt toàn bộ các giá trị ℓ với weight(ℓ)=w nên Snew tính được 
trong 9.4.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w và đây là điều cần chứng minh. 
Điều trên cho thấy Slist sau bước 9.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ)w và vì thế 
sau bước 9 Slist chính là tập cần xây dựng. 
Do mỗi lần tính b = gℓ trong thuật toán 1 (bước 9.4.4) chỉ cần đúng 1 phép toán nhóm 
nên ta có kết quả sau. 
Kết quả 3. Số phép toán nhóm tối đa của thuật toán 1, ký hiệu Cost1(k,m), được đánh giá 
theo công thức sau 
Cost1(k,m)= 

k
1w
w
mC . (3.7) 
Từ (2.1) và (3.7) ta thu được hệ quả sau đây: 
Hệ quả 4. Cost0(k,m)  
1
2
k 
Cost1(k,m). 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 153
4. PHƯƠNG PHÁP BABY-STEPS, GIANT-STEPS 
TÌM LOGARIT CÓ TRỌNG SỐ THẤP 
4.1. Thuật toán 
Trong phần này, chúng tôi đưa ra một mô tả của thuật toán như sau. Thuật toán 2 dựa 
vào phương pháp baby-steps, giant-steps tách ℓ=2n ℓ1+ ℓ2 với / 2n m    , sau đó xây 
dựng các tập Sbaby và Sgiant. Sau đó, thuật toán sẽ tìm va chạm trong tập Sbaby. Việc chứng 
minh tính đúng đắn của thuật toán được làm rõ trong mục 4.2.1. 
Thuật toán 2. (tính logarit trọng số nhỏ theo phương pháp baby-steps, giant-steps) 
Input: a  g, k, m với #g là số m-bits. 
Output: ℓ = logga nếu tìm được. Ngược lại trả về "Failure". 
1 n  m/2; 
2 Sbaby  MakeSlist(g,n,k); 
3 g1  
n2g ; 
4 Sgiant  MakeSlist(g1,n,k); 
5 (b1,ℓ1)  First(Sgiant); 
6 while ((b1,ℓ1)  Null) do { 
6.1 b  a*b1; 
6.2 (b,ℓ2)  Search((b,.),Sbaby); 
6.3 if ((b,ℓ2)  "Failure") then return (2nℓ1+ℓ2); 
6.4 (b1,ℓ1)  Next((b1,ℓ1),Sgiant); 
}. 
4.2. Đánh giá thuật toán 2 
4.2.1. Khả năng tìm được các logarit trọng số thấp của thuật toán 2 
Kết quả 5. Với mọi a = gℓ thỏa mãn các điều kiện sau 
ℓ = 2nℓ1+ ℓ2 (4.1) 
 weight(ℓi)k và ℓi<2n (i=1,2) (4.2) 
Thì thuật toán 2 luôn tìm được ℓ. 
Chứng minh: Theo định nghĩa hàm MakeSlist(g1,n,k) đưa ra trong phần 2 thì Sbaby gồm 
các cặp (b,ℓ) trong đó weight(ℓ)k, ℓ<2n và b=gℓ còn Sgiant gồm các cặp (b,ℓ) trong đó 
weight(ℓ)k, ℓ<2n và b=g1ℓ =





  n2g . 
Từ (4.2) thì luôn tồn tại cặp (b2,ℓ2)Sbaby và cặp (b1,ℓ1)Sgiant tức là 
 b2 = gℓ2 còn b1 = g1ℓ1 = 
1
2ng





  
do đó, b=a*b1=gℓ*
1
2ng





  =gℓ2=b2 
nên, Search((b,.),Sbaby)=(b2,ℓ2)"Failure" 
Điều kiện trong 6.3 xảy ra và ta tìm được ℓ=logga. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 154 
Chú ý rằng từ hai điều kiện (4.1) và (4.2) về ℓ trong kết quả 5 ta có: 
 weight(ℓ) = weight(ℓ1) + weight(ℓ2) (4.3) 
điều này có nghĩa thuật toán 2 có thể tìm được tất cả các logarit với trọng số không quá k, 
thậm chí có thể tìm được cả logarit với trọng số lên đến 2k. Chẳng hạn số các logarit trọng 
số 2k có thể tìm được theo thuật toán 2 là  2knC trên tổng số k2n2C . 
4.2.2. Đánh giá Cost2 của thuật toán 
Theo công thức (3.7) trong kết quả 3 thì số phép toán nhóm cần thực hiện tại các bước 
2 và 4 của thuật toán 2 đều là 

k
1w
w
nC . Bước 3 của thuật toán này cần đến một phép tìm 
phần tử ngược trong nhóm, biết rằng công thức chung cho mọi nhóm là aℓ = a#gℓ nên số 
phép toán nhóm cần cho phép toán này là không quá 4n. Phần tìm logarit của thuật toán 
thực hiện tối đa 

k
1w
w
nC vòng trong bước 6 mà mỗi vòng cần đúng một phép toán nhóm 
tại bước 6.1, do đó, ta có: 
Cost2(k,2n)  


k
1w
w
n n4C3 (4.5) 
5. KẾT LUẬN 
Bài báo đã đề xuất 2 thuật toán mới và đưa ra đánh giá độ phức tạp tính toán của các 
thuật toán này. Sau khi đánh giá ta thấy thuật toán 1 có độ phức tạp ít hơn so với thuật toán 
truyền thống, thuật toán đề xuất thứ 2 có thể tìm các logarit trọng số lên đến 2k. Tuy 
nhiên, thuật toán 2 tốn bộ nhớ lưu trữ, vì vậy, nhóm sẽ nghiên cứu cải tiến thuật toán 2 
bằng cách sử dụng hàm băm mật mã. Hướng nghiên cứu tiếp theo của nhóm sẽ sử dụng 
hàm băm để tiết kiệm bộ nhớ lưu trữ dựa trên kết quả [6]. 
TÀI LIỆU THAM KHẢO 
[1]. V. Miller.Use of elliptic curves in cryptography. In H. Williams, editor, Advances in 
Cryptology, Proc. Eurocrypt '85, volume 218 of Lecture Notes in Computer Csience, 
pages 417-426, Springer-Verlag, 1985. 
[2]. A. Odlyzko. Discrete logarithms in finite fields and their cryptographyc significance. 
In Advances in Cryptology, Proc. Eurocrypt '84, volume 209 of Lecture Notes in 
Computer Csience, pages 224-313, Springer-Verlag, 1985. 
[3]. D. Shanks, Class number, a theory of factorization, and general. In 1969 Number 
Theory Institue, Stony Brook, N. Y., volume 20 of Proc. Sympos. Pure Math., pages 
415-440. Amer. Math. Soc., 1971. 
[4]. S. Kim, J. H. Cheon, Parameterized splitting systems for the discrete logarithm, IEEE 
transactions on Information Theory, 2009. 
[5]. A. May, I. Ozerov A generic algorithm for small weight discrete logarithm in 
composite groups, 2014. 
[6]. B. Kacsmar, S. Plosker, R. Henry, Computing Low-weght discrete logarithms, 24th 
Annual Conference on Selected Areas in Cryptography (SAC 2017). 
[7]. D.R. Stinson Some baby-step giant-step algorithms for the low Hamming weight 
discrete logarithm problem, 2001. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 155
[8]. Jung Hee Chenon, Hong TaeKim, Analysis of Low Hamming weight products, 
Discrete applied mathematics, 2008. 
ABSTRACT 
A BUIDING METHOD OF SET Slist FOR LOW WEIGHT LOGARITS 
In this paper, some methods construction set Slist, consist low-weight logarithm 
for solve discrete logarithm problem are described. Original algorithm construction 
set Slist is described, then two new algorithms in section 3, 4 are proposed; 
Complexity of new algorithms is evaluated. The proposed algorithm uses much 
memory. In the future, method using hash function for reducing storage memory, 
based on [6] will be researched. 
Keywords: Algorithm solve discrete logarithm, Solve low-weight discrete logarithm. 
Nhận bài ngày 11 tháng 07 năm 2017 
Hoàn thiện ngày 03 tháng 08 năm 2017 
Chấp nhận đăng ngày 20 tháng 12 năm 2017 
Địa chỉ: 1Ban Cơ yếu chính phủ; 
 2Học viện Kỹ thuật Mật mã, Ban Cơ yếu chính phủ. 
 *Email:nguyenthanhson@nacis.gov.vn.