Kiểm tra tính nguyên tố xác suất

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ù. 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) nhng 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.

§Þ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

§Æc trng 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 trng 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 ?