Vietebooks Nguyễn Hoàng Cương
Trang 1
Ch−¬ng 4
KiÓm tra tÝnh nguyªn tè x¸c suÊt
§Ó thiÕt lËp hÖ mËt RSA, ta ph¶i t¹o ra c¸c sè nguyªn tè ngÉu
nhiªn lín (ch¼ng h¹n cã 80 ch÷ sè). Trong thùc tÕ, ph−¬ng c¸ch thùc
hiÖn ®iÒu nµy lµ: tr−íc hÕt ph¶i t¹o ra c¸c sè ngÈu nhiªn lín, sau ®ã
kiÓm tra tÝnh nguyªn thuû cña chóng b»ng c¸ch dïng thuËt to¸n x¸c
suÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh− thuËt to¸n
Miller- Rabin hoÆc lµ thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸n
trªn ®Òu ®−îc tr×nh bµy trong phÇn nµy. Chóng lµ c¸c thuËt to¸n
nhanh (tøc lµ mét sè nguyªn n ®−îc kiÓm tra trong thêi ®a thøc theo
log2n, lµ sè c¸c bÝt trong biÓu diÖn nhÞ ph©n cña n). Tuy nhiªn, vÉn cã
kh¶ n¨ng lµ thuËn to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ n
lµ hîp lÖ sè. Bëi vËy, b»ng c¸ch thay ®æi thuËt to¸n nhiÒu lÇn, cã thÓ
gi¶m x¸c suÊt sai sè d−íi mét møc ng−ìng cho phÐp (sau nµy sÏ th¶o
luËn kü h¬n mét chót vÒ vÊn ®Ò nµy).
Mét vÊn ®Ò quan träng kh¸c: lµ cÇn ph¶i kiÓm tra bao nhiªu sè
nguyªn ngÉu nhiªn (víi kÝch th−¬c x¸c ®Þnh)cho tíi khi t×m ®−îc mét
sè nguyªn tè. Mét kÕt qu¶ nçi tiÕng trong lý thuyÕt sè (®−îc gäi lµ
®Þnh lý sè nguyªn tè) ph¸t biÓu r»ng: sè c¸c sè nguyªn tè kh«ng lín
h¬n N xÊp xØ b»ng N/ln N. Bëi vËy, nÕu p ®−îc chän ngÉu nhiªn th×
x¸c suÊt p lµ mét sè nguyªn tè sÏ vµo kho¶ng 1/ln p. Víi mét mo®un
512 bÝt, ta cã 1/ln p ≈ 1/77. §iÒu nµy cã nghÜa lµ tÝnh trung b×nh, c−
177 sè nguyªn ngÉu nhiªn p víi kÝch th−íc t−¬ng øng sÏ cã mét sè lµ
sè nguyªn tè. DÜ nhiªn, nÕu chÜ h¹n chÕ xÐt c¸c sè nguyªn lÎ th× x¸c
suÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, hoµn
toµn cã kh¶ n¨ng t¹o ®−îc c¸c nguyªn tè ®ñ lín vµ do ®ã vÒ mÆt thùc
thÓ ta cã thÓ thiÕt lËp ®−îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xem
xÐt ®iÒu nµy ®−îc thùc hiªn nh− thÕ nµo.
Mét bµi to¸n quyÕt ®Þnh lµ mét bµi to¸n to¸n trong ®ã mét c©u hái
cÇn ®−îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt lµ mét
thuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ng−îc l¹i, thuËt to¸n
kh«ng sö dông c¸c sè ngÉu nhiªn sÏ ®−îc gäi lµ mét thuËt to¸n tÊt
®Þnh). C¸c ®Þnh nghÜa sau cã liªn quan tíi c¸c thuËt to¸n x¸c suÊt cho
c¸c bµi to¸n quyÕt ®Þnh.
§Þnh nghÜa 4.1
ThuËt to¸n Monte Carlo ®Þnh h−íng “cã” lµ mét thuËt to¸n x¸c
suÊt cho mét bµi to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«n
lµ ®óng cßn c©u tr¶ lêi “kh«ng” cã thÓ lµ sai. ThuËt to¸n Monte Carlo
®Þnh h−íng “kh«ng“ còng ®−îc ®Þnh nghÜa theo c¸ch t−¬ng tù.
Vietebooks Nguyễn Hoàng Cương
Trang 2
Chóng ta nãi r»ng, mét thuËt to¸n Monte Carlo ®Þnh h−íng “cã” cã
x¸c suÊt sai b»ng ε nÕu víi bÊt kú mæt tr−êng hîp nµo mµ c©u tr¶ lêi
lµ “cã” th× thuËt to¸n cã c©u tr¶ lêi sai “kh«ng” víi x¸c suÊt kh«ng
lín h¬n ε (x¸c suÊt nµy ®−îc tÝnh trªn mäi phÐp chon ngÉu nhiªn, cã
thÓ thùc hiªn bëi thuËt to¸n víi mét c©u vµo ®· cho).
Bµi to¸n quyÕt ®Þnh ë ®©y lµ bµi to¸n hîp lÖ sè m« t¶ ë h×nh
4.5.
CÇn chó ý r»ng mét thuËt to¸n quyÕt ®Þnh chØ cã c©u tr¶ lêi “cã” hoÆc
“kh«ng” ®Æc biÖt trong bµi to¸n hîp lÖ sè lµ ta kh«ng yªu cÇu thuËt
to¸n tÝnh tÝch thõa sè khi n lµ hîp lÖ sè.
Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµ
mét thuËt to¸n Monte- Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè cã
Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµ mét
thuËt to¸n Monte-Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè vµ x¸c
xuÊt sai 1/2. Bëi vËy, nÕu thuËt to¸n tr¶ lêi “cã” th× n lµ hîp sè;
ng−îc l¹i nÕu n lµ hîp sè th× thuËt to¸n tr¶ lêi “cã” víi x¸c xuÊt tèi
thiÓu 1/2.
H×nh 4.5. Bµi to¸n hîp sè.
H×nh 4.6. Bµi to¸n vÒ c¸c thÆng d− bËc hai.
MÆc dï thuËt to¸n Miller-Rabin (ta sÏ xÐt sau) nhanh h¬n
thuËt to¸n Soloway-Strasson (S-S) nh−ng ta sÏ xÐt thuËt to¸n S-S
tr−íc v× nã dÔ hiÓu h¬n vÒ kh¸i niÖm, ®ång thêi l¹i liªn quan tíi mét
sè vÊn ®Ò cña lý thuyÕt sè (mµ ta sÏ cßn dïng trong c¸c ch−¬ng tr×nh
sau). Ta sÏ x©y dùng mét sè nÒn t¶ng s©u s¾c h¬n trong lý thuyÕt sè
tr−íc khi m« t¶ thuËt to¸n.
§Æc tr−ng cña bµi to¸n: mét sè nguyªn d−¬ng n ≥ 2
C©u hái: n cã ph¶i lµ hîp sè kh«ng ?
§Æc tr−ng cña bµi to¸n: cho p lµ mét sè nguyªn tè lÎ vµ
mét sè nguyªn x sao cho 0 ≤ x ≤ p-1
C©u hái: x cã ph¶i lµ thÆng d− bËc hai phÐp modulo p ?
Vietebooks Nguyễn Hoàng Cương
Trang 3
§Þnh nghÜa 4.2.
Gi¶ sö p lµ mét sè nguyªn tè lÎ vµ x lµ mét sè nguyªn, 1 ≤ x ≤
p-1. x ®−îc gäi lµ thÆng d− bËc hai theo modulo p nÕu ph−¬ng tr×nh
®ång d− y2 ≡ x (modulo p) cã mét nghiÖm y∈Zp x ®−îc gäi lµ thÆng
d− kh«ng bËc hai theo modulo p nÕu x ??? 0 (mod p) vµ x kh«ng ph¶i
lµ thÆng d− bËc hai theo modulo p.
VÝ dô 4.6.
C¸c thÆng d− bËc hai theo modulo 11 lµ 1,3,4,5 vµ 9. CÇn ®Ó ý r»ng,
(±1)2=1, (±5)2=3, (±2)2=4, (±4)2=5, (±3)2=9 (ë ®©y tÊt c¶ c¸c phÐp sè
häc ®Òu thùc hiÖn trong Z11).
Bµi to¸n quyÕt ®Þnh thÆng d− bËc hai ®−îc tr×nh bµy trªn h×nh
4.6 sÏ ®−îc thÊy mét c¸ch t−¬nngf minh nh− sau:
Tr−íc hÕt, ta sÏ chøng minh mét kÕt qu¶- tiªu chuÈn Euler –
t¹o nªn thuËt to¸n tÊt ®Þnh theo thêi gian ®a thøc cho bµi to¸n vÒ c¸c
thÆng d− bËc hai.
§Þnh lý 4.8. (Tiªu chuÈn Euler)
Gi¶ sö p lµ mét sè nguyªn tè, khi ®ã x lµ mét thÆng d− bËc hai
theo modulo p khi vµ chØ khi:
x
(p-1)/2 ≡1 (mod p)
Chøng minh:
Tr−íc hÕt gi¶ sö r»ng, x≡y2(mod p). Theo hÖ qu¶ 4.6, nÕu p lµ
sè nguyªn tè th× xp-1≡1 (mod p) víi mäi x ≡ 0 (mod p). Bëi vËy ta cã :
x
(p-1)/2 ≡ (y2)(p-1)/2 (mod p)
≡yp-1(mod p)
≡1 (mod p)
Ng−îc l¹i, gi¶ sö r»ng x(p-1)/2≡1 (mod p). Cho p lµ mét phÇn tö
nguyªn thuû theo modulo p. Khi ®ã x≡bi (mod p) víi gi¸ trÞ i nµo ®ã.
Ta cã
x(p-1)/2 ≡ (bi)(p-1)/2 (mod p)
≡bi(p-1)/2(mod p)
V× p cã bËc b»ng p-1 nªn p-1 ph¶i lµ −íc cña i(p-1)/2. Bëi vËy i lµ sè
ch½n vµ nh− vËy c¨n bËc hai cña x lµ ±bi/2.
Vietebooks Nguyễn Hoàng Cương
Trang 4
§Þnh lý 4.8 sÏ dÉn tíi mét thuËt to¸n thêi gian ®a thøc cho c¸c
thÆng d− bËc hai nhê sö dông kü thuËt “b×nh ph−¬ng vµ nh©n” cho
phÐp lÊy luü thõa theo modulo p. §é phøc t¹p cña thuËt to¸n kho¶ng
O((log p)3).
Sau ®©y tiÕp tôc ®−a ra mét sè ®Þnh nghÜa tõ lý thuyÕt sè:
§Þnh nghÜa 4.3.
Gi¶ sö p lµ sè nguyªn tè lÎ. Víi mét sè nguyªn tè bÊt kú a ≥0,
ta
®Þnh nghÜa ký hiÖu Legendre nh− sau:
0 nÕu a ≡ 0 (mod p)
= 1 nÕu lµ th¨ng d− bËc hai theo modulo p
-1 nÕu lµ th¨ng d− kh«ng bËc hai theo
modulo p
Ta ®· biÕt lµ a(p-1)/2≡ 1 (mod p) khi vµ chØ khi a lµ mét thÆng d−
bËc hai theo modulo p. NÕu a lµ béi cña p th× râ rµng a(p-1)/2≡ 0(mod
p). Cuèi cïng, nÕu a lµ mét thÆng d− kh«ng bËc hai theo modulo p th×
a(p-1)≡ -1 (mod p) v× ap-1≡1(mod p). Bëi vËy, ta cã kÕt qu¶ cho phÐp
x©y dùng mét thuËt to¸n h÷u hiÖu ®Ó ®¸nh gi¸ c¸c ký hiÖu Legendre
nh− sau
§Þnh Lý 4.9.
Gi¶ sö p lµ mét sè nguyªn tè. Khi ®ã ≡ a(p-1)/2 (mod p).
Sau ®©y lµ mét ®Þnh nghÜa tæng qu¸t ho¸ cho ký hiÖu
Legendre.
§Þnh nghÜa 4.4.
Gi¶ sö n lµ mét sè nguyªn d−¬ng lÎ vµ ph©n tÝch theo c¸c luü
thõa nguyªn tè cña n lµ p1e1 ....... pKek . Gi¶ sö a ≥ 0 lµ mét sè nguyªn.
Ký hiÖu
Jacobi ®−îc ®Þnh nghÜa nh− sau:
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
p
a
⎟
⎠
⎞
⎜
⎝
⎛
r
a
Vietebooks Nguyễn Hoàng Cương
Trang 5
VÝ dô 4.7.
XÐt ký hiÖu Jacobi . Ph©n tÝch luü thõa nguyªn tè cña
9975 lµ: 9975=3 x 52 x 7 x 19. Bëi vËy ta cã:
=
=(-1)(-1)2(-1)(-1)
= -1.
Gi¶ sö n > 1 lµ mét sè lÎ. NÕu n lµ mét sè nguyªn tè th×
≡
a(n-1)/2 (mod n) víi a bÊt kú. MÆt kh¸c nÕu n lµ mét hîp sè th× ®ång d−
thøc trªn cã thÓ ®óng hoÆc kh«ng. NÕu ph−¬ng tr×nh ®ã vÉn ®óng th×
a ®−îc gäi
lµ sè gi¶ nguyªn tè Euler theo c¬ sè n. VÝ dô: 10 lµ sè gi¶ nguyªn tè
Euler
theo c¬ sè 91 v× :
= -1 = 1045 mod 91
Tuy nhiªn cã thÓ chøng tá r»ng, víi mét hîp sè lÎ n bÊt kú, sÏ
cãp nhiÒu nhÊt mét nöa c¸c sè nguyªn a (sao cho 1 ≤ a ≤ n-1) lµ c¸c
sè gi¶ nguyªn tè Euler c¬ sè n (xem c¸c bµi tËp). §iÒu ®ã chøng tá
r»ng, viÖc kiÓm tra tÝnh nguyªn tè theo thuËt to¸n Soloway-Strasson
ei
K
1i i
p
a
n
a∏
=⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
9975
6278
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
=
⎟
⎠
⎞
⎜
⎝
⎛
19
6278
7
6278
5
6278
3
6278
9975
6278 2
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
⎟
⎠
⎞
⎜
⎝
⎛
19
8
7
6
5
3
3
22
⎟
⎠
⎞
⎜
⎝
⎛
91
10
⎟
⎠
⎞
⎜
⎝
⎛
n
a