Phát triển thuật toán của pollard tính cấp của phần tử trong Zn

Công nghệ thông tin & Cơ sở toán học cho tin học 
L. V. Tuấn, L. Đ. Tân, “Phát triển thuật toán của Pollard tính cấp của phần tử trong .” 152 
PHÁT TRIỂN THUẬT TOÁN CỦA POLLARD TÍNH 
CẤP CỦA PHẦN TỬ TRONG 
Lê Văn Tuấn1*, Lều Đức Tân2 
Tóm tắt: Bài viết này giới thiệu thuật toán của Pollard để giải bài toán phân tích 
số và bài toán logarit rời rạc. Dựa trên thuật toán của Pollard, chúng tôi xây dựng 
thuật toán để tính cấp của một phần tử trong . Kết quả nghiên cứu được ứng 
dụng vào phân tích độ an toàn của các lược đồ chữ ký số có độ an toàn dựa trên 
tính khó giải của bài toán logarit rời rạc trong vành Zn. 
Từ khóa: Bài toán phân tích số; Bài toán logarit rời rạc; Cấp của phần tử. 
1. MỞ ĐẦU 
Hiện nay, hệ mật khoá công khai cùng các biến thể của nó, có độ an toàn dựa trên tính 
khó giải của bài toán logarit rời rạc trên vành Zn, đang được các nhà khoa học trong nước 
và trên thế giới nghiên cứu và phát triển [1] [2] [4]. Đồng thời, việc nghiên cứu và phát 
triển các thuật toán giải bài toán logarit rời rạc trên vành Zn cũng được quan tâm bởi các 
nhà khoa học. Bởi vì những thuật toán giải bài toán logarit rời rạc trên vành Zn là cơ sở để 
xây dựng tham số an toàn cho hệ mật cùng các biến thể có độ an toàn dựa trên tính khó 
giải của bài toán này. Việc nghiên cứu ra các thuật toán để giải bài toán logarit rời rạc trên 
trường GF(p) đã được nhiều nhà khoa học nghiên cứu, phát triển và đang được ứng dụng 
trên thực tế, tiêu biểu là tác giả Pollard với thuật toán mang tên Rho Pollard [6]. Tuy 
nhiên, cho đến nay vẫn chưa có thuật toán nào trên thế giới và trong nước được công bố để 
giải bài toán logarit rời rạc trên vành Zn. Một điều hiển nhiên rằng, nếu tính được cấp của 
các phần tử trên thì hầu hết các thuật toán giải bài toán logarit rời rạc trên trường GF(p) 
có thể áp dụng để giải bài toán logarit rời rạc trên vành Zn. Vậy, để giải bài toán logarit rời 
rạc trên vành Zn, thì việc tính cấp của của phần tử thuộc nhóm có vai trò quyết định. 
Trong lý thuyết số thì hai bài toán “phân tích hợp số n ra thừa số nguyên tố” và “xác 
định cấp của phần tử trong ” đã được chứng minh là có độ phức tạp tính toán tương 
đương. Nếu như bài toán phân tích số có được một số thuật toán tìm các ước nguyên tố p 
với độ phức tạp tính toán O( ) chẳng hạn như thuật toán Rho-Pollard [5] thì với bài toán 
còn lại chỉ với thuật toán duyệt dần (vét cạn) có thể tìm được cấp của các phần tử có cấp m 
trong thời gian O(m). Trong bài viết này, chúng tôi phỏng theo phương pháp Rho-Pollard 
tính logarit rời rạc trên trường GF(p) [3] [5] để xây dựng thuật toán tính cấp m của phần tử 
trong với độ phức tạp tính toán O( ) và độ phức tạp không gian là O( ) (bit). 
2. CƠ SỞ TOÁN HỌC 
2.1. Kết quả về xác định cấp của phần tử 
Đị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 (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 (1) được gọi là 
“cấp của g trong G” và ký hiệu là ord(g) mod G hay .■ 
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 của #G, ngoài ra, nếu số tự nhiên d thỏa mãn (1) thì cũng là 
ước của d. 
Thuật toán 2.1: Thuật toán tính cấp của phần tử. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 153
Input: Cho G là một nhóm nhân và g ∈ G. Nếu và M = với là 
các số nguyên tố khác nhau. 
Output: d = . 
1. d ← M; 
2. for i from 1 to k do 
begin 
j =1; 
ok=1; 
while ((j ≤ ) and ok) do 
begin 
n = d/ ; 
ok = ; 
if (ok) 
{d = n; 
j j+1; 
} 
end while; 
end for; 
3 return d.■ 
Định lý 2.1. Thuật toán 2.1 là đúng đắn.■ 
Từ định lý trên, ta dễ dàng thu được hệ quả sau. 
Hệ quả 2.2. Cho G là một nhóm nhân và g ∈ G. Nếu và M = với 
là các số nguyên tố khác nhau và R| . Khi đó, áp dụng thuật toán 2.1 với các ước 
nguyên tố trong phần phân tích được của M ta cũng tìm được .■ 
2.2. Thuật toán phân tích số và thuật toán tính logarit rời rạc của Pollard 
Thuật toán 2.2: Thuật toán phân tích số [5]. 
Trong thuật toán này, Pollard đã sử dụng hàm giả ngẫu nhiên F(x) = ( ) mod n. 
Thuật toán phân tích số trình bày như sau: 
Input: Hợp số n. 
Output: p là ước không tầm thường của n. 
1. [Choose seeds] 
Choose random a∈ [1,n-1]; 
Choose random s ∈ [1,n-1]; 
U = V = s; 
2. [Factor search] 
U = F(U); 
V = F(V); 
V = F(V); 
p = gcd(U – V,n); 
if (p == 1) goto 2 [Factor search]; 
3. [Bad seed] 
 if (p == n) goto 1 [Choose seeds];// U và V gặp nhau 
4. [Success] 
return p;■ 
Định lý 2.3. Thuật toán 2.2 tìm được thừa số nguyên tố p của n trong O( ) bước.■ 
Công nghệ thông tin & Cơ sở toán học cho tin học 
L. V. Tuấn, L. Đ. Tân, “Phát triển thuật toán của Pollard tính cấp của phần tử trong .” 154 
2.3. Một số kết quả bổ trợ 
Để phục vụ cho thuật toán được trình bày trong mục 3, chúng tôi đưa ra một kết quả 
sau: 
Định lý 2.4. Cho s số tự nhiên ngẫu nhiên t bít ( , i = 1, 2, ..., s), 
ký hiệu d = gcd( ). Khi này, ta có xác suất để trong d có ước nguyên tố r lớn 
hơn k bít (r ), ký hiệu là , được đánh giá theo bất đẳng thức sau 
 (2) 
với u = . 
Chứng minh: 
Nhớ lại rằng với r là một số nguyên tố bất kỳ thì xác suất để r là ước của một số tự 
nhiên N đúng bằng . Như vậy, với mỗi ước nguyên tố r của cũng là ước của các 
 (do đó, cũng là ước của gcd( )) xảy ra với xác suất là . 
Từ là số t bít nên nó chỉ chứa cùng lắm là u = thừa số nguyên tố trên k bít, vậy, 
ta có ước lượng sau: 
 = 
Do r , ta có ước lượng sau: 
 ≤ 
= . 
Định lý đã được chứng minh.■ 
3. THUẬT TOÁN TÍNH CẤP CỦA PHẦN TỬ TRONG 
THEO PHƯƠNG PHÁP RHO-POLLARD 
3.1. Thuật toán 
Lựa chọn hàm F: → 
Bản chất của phương pháp Rho-Pollard là chọn trước một hàm giả ngẫu nhiên theo 
biến thứ 2 F: → trên cơ sở một phân hoạch tập thành k tập con có lực 
lượng đồng đều. Để thêm phong phú trong thuật toán được trình bày dưới đây, chúng tôi 
chọn phân hoạch theo các số đồng dư theo mô đun k=3, nói một cách khác hai hàm F(x,y) 
và E(a,b,y) được xác định theo công thức sau: 
F(x,y) = (3) 
Và do cấp của g chưa xác định nên ta không thể lập hàm tính số mũ tương ứng giống 
như công thức (3) mà hàm E: ℕ×ℕ× → ℕ×ℕ phải được xác định như sau: 
E(a,b,y) = (4) 
Thuật toán 3.1 
Input: n, g ∈ . 
Output: d = ord(g) (mod n). 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 155
1. d = 0; 
2. Chọn mầm s//[Choose seeds] 
Chọn ngẫu nhiên s, s ∈ [1,n-1]; 
x = mod n; // 
y = z = 1; 
a = b = u = v = 0; 
3. Tìm mối liên hệ giữa y và z.//[Colection search] 
(a,b) = E(a,b,y); y = F(x,y); 
(u,v) = E(u,v,z); z = F(x,z); 
(u,v) = E(u,v,z); z = F(x,z); 
if (y ≠ z) goto 3//[Colection search]; 
4. M = ; 
5. [Bad seed] 
if (M == 0) goto 2//[Choose seeds]; 
6. d = gcd(M,d); 
7. Phân tích d theo mẫu: 
 d= R. với gcd(R, ) = 1 //theo thuật toán 2.2; // 
8. Kiểm tra kết quả phân tích//[Bad factoring] 
 Nếu R là hợp số thì goto 2// [Choose seeds]; 
9. Tính toán bậc của g là d, d = ord(g) (mod n) bởi thuật toán 2.1// 
10 return d.■ 
3.2. Chứng minh tính đúng đắn của thuật toán 3.1 
Bổ đề 3.1 Với mọi giá trị y và z tính được tại bước 3 đều có dạng: 
y = mod n và z = mod n. (5) 
Chứng minh: 
Do việc tính y và (a,b) giống hệt như việc tính z và (u,v) nên ở đây ta chỉ cần chứng 
minh đẳng thức y = mod n là đủ. Quả vậy, từ bước 2 ta có x = mod p, y= 1, a= 
b= 0. Nên theo hai công thức (3) và (4) các giá trị y và (a,b) tính được tại bước lặp đầu tiên 
của bước 3 sẽ là: 
y= (x.y) mod n= x= mod n, a= a+1= 1 và b= b= 0. Suy ra y = mod n hay 
(3-3) đã đúng tại bước lặp đầu tiên của bước 3. 
Giả thiết quy nạp là (3-3) đã đúng đến bước lặp thứ i của bước 3. Ký hiệu các giá trị y, 
(a,b) tính được tại vòng thứ i+1 là y*, (a*,b*). Lại theo hai công thức (3) và (4): 
Trường hợp y mod 3 = 0, kết quả tính y* như sau: 
y* = (x.y) mod n = mod n, a* = a+1 và b* = b. Theo đẳng thức (5) ta có 
 = = = (mod n) 
Trường hợp y mod 3 = 1, kết quả tính y* như sau: 
y* = ( ) mod n, a* = 2a và b* = 2b. Theo đẳng thức (5) ta có 
 = = = (mod n) 
Trường hợp y mod 3 = 2, kết quả tính y* như sau: 
y* = (g.y) mod n , a* = a và b* = b+1. Theo đẳng thức (5) ta có 
 = = = (mod n) 
Như vậy (5) đã đúng tại vòng thứ i+1 nên theo nguyên lý quy nạp ta có (3-3) đúng tại 
mọi bước lặp của bước 3 và bổ đề đã được chứng minh.■ 
Định lý 3.2. Thuật toán 3.1 là đúng đắn. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
L. V. Tuấn, L. Đ. Tân, “Phát triển thuật toán của Pollard tính cấp của phần tử trong .” 156 
Chứng minh 
Trước hết, ta chứng tỏ rằng các giá trị M tìm được tại bước 4 là bội của ord(g). 
Quả vậy, do bước 4 được thực hiện chỉ khi y= z nên theo bổ đề 3.1 ta có đồng dư 
thức sau: 
= (mod n) hay = = 1 (mod n). Theo tính chất của cấp 
của g là số nguyên dương nhỏ nhất thỏa gord(g)=1 mod n, từ đẳng thức = 1 (mod n) dẫn 
đến M là bội của ord(g) ■. 
Từ điều chứng minh được trên, ta có, d xác định tại bước 6 cũng là bội của ord(g) nên 
theo định lý 2.1 ta có giá trị d tìm được tại bước 9 của thuật toán (và cũng là đầu ra của 
thuật toán 3.1) đúng bằng ord(g) vậy định lý đã được chứng minh.■ 
3.3. Độ phức tạp thời gian và không gian của thuật toán 3.1 
Bổ đề 3.3. Nếu hàm E cho theo công thức (4) là giả ngẫu nhiên theo (a,b,y) thì bước 3 
của thuật toán 3.1 thực hiện trong khoảng O( ) bước. 
Chứng minh: 
Trong mỗi bước trong vòng 3 của thuật toán kiểm tra điều kiện y = z, điều kiện trên 
theo bổ đề 3.1 là tương đương với điều kiện: 
s.a+b = s.u+v (mod ord(g)). (6) 
Theo giả thiết của bổ đề, hai vế của (6) được coi là các số ngẫu nhiên nên theo định 
lý ngày sinh thì trong khoảng cặp (s.a+b, s.u+v) sẽ tồn tại ít nhất một cặp 
thỏa mãn (6) với xác suất (e là số tự nhiên ≈ 2...). Điều trên có nghĩa trong 
khoảng O( ) bước ta sẽ tìm được 1 cặp thỏa mãn (6) và điều này đã chứng 
minh xong bổ đề.■ 
Hệ quả 3.4. Kích thước của các biến a, b, u, v và do đó, các biến d, M trong thuật toán 
3.1 cho theo công thức: 
O( ) (bits) (7) 
Quả vậy, theo công thức (4) thì sau mỗi vòng trong bước 3 các giá trị a, b được tăng 
lên tối đa là 1 bít còn hai gia trị u, v được tăng lên tối đa 2 bít (ứng với y và z đều chia 
hết cho 3)). Số vòng của bước này, theo bổ đề 3.3 là O( ) với a, b, u, v xuất phát 
đều bằng 0 cho nên kích thước của 4 biến nêu trên được cho bởi (7) và hệ quả đã được 
chứng minh.■ 
Bổ đề 3.5. Sau s giá trị M tìm được thì giá trị d tính trong bước 6 sẽ qua được bước 8 
trong thuật toán 3.1 với xác suất bằng . (8) 
Chứng minh: 
Trong giải tích cổ điển ta có , điều này có nghĩa khi x đủ nhỏ thì 
 ≈ u.x. 
Theo hệ quả 3.4, giá trị M là số cỡ O( ) bít nên trong phạm vi ord(g) đủ nhỏ để 
thuật toán 3.1 có thể tìm được các giá trị M, chẳng hạn, cỡ k bít thì cỡ của biến M sẽ là cỡ 
 bits. Lại từ định lý 2.3 cho thấy với khả năng độ phức tạp tính toán là thì 
có thể tìm được các ước không tầm thường cỡ (tức là các ước cỡ k bít), vì vậy, có 
thể coi giá trị t = trong định lý 2.4 và theo định lý này ta có xác suất để giá trị d tìm 
được trong bước 6 của thuật toán 3.1 sau s lần tính M có chứa ước nguyên tố lớn hơn 2k 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 157
(ngưỡng phân tích được của thuật toán 2.2) nhưng không là ước của org(g), cũng chính là 
xác suất d có thể không qua được bước 8 là: 
 = ≈ ≤ . (9) 
Đến đây bổ đề đã được chứng minh.■ 
Với nhận định 2.4 về khả năng thực hiện được thuật toán 2.2 (giá trị k lớn hơn 40) nên 
với s = 2 thì biểu thức (8) sẽ cho giá trị lớn hơn 0.999999, với s= 3 sẽ là lớn hơn 
0.999999999999999999 ... nên ta có thể kết luận như sau: 
Định lý 3.6. Thuật toán 3.1 có độ phức tạp thời gian là và độ phức tạp không 
gian là bít để tìm được ord(g).■ 
4. VÍ DỤ 
Ứng dụng thuật toán 3.1 để tính bậc của g với g = 2 trên vành Zn, với n = 4292870399 
= 65519 * 65521. Tại bước 2 của thuật toán, ta chọn mầm s = 2. Sau 12058 vòng lặp bước 
3, các giá trị y và z được tìm thấy như sau: 
y = 2739898200 
z = 2739898200 
Với s = 2, tại bước 4 của thuật toán đã tìm ra M với len(M)=502*16=8032 bit ứng với 
số 2414 chữ số thập phân: 
24403621586051107094504468678501919369704426597569428913208694650330503328
35011756603533747150762031373495855735839791869089565772846233197223578906307367
04728805485582809118307820445190432806827010085952415241918529162237525348863373
94497187969417732182173162851821116494312556137658504319311781416792018803394519
26985597371971869304564180385101066181647982979769199693035572500706487026812730
48589722387013998281765567588736535499801535016032949850789453364324160337552195
44946610792809222326014221061200444015009958208347325244371891392679533728628971
55200082408112885789761383595314143318122662397080896223398021567631763246654426
34838235140249720968286351107544662694155836604724119426596089874691961532150151
79244230055534459989723640238221713093390789291715816899093087107827254635786841
65376349427918128814301606550654805288415836107760272756874108309061484890714075
02455016210949708080111033549777447568186382348355658061628814035690576529002324
61609895311959864118509872787957521199607454681668481710195907318232249935130788
58327581435279423955975632939598368017606982123226557138481927589283973133498830
83717826422674150915629798091012406309254808690367868958896734269081431166291639
81427739568161474249666669942018418666376231535769138698805928090771678353228787
50664729806285759973488780566853467944009319895883261016019511499302034671971405
77506645126448271222111797558208264424019639226395618940852141845597963524614991
82556487217783218114576062188612752157095025794299843426983097135023057823142572
25517761385766744300219520397784527792338411840341494326998947485625528403096184
13010370311415926209035782911282823000287897654245871324684196743234878770620667
60695473643806409076482214134695296933492261421618229443076339775884037419939988
67078167669673669724849576089433577547617209172628083149245948693169579929992130
46410647955253731813347941864798224644891556686357112956144657816673984491550158
60023341155670847249468276296809359088409612534427721810595419674326893201158641
02936105205499371837125777140543498884689899348539228939838999597680600343301171
64854432035691240594086951068710377387437844821575831555136198259885779831722944
24341710730597163288094997825627620400548175315656737467930121248632364348135464
09930698589204059627100515149160577711335798773336894294421625847586601669152900
Công nghệ thông tin & Cơ sở toán học cho tin học 
L. V. Tuấn, L. Đ. Tân, “Phát triển thuật toán của Pollard tính cấp của phần tử trong .” 158 
67027092741410749183647565560694025638149186629695615216675530122045232012568519
40523342617148129280. 
Bước 5 của thuật toán 3.1 tìm ra M 0 nên thuật toán chuyển sang bước 6. Vì d được 
khởi tạo giá trị 0 nên kết quả bước 6 tìm ra ngay giá trị d= gcd(M,d) chính là M. Bước 7, 
thuật toán phân tích số d về dạng chuẩn như sau: d = R. , với gcd(R, ) = 1. 
Kết quả phân tích là: 
d=2^3086*3^2*5*7*13*17*41*47*293*1627*40091097706832788303502964307070
12825368753073686519561729330751274879323401255449199583735087499291906205014049
45717825120127655221516295089210322935739573395888641017882230232720950104264926
31700577737258519214044779806113567880049809028078167392050836688337045791715440
62615675321431327621739908904130675999563284350310836383210607458743326940699743
28519563150951983424245829028188561063106144456186526992242855530370378178723726
28069235340269359310951869600724879945915989898246587036431812803233472162268513
96066610115908399560563913970645076435636581980323873016153008309982428564342508
72658668266110768415251178168658307934438975836279498732955054496216629093669433
34375900384084003729344337817495405501800740592422875703026476204218214667222796
27265454211470315675181090321185406085034275466334298147087401126875177668056255
40231342577498408949978913162530368296072418567841244891056154211419017056934471
66321065072841007635451093124696202511568200807663932273935821083851611950711746
35963732134122839245612159189173985822327963112822497120934804776598803544906053
04940868783385572188969674427340264205187128576939671414234801776791285070994297
23075221746522885241419381292519694696396199914474494339916521196974839381899689
35299066804733237939526639426131186035851187787298329516290988101516697150670709
43548134368308186779817347893712548878667247532182506067495682717254060236100365
8232334430935632208262428808731923611580132447287292641099618985774198296746059. 
Đồng thời tại bước 7 kiểm tra điều kiện gcd(R, ) = 1. Tại bước 8 của thuật toán 
3.1, ứng với s = 2, thực hiện kiểm tra giá trị R là hợp số hay số nguyên tố. Với giá trị R 
dưới đây: 
40091097706832788303502964307070128253687530736865195617293307512748793234
01255449199583735087499291906205014049457178251201276552215162950892103229357395
73395888641017882230232720950104264926317005777372585192140447798061135678800498
09028078167392050836688337045791715440626156753214313276217399089041306759995632
84350310836383210607458743326940699743285195631509519834242458290281885610631061
44456186526992242855530370378178723726280692353402693593109518696007248799459159
89898246587036431812803233472162268513960666101159083995605639139706450764356365
81980323873016153008309982428564342508726586682661107684152511781686583079344389
75836279498732955054496216629093669433343759003840840037293443378174954055018007
40592422875703026476204218214667222796272654542114703156751810903211854060850342
75466334298147087401126875177668056255402313425774984089499789131625303682960724
18567841244891056154211419017056934471663210650728410076354510931246962025115682
00807663932273935821083851611950711746359637321341228392456121591891739858223279
63112822497120934804776598803544906053049408687833855721889696744273402642051871
28576939671414234801776791285070994297230752217465228852414193812925196946963961
99914474494339916521196974839381899689352990668047332379395266394261311860358511
87787298329516290988101516697150670709435481343683081867798173478937125488786672
47532182506067495682717254060236100365823233443093563220826242880873192361158013
2447287292641099618985774198296746059, 
Kết quả kiểm tra cho thấy giá trị R là hợp số nên việc chọn giá trị mầm s phải được 
thực hiện lại. Trong lần lặp tiếp theo của thuật toán 3.1, giá trị mầm s được chọn là 3. Sau 
16654 vòng lặp trong bước 3 của thuật toán, đã tìm ra giá trị y và z như sau: 
y = 4218529016 
z = 4218529016 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 49, 06 - 2017 159
Tại bước 4 của thuật toán ứng với s=3, đã tìm ra giá trị M (len(M)=11600 bit), giá trị 
đó là: 
M=11675813215898891881236242812163533751078264322914648027222856893780714
97173231687286473794200686807832631550022765063338345596269795974463688033619362
90170504932285914321200154804184326265761671355280027423904292581797985718676501
58810903687393227223567374248487438000625157461820231271109386787257275950761742
99248084010087293734304477773582501945455127227324777001949506840616175587332750
93973917102738195885068737000831904043107639351414484230961895010996135445448156
63255191414945334051814011263463319849643993847461456484718703001476867555736431
55123635817734756338130482108283568541769246422573660541802301530172114245758933
88133666945851259496413393553894644437994096708817162863201500496561605554952616
84062854941356535934455804140184267092695974694637204582585592298870285470999252
87076473765141376855476720758645220058554979739033270181608955893238711136561966
41696548939429327614923650257193912873719411130813229715864185293386965637451589
34122723691479033070435269327369758312685864876290551689305104397390135163357016
05524966191941422596114078749386843869674534802931282452069366081795176264964815
98892427893469113438422088295186975676744078177317370162895279282909337433055286
04021608593894309223977854608635087052301515188040688005931675000139110413189078
40010730800256382013296603766874911229443476239899727908467416251802672614808693
41052167224495234348227012014180153678019709306967222777172662235258942491250055
82893678754512690865786957866107081771656430743476601281048078055850413160458925
44321532187251156191905166964846257437198054263669254012684099922620149680055411
97837658811225339274668805831055695770405747985103698384394521285028813938575228
15829277008144530443843901652723344161652311595002731238914899602305895327460807
74038182987613159054239544579957199189444145652246297348231112985743085247725922
54280828582130305049088182725367247570453342412223736977686437814845905877459786
09777685217032642526313703518029277196411576603397859787758106225491134251821245
05257928063007108240224179829260346439449569903331852602259066845457230692262311
01751262537326147600668221821679579613240778116923110417640199848296091103946059
71182506624575243855637952935344199636048281053585724581995443387459733621266369
19104207194185042013772362641680836976868389430055593633163278102206712303113283
47695751547813301837584153921832882777813854491701557864135919428472274278889874
23159926176918019598752462619934400885632441538523242205835727461342308662115736
96690765814630544299307691114447659590771868965382491073403271224967919317733118
75445415767717727413845096967234079779110758994938470652919022063243016702616185
23987265966691691912756023008645273913065474917665262081185468610091143455533456
81548833358323946443595678948156769284384258789866126671790082567219032479016427
78057119981582223526529821121310380374797411578523092000184677142919066676145427
65080629580165374444451696863085369494706636770797498830260820405487413857627625
95005473675309785844787699318503770395873229373039692701174056621080807121057171
98954998609428720021263119006237520742048892068410727257754247165063163442803612
31970478887620300336899975908037193406839201471758277960803200971767002557763689
38686017037323517386611711318249371074539009908470266655297678395864559501588357
93976463113174492544883647084327621470987556723897216375520751058655790123383677
98920430210291464117404484675442368930060961188249045018358858482903675838512706
9711701363448453657935940092102840975966769568699991982080. 
Khi đó, kết quả tính d tại bước 6, d= gcd(M,d) như sau: 
32611193226558320238792399859487438645120431994207509375796189953792521856
70432450848683683099125473311247328690626286372933523472707464886491144748267320
39913200276956473180242714067035557336816246031700399110187690721406807880737693
47641960088401909723586181445294801093820431889640891733029330944873767855240203
82523977857257093846419891949595397115666189881890549655407366456493702101050974
00120284150733158940103263150482213778156660424713685859087858914491843097476421
02734404068874420855023096988027301529367483137690306407281767178934806989400508
Công nghệ thông tin & Cơ sở toán học cho tin học 
L. V. Tuấn, L. Đ. Tân, “Phát triển thuật toán của Pollard tính cấp của phần tử trong .” 160 
37408898889435733465724981179847425036083527097018838584417560579652929747679548
8994139742617970697451492214200577890108406901107589120 
Bước 7, kết quả phân tích d về dạng chuẩn là: d= 2^2263*3^2*5*13*17*41*47. Kết 
quả tính bậc của g theo thuật toán 3.1 là: Ord(g)=38328030 
Trong ví dụ trên, giá trị M được tính trong bước 4 của thuật toán 3.1 rất lớn, lý do vì 
thuật toán đã sử dụng công thức (4), được phỏng theo công thức thuật toán của Pollard, tức 
là các toạ độ (a,b) không được rút gọn theo cấp của g, đây là sự trả giá về không gian lưu 
trữ mà thuật toán 3.1 yêu cầu. 
5. KẾT LUẬN 
Bài báo đã giới thiệu thuật toán “phân tích số” và thuật toán “tìm logarit rời rạc” của Rho 
Pollard. Phỏng theo phương pháp của Rho Pollard, chúng tôi đã xây dựng được thuật toán 
tính bậc của phần tử bất kỳ trong và cài đặt thành công thuật toán trên ngôn ngữ lập trình 
C++. 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 tính đúng đắn, tính dừng. Kết quả nghiên cứu khẳng định rằng với khả 
năng tính toán của máy tính hiện nay, việc tìm được toàn bộ các ước nguyên tố không quá 
 của một hợp số cỡ vài ngàn chữ số thập phân là khả thi. Kết quả nghiên cứu làm cơ sở 
để xây dựng hệ tiêu chuẩn về tham số cho các hệ chữ ký số và biến thể 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]. C Meshram. “Discrete Logarithm and Integer Factorization using IBE”. ISSN: 2089-
3191, Bulletin of Electrical Engineering and Informatics Vol. 4, No. 2, June 2015, 
160-168. 
[3]. Douglas R. Stinson, “Cyptography theory and practice”, 2003, 191-193. 
[4]. OKAMOTO E, (1987), “Key distribution systems based on identification 
information”, Proc. Of Crypto. 
[5]. Richard Crandall, Carl Pomerance. “Prime Numbers, A Computational Perspective”, 
Second Edition, Springer Science + Business Media, Inc, 2005, 229-231. 
ABSTRACT 
DEVELOPING POLLARD ALGORITHM 
TO COMPUTE ORDER OF ELEMENTS IN 
Abstract: In this submission, Pollard's the large integer factoring algorithm and 
the algorithm for solving discrete logarithm problem have been introduced. Based 
on these logarithms, an algorithm to compute the order of elevents in is 
developed. The results are able to apply on analysing security of digital signature 
schemes, which are on basis of discrete logarithm problem in ring Zn. 
Keyword: Large integer factoring Problem; Discrete Logarithm Problem; Order of elevents. 
Nhận bài ngày 19 tháng 4 năm 2017 
Hoàn thiện ngày 29 tháng 5 năm 2017 
Chấp nhận đăng ngày 20 tháng 6 năm 2017 
Địa chỉ: 1 Học viện Khoa học quân sự; 
 2 Học viện Kỹ thuật Mật mã. 
 *Email: levantuan71@yahoo.com