Giáo trình Số học thuật toán - Chương 4: Thặng dư bình phương

hiệm hay 
không. Mặc dầu vậy, kí hiệu Jacobi có nhiều tính chất t−ơng tự với kí hiệu 
Legendre. 
Định lí 4.13. Giả sử n là số nguyên d−ơng lẻ, a và b là các số nguyên tố cùng nhau 
với n. Khi đó: 
(i) Nếu a≡ b(mod n) thì a
n
b
n



 =



 . 
(ii) 
ab
n
a
n
b
n



 =







 
(iii)
−



1
n
=(-1)(n-1)/2 
 68
(iv)
2
n



=(-1)
(n
2
-1)/8 
Chứng minh. Hai đẳng thức đầu tiên dễ suy ra từ định nghĩa kí hiệu Jacobi và tính 
chất của kí hiệu Legendre. 
Để chứng minh tính chất thứ 3, ta nhận xét rằng, do (pi-1) chẵn nên 
(1+(pi-1))
t1≡ 1+ti(pi-1)(mod 4), 
(1+ti(pi-1))(1+tj(pj-1)) ≡ 1+ti(pi-1)+ tj(pj-1)(mod 4). 
Từ đó suy ra: 
n≡ 1+t1(p1-1)+t2(p2-1)+...+ tm(pm-1)(mod 4), 
tức là, 
(n-1)/2≡ t1(p1-1)/2+t2(p2-1)/2+...+ tm(pm-1)/2(mod 2) 
Hệ thức này cùng với định nghĩa cho ta đẳng thức (iii). 
Chứng minh (iv). Ta có: 
2 2 2 2
1
1 2
1 8 1 8 1 8
1 2
1 1
2
2 2
2 2
n p p p
t t
m
t
t p t p t p
m
m m



 =











 = −
− + − + + −... ( ) ( )/ ( ) / ... ( ) / 
Lập luận t−ơng tự nh− trong chứng minh phần trên,ta có: 
n2≡ 1+t1(p12-1)+t2(p22-1)+...+ tm(pm2-1)(mod 64), 
và khi đó (iv) suy ra từ định nghĩa. 
Định lí 4.14. (Luật thuận nghịch bình ph−ơng đối với kí hiệu Jacobi). Giả sử m, 
n là các số nguyên d−ơng lẻ, nguyên tố cùng nhau. Khi đó: 
n
m
m
n
m n






 = −
− −
( )1
1
2
1
2 . 
Chứng minh. Giả sử m, n có phân tích ra thừa số nguyên tố dạng: 
m=p1
a 1 p2
a 2 ...ps
a s , n=q1
b 1 q2
b 2 ...qr
b r . Dùng định nghĩa và luật thuận nghịch bình 
ph−ơng của kí hiệu Legendre, ta đ−ợc: 
n
m
m
n j
s
i
r a
p
b qj
j
i
i
a j
p j
bi
qi
j
s
i
r







 = − = −
∑∑
==
− −∏∏
− −
==
11
1
2
1
21 1
1
2
1
2
11( ) ( ) . 
Nh− trong chứng minh định lí 4.13, (iii), ta có: 
 69
a
p m
b q n
j
j
j
s
i
i
i
r
− ≡ −
− ≡ −
=
=
∑
∑
1
2
1
2
2
1
2
1
2
2
1
1
(mod ),
(mod ).
Từ đó suy ra định lí. 
Đ4. Thuật toán tính kí hiệu Jacobi. 
Giả sử a, b là hai số nguyên d−ơng nguyên tố cùng nhau, a>b. Đặt R1=a, R2=b. 
Dùng thuật chia Eulid và tách luỹ thừa cao nhất của 2 trong phần d−, ta đ−ợc: 
 R0 = R1q1 + 2
s 1 R2 
R = R q + 2 R
R = R q + 2 R
R = R q + 2 .1
1 2 2
s
3
n-3 n-2 n-2
s
n-1
n-2 n-1 n-1
s
2
n-2
n-1
................................
trong đó sj là các số nguyên không âm, Rj là số nguyên lẻ bé hơn Rj-1. 
Ta chú ý rằng, số các phép chia đòi hỏi trong thuật toán trên là không v−ợt quá số 
phép chia cần thiết khi dùng thuật toán Euclid để tìm −ớc chung lớn nhất của hai số 
a và b. 
Đặt: 
R a b s R s R s R R R R Rn n n n( , ) ... . ... . .= − + − + + − + − − + + − −− − − −1 1
2
2
2
2
1
1
2
1 2 2 11
8
1
8
1
8
1
2
1
2
1
2
1
2
Ta có định lí sau. 
Định lí 4.15. Giả sử a,b là các số nguyên d−ơng và a>b. Khi đó ta có: 
a
b



=(-1)
R(a,b) 
Chứng minh. Theo các phần (i), (ii), và (iv) của định lí 4.13 ta có: 
a
b
R
R
R
R R
R
R
R
R
s s s R


 =



 =




= 





 = −




−
0
1
2
1 1
2
1
1
8 2
1
2 2
1
1 1
1
1
2
( ) . 
Dùng luật thuận nghịch bình ph−ơng của kí hiệu Jacobita đ−ợc: 
 70
R
R
R
R
R R
2
1
1
2
1
2 1
2
1
1 2


 = −




− −
( ) . 
Nh− vậy, 
a
b
R
R
R R s R


 = −




− − + −
( )1
1 2
1
1
21
2
1
2
1
8 1
2
Tiếp tục quá trình đó, ta đi đến công thức cần chứng minh. 
Hệ quả 4.16. Giả sử a và b là các số nguyên d−ơng nguyên tố cùng nhau, a>b. Khi 
đó, kí hiệu Jacobi 
a
b



 có thể tính đ−ợc với O((log2b)
3) phép tính bit. 
Chứng minh. Nh− ta đã nhận xét, số các phép chia trong thuật toán xác định R(a,b) 
không v−ợt quá số phép chia trong thuật toán Euclid để tính −ớc chung lớn nhất của 
a và b. Theo định lí Lamé, cần có O(log2b) phép chia. Mỗi phép chia cần không 
quá O((log2b)
2) phép tính bit. Sau mỗi phép chia, cặp số Rj, sj tìm đ−ợc bởi O(log2b) 
phép tính bit (chỉ cần là các phép dịch chuyển). Nh− vậy, khi biết a, b, chỉ cần 
O((log2b)
3) phép tính bit để xác định các số Rj, sj. Để nâng (-1) lên luỹ thừa R(a,b) 
nh− trong định lí, ta chỉ cần sử dụng 3 chữ số nhị phân cuối cùng của Rj và chữ số 
nhị phân cuối cùng của sj, vì giá trị luỹ thừa của (-1) chỉ phụ thuộc vào tính chẵn lẻ 
của số mũ. Nh− vậy, khi đã có Rj, sj, ta chỉ cần O(log2b) để xác định 
a
b



 . Hệ quả 
đ−ợc chứng minh. 
Ta có thuật toán sau đây để tính kí hiệu Jacobi dựa vào các định lí vừa chứng minh. 
Thuật toán tính kí hiệu Jacobi 
a
b



 (và do đó, tính kí hiệu Legendre khi b là 
số nguyên tố). 
J1. (Kiểm tra b≠ 0). Nếu b=0, in ra 0 nếu |a|≠ 1, in ra 1 
nếu |a|=1 và kết thúc thuật toán. 
J2. (Tách các luỹ thừa của 2 khỏi b). Nếu a và b đều 
chẵn, in ra 0 và kết thúc thuật toán. Ng−ợc lại, đặt 
v←0, và khi b chẵn, đặt v←v+1, b←b/2. Sau đó, nếu v 
chẵn, đặt k←1, ng−ợc lại, đặt k←(-1)(a 2 -1)/8. Cuối cùng, 
nếu b<0, đặt b←-b, và nếu hơn nữa, a<0, đặt k←-k. 
J3. (Kết thúc?). (ở b−ớc này, ta có b lẻ và b>0). Nếu 
a=0, in ra 0 nếu b>1, in ra k nếu b=1 và kết thuật 
toán. Ng−ợc lại, đặt v←0 và nếu a chẵn, đặt v←v+1, 
a←a/2. Nếu v lẻ, đặt k← (-1) (b2 −1 8)/ k . 
J4. (Sử dụng luật thuận nghịch). Đặt k←(-1)(a-1)(b-1)/4k. 
 71
Nhận xét. ở đây, ta cần l−u ý một điều. Mặc dù trong thuật toán có xuất hiện các 
phép chia (a2-1)/8, (b2-1)/8, (a-1)(b-1)/4, và phép nâng (-1) lên luỹ thừa đó, ta 
không cần làm các phép chia cũng nh− nâng lên luỹ thừa, vì đòi hỏi quá nhiều phép 
tính bit. Vì giá trị luỹ thừa của (-1) chỉ phụ thuộc vào tính chẵn lẻ của các đại l−ợng 
trên, nên chẳng hạn đối với (-1)(a
2
-1)/8, giá trị đó chỉ phụ thuộc a mod 8 và bằng 
một trong những số của dãy sau đây: 
{0,1,0,-1,0,-1,0,1}. 
Thuật toán tính căn bậc 2 modulo p. 
Trong nhiều ứng dụng (chẳng hạn, xem Ch−ơng 7), ta cần phải tính căn bậc 2 
modulo p, khi biết nó tồn tại. Tất nhiên, một trong các ph−ơng pháp để giải ph−ơng 
trình đồng d− x2≡ a(mod p), (a,p)=1 là kiểm tra tất cả các số từ 1 đến p-1. Tuy 
nhiên, khi làm việc với p lớn, ph−ơng pháp này không thể áp dụng đ−ợc (thời gian 
đòi hỏi là O(p)). 
Với những số nguyên tố dạng p≡ 3(mod 4), bài toán khá đơn giản. Ta có: 
x≡ a(p+1)/4(mod p). 
Thật vậy, 
x≡ a(p+1)/2≡ a.a(p-1)/2 ≡ a(mod p) . 
Khi p /≡ 3(mod 4), ta có p≡ 1(mod 8) hoặc p≡ 5(mod 8). Trong tr−ờng hợp 
p≡ 5(mod 8), lời giải cũng có thể tìm đ−ợc không khó khăn. Thật vậy, ta có: 
a(p-1)/2≡ 1(mod p), 
do đó 
a(p-1)/4≡ ± 1(mod p). 
Dễ kiểm tra đ−ợc rằng, trong tr−ờng hợp đồng d− thoả mãn với dấu cộng, nghiệm 
phải tìm là 
x=a(p+3)/8(mod p). 
Nếu đồng d− thoả mãn với dấu trừ, dùng định lí 4.8 ta có: 
a(p-1)/2≡ -1(mod p). 
Từ đó nghiệm phải tìm là: 
x=2a.(4a)(p-5)/8(mod p). 
Nh− vậy chỉ còn phải xét tr−ờng hợp p≡ 1(mod 8). Cho đến nay, mới chỉ có một 
thuật toán (thuật toán Shoof sử dụng đ−ờng cong elliptic) với thời gian đa thức. Tuy 
nhiên, trong thực tế, thuật toán đó rất khó sử dụng. Sau đây chúng ta tìm hiểu thuật 
toán xác suất của Tonelli và Shanks. 
Thuật toán Tonelli-Shanks chính là một mở rộng tự nhiên của các tr−ờng hợp riêng 
đã xét trên đây. 
 72
Ta luôn luôn viết p-1=2e.q, với q lẻ. 
Nếu ta tìm đ−ợc phần tử z và số nguyên chẵn k sao cho 
aqzk ≡ 1(mod p) 
thì nghiệm cần tìm sẽ đ−ợc cho bởi 
x=a(q+1)/2zk/2. 
Ta sẽ tìm phần tử z d−ới dạng z=nq. 
Ta chỉ ra rằng, phần tử z nh− vậy thoả mãn điều kiện đặt ra khi và chỉ khi n là một 
không thặng d− bình ph−ơng modulo p. Ta có: 
(aq)2
e
=a pφ ( )−1 ≡ 1(mod p), 
do đó aq thuộc vào nhóm G các phần tử cấp là một −ớc số của 2e. Nh− vậy, để tồn 
tại k, chỉ cần chọn n là phần tử sinh của nhóm G (khi đó, do a là một không thặng 
d− bình ph−ơng nên số mũ k phải là chẵn). Số nguyên n sẽ là một phần tử sinh của 
G khi và chỉ khi n, n2, n4,...,n2
e
(≡ 1(mod p)) không đồng d− với nhau modulo p. Dễ 
thấy rằng, điều đó xảy ra khi và chỉ khi n là một không thặng d− bình ph−ơng 
modulo p. 
Để xây dựng thuật toán, ta cần giải quyết hai vấn đề: Tìm phần tử z, và tìm số mũ k. 
Phần thứ nhất đ−ợc giải quyết bằng thuật toán xác suất. Ta chọn ngẫu nhiên một số 
n, và tính kí hiệu Legendre 
n
p



 . Khi đó, nếu 
n
p



=-1, ta đặt z=n
q. Trong tr−ờng 
hợp ng−ợc lại, ta tiếp tục làm nh− trên với một số ngẫu nhiên khác cho đến khi tìm 
đ−ợc một số n thích hợp. Vì số các thặng d− bình ph−ơng bằng (p-1)/2 nên mỗi lần 
chọn ngẫu nhiên một số n, xác suất để có 
n
p



=-1 là 1/2. 
Trong thực tế, ta có thể tìm ra một không thặng d− bình ph−ơng rất nhanh. Chẳng 
hạn, xác suất hai m−ơi lần thất bại liên tiếp nhỏ hơn 10-6. 
Số mũ k khó tìm hơn. Thật ra, ta không cần biết số mũ k, mà cần biết a(q+1)/2zk/2. 
Thuật toán. Giả sử p là một số nguyên tố lẻ, n∈Z. Ta viết 
p-1=2e.q với q lẻ. 
1. (Tìm phần tử sinh). Chọn ngẫu nhiên số n cho đến 
khi thoả mãn
n
p



=-1. Sau đó đặt z←n
q(mod p). 
2. (Xuất phát). Đặt y←z, r←e, x←a(p-1)/2(mod p), 
b←ax2(mod p ), x←ax(mod p). 
3. (Tìm số mũ). Nếu b≡ 1(mod p) in ra x và kết thúc 
thuật toán, Trong tr−ờng hợp ng−ợc lại, tìm số m nhỏ 
nhất sao cho m≥1, b m2 ≡ 1(mod p). Nếu m=r, in ra thông 
 73
báo nói rằng a không phải là thặng d− bình ph−ơng 
modulo p. 
4. (Thu hẹp số mũ). Đặt t← y r m2 1− − , y←t2, r←m, x←xt, 
b←by (mọi phép tính đều modulo p)và chuyển sang b−ớc 
3. 
Chú ý rằng từ khi bắt đầu b−ớc 3, ta luôn luôn có các đồng d− modulo p: 
ax≡ x2, y r2 1− ≡ -1, b r2 1− ≡ 1. 
Từ đó suy ra rằng, nếu nhóm con Gr các phần tử cấp là một −ớc của 2r, thì y là phần 
tử sinh của nhóm Gr, b ∈ Gr-1, tức là b chính ph−ơng trong Gr. Vì r thực sự giảm tại 
mỗi b−ớc lặp của thuật toán, nên số b−ớc lặp nhiều nhất bằng e. Khi r ≤1, ta có 
b=1, thuật toán kết thúc, và x là một căn bậc 2 của a mod p. 
Có thể thấy rằng, trung bình, b−ớc 3 và b−ớc 4 đòi h