Chơng 4

Hệ mật RSA và vấn đề phân tích thừa số
4.1. Giới thiệu về hệ mật khoá công khai
Trong mô hình mật m cổ điển trớc đây mà hiện nay đang đợc nghiên
cứu Alice (ngời gửi) và Bob (ngời nhận) chọn một cách bí mật khoá K. Sau
đó dùng K để tạo luật m hoá ekvà luật giải m dk. Trong hệ mật này dk hoặc
giống nh ek hoặc dễ dàng nhận đợc từ nó (ví dụ trong hệ DES quá trình giải
m hoàn toàn tơng tự nh quá trình m nhng thủ tục khoá ngợc lại). Các
hệ mật thuộc loại này đợc gọi là hệ mật khoá bí mật, nếu để lộ ek thì làm cho
hệ thống mất an toàn.
Nhợc điểm của hệ mật này là nó yêu cầu phải có thông tin trớc về
khoá K giữa Alice và Bob qua một kênh an toàn trớc khi gửi một bản m bất
kỳ. Trên thực tế điều này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách
xa nhau và họ chỉ có thể liên lạc với nhau bằng th tín điện tử (Email). Trong
tình huống đó Alice và Bob không thể tạo một kênh bảo mật với giá phải
chăng.
ý tởng xây dựng một hệ mật khoá công khai (hay khoá dùng chung) là
tìm một hệ mật không có khả năng tính toán để xác định dkkhi biết ek. Nếu
thực hiện đợc nh vậy thì quy tắc m ek có thể đợc công khai bằng cách
công bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khoá công
khai). Ưu điểm của hệ mật khoá công khai là ở chỗ Alice (hoặc bất kì một ai)
có thể gửi một bản tin đ m cho Bob (mà không cần thông tin trớc về khoá
mật) bằng cách dïng luËt m c«ng khai ek. Ng−êi nhËn A sÏ là ngời duy nhất
có thể giải đợc bản m này bằng cách sử dụng luật giải m bí mật dk của
mình.
Có thể hình dung hệ mật này tơng tự nh sau. Alice đặt một vật vào
một hộp kim loại và rồi khoá nó lại bằng một khoá số do Bob để lại. Chỉ có
Bob là ngời duy nhất có thể mở đợc hộp vì chỉ có anh ta mới biết tổ hợp m
của khoá số của mình.

ý tởng về một hệ mật khoá công khai đ đựoc Diffie và Hellman đa
ra vào năm 1976. Còn việc hiện thực hoá nó thì do Rivesrt, Shamir và
Adleman đa ra đầu tiên vào năm 1977, họ đ tạo nên hệ mật nổi tiếng RSA
(sẽ đợc nghiên cứu trong chơng này). Kể từ đó một số hệ đợc công bố, độ
mật của chúng dựa trên các bài toán tính toán khác nhau. Sau đây là các hệ
mật khoá công khai quan trọng :
+ Hệ mật RSA:
Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số
nguyên tố các số nguyên lớn. Hệ này sẽ đợc mô tả trong phần 4.3.
+ Hệ mật xếp ba lô Merkle - Hellman:
Hệ này và các hệ liên quan dựa trên tính khó giải của bài toán tổng các
tập con (bài toán này là bài toán NP đầy đủ là một lớp khá lớn các bài toán
không có thuật giải đợc biết trong thời gian đa thức). Tuy nhiên tất cả các hệ
mật xếp ba lô khác nhau đều đ bị chứng tỏ là không mật (ngoại trừ hệ mật
Chor Rivest sẽ đợc nêu dới đây). Hệ mật này đợc xét ở chơng 5.
+ Hệ mật McEliece:
Hệ này dựa trên lý thuyết m đại số và vẫn còn đợc coi là an toàn. Hệ
mật McEliece dựa trên bài toán giải m cho các m tuyến tính (cũng là một bài
toán NP đầy đủ). Hệ mật McEliece đợc trình bày ở chơng 5.
+ Hệ mật Elgamal:
Hệ mật Elgamal dựa trên tính khó giải của bài toán logarithm rời rạc
trên các trờng hữu hạn (xem trong chơng 5).
+ Hệ mật Chor - Rivest:
Hệ mật Chor - Rivest cũng đợc xem nh một loại hệ mật xếp ba lô.
Tuy nhiên nó vẫn đợc coi là an toàn.
+ Hệ mật trên các đờng cong Elliptic
Các hệ mật này là biến tớng cảu các hệ mật khác (chẳng hạn nh hệ
mật Elgamal) , chúng làm việc trên các đờng cong Elliptic chứ không phải là
trên các trờng hữu hạn. Hệ mật này đảm bảo độ mật với khoá số nhỏ hơn các

hệ mật khoá công khai khác (xem chơng 5).
Một chú ý quan trọng là một hệ mật khoá công khai không bao giờ có
thể đảm bảo đợc độ mật tuyệt đối (an toàn vô điều kiện). Sở dĩ nh vậy vì đối
phơng khi nghiên cứu một bản m y có thể m lần lợt các bản rõ bằng luật
m công khai ek cho tới khi anh ta tìm đợc bản rõ duy nhất x đảm bảo y = ek


(x). Bản rõ này chính là kết quả giải m của y. Bởi vậy ta chỉ nghiên cứu độ
mật về mặt tính toán của các hệ mật này.
Một khái niệm có ích khi nghiên cứu hệ mật khoá công khai là khái
niệm về hàm cửa sập một chiều. Ta định nghĩa khái niệm này một cách không
hình thức.
Hàm m khoá công khai ek của Bob phải là một hàm dễ tính toán. Song
việc tìm hàm ngợc (hàm giải m ) phải rất khó khăn (đối với bất kỳ ai không
phải là Bob). Đặc tính dễ tính toán nhng khó tính toán hàm ngợc thờng
đợc gọi là đặc tính một chiều. Bởi vậy điều kiện cân thiết là ek phải là hàm
một chiều.
Các hàm một chiều đóng vai trò quan trọng trong mËt m häc: chóng rÊt
quan trong c¸c hƯ mËt khoá công khai và trong nhiều lĩnh vực khác. Đáng tiếc
là mặc dù có rts nhiều hàm đợc coi là hàm một chiều nhng cho tới nay vẫn
không tồn tại một hàm nào có thể chứng minh đợc là hàm một chiều.
Sau đây là một ví dụ về một hàm đợc coi là hàm một chiều. Giả sử n là
tích của hai số nguyên tố lớn p và q, giả sử b là một số nguyên dơng. Khi đó
ta xác định ánh xạ f : Zn Zn là
f(x) = xb mod n
(với b và n đ đợc chọn thích hợp thì đây chính là hàm m RSA, sau này sẽ
còn nói nhiều về nó).
Để xây dựng một hệ mật khoá công khai thì việc tìm đợc một hàm một
chiều vẫn cha đủ. Ta không muốn ek là hàm một chiều đối với Bob vì anh ta
phải có khả năng giải m các bản tin nhận đợc một cách hiệu quả. Điều cần

thiết là Bob phải có một cửa sập chứa thông tin bí mật cho phép dễ dàng tìm
hàm ngợc cđa ek. Nh− vËy Bob cã thĨ gi¶i m mét cách hữu hiệu vì anh ta có
một hiểu biết tuyệt mật nào đó về K. Bởi vậy một hàm đợc gäi lµ cưa sËp mét
chiỊu nÕu nã lµ hµm mét chiều và nó trở nên dễ tính ngợc nếu biết một cửa
sập mhất định.
Ta sẽ xét cách tìm một cửa sập đối với hàm f nêu ở trên trong phần 4.3.
Các tìm này sẽ dẫn đến hệ mật RSA.


4.2. một số vấn đề sâu hơn về lý thuyết số
Trớc khi mô tả hệ mật RSA làm việc ra sao cần phải xem xét một số
yếu tố liên quan ®Õn lý thuyÕt sè vµ sè häc modulo. Hai kÕt quả cần biết là
thuật toán Euclide và định lý phần d China.
4.2.1 Thuật toán Euclide
Trong chơng 1 đ xét Zn là một vành với số nguyên dơng bất kỳ n. Ta
cũng đ chứng tỏ rằng phần tử b Zn có phần tử nghịch đảo (phần tử ngợc
của phép nhân) khi và chỉ khi CLN(b,n) = 1 và các số nguyên dơng nhỏ hơn
n và nguyên tố cùng nhau với n bằng (n).
Tập các thặng d theo modulo n và nguyên tố cùng nhau với n đợc ký
hiệu là Zn* .Không khó khăn có thể thấy rằng Zn* sẽ tạo nên một nhóm Abel
đối với phép nhân. Ta cũng biết rằng, phép nhân theo modulo n là giao hoán và
kết hợp và phần tử đơn vị là 1. Một phần tử bất kỳ trong Zn*đều có nghịch đảo
bội (cũng nằm trong Zn*). Cuối cùng Zn* là đóng đối với phép nhân vì xy là
nguyên tố cùng nhau với n khi x và y nguyên tố cùng nhau với n. (H y chứng
minh điều này!)
Cho tới bây giờ ta chỉ biết rằng một phần tử b bất kì Zn* đều có nghịch
đảo b-1 song việc tính nó vẫn cha nói đến. Một thuật toán nh vậy đợc gọi là
thuật toán Euclide mở rộng.
Trớc tiên ta sẽ mô tả thuật toán Euclide, thông thờng thuật toán này
đợc dùng để tính −íc sè chung lín nhÊt (−CLN) cđa hai sè nguyªn dơng r0

và r1 với r0 > r1.Thuật toán Euclide bao gåm viƯc thùc hiƯn c¸c phÐp to¸n nh−
sau:
r0 = q1 r1 +r2
r1 = q2 r2 +r3
.
.
rm -2 = qm -1 rm -1 +rm
rm -1 = qm rm

0 < r2 < r1
0 < r3 < r2
0 < rm -1 < rm

Khi đó dễ dàng chứng tỏ đợc rằng
CLN(r0 , r1 ) = −CLN(r1 , r2 ) = . . . −CLN(rm-1 , rm ) = rm


Bởi vậy

CLN(r0 , r1 ) = rm

Vì thuật toán Euclide tính các CLN nên có thể áp dụng nó để xác định
xem liệu một số nguyên dơng b < n có nghịch đảo theo modulo n không bằng
cách bắt đầu với r0 = n và r1 = b. Tuy nhiên thuật toán này không cho phép tính
giá trị của phần tử nghịch đảo (nếu nó tồn tại).
Bây giờ giả sử ®Þnh nghÜa mét d y sè t0 , t1 ,.... ,tm theo các công thức
truy toán sau (trong đó các giá trị qj đ đợc xác định ở trên)
t0 = 0
t1 = 1
tj = tj-2- qj-1 tj-1 mod r0 nÕu j 2

Ta có kết quả quan trọng sau
Định lý 4.1.
Víi 0 ≤ j ≤ m, ta cã rj ≡ tjr1 (mod r0), trong đó các giá trị qj và rj đợc
xác định theo thuật toán Euclide còn các giá trị tj đợc xác định theo công
thức truy toán ở trên.
Chứng minh:
Ta chứng minh bằng cách quy nạp theo j. Định lý hiển nhiên đúng với j
= 0 và j = 1. Giả sử định lý cũng đúng với j = i-1 và j = i-2, trong đó i 2; sau
đây ta sẽ chứng tỏ định lý đúng với j = i. Theo quy nạp ta có
và
Bây giờ ta tÝnh

ri-2 ≡ ti-2 r1 (mod r0)
ri-1 ≡ ti-1 r1 (mod r0)
ri = ri-2 - qi-1 ri-1
≡ ti-2 r1 - qi-1 ti-1 r1 (mod r0)
≡ (ti-2 - qi-1 ti-1)r1 (mod r0)
≡ ti r1 (mod r0)

Bởi vậy theo quy nạp định lý là đúng.
Hệ quả rút ra trực tiếp từ định lý trên.
Hệ quả 4.2:


Giả sử CLN (r0,r1) = 1, khi đó tm = r1-1 mod r0.
Hìn 2.1 Thuật toán Euclide mở rộng:
1.
2.
3.
4.

5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

n0 = n
b0 = b
t0 = 0
t=1
q = n0 /b0
r = n0 - q×b0
While r > 0 do
temp = t0 -q×t
if temp ≥ 0 then temp = temp mod n
if temp < 0 then temp = n - ((- temp) mod n)
t0 = t
t = temp
n0 = b 0
b0 = r
q = n0 /b0
r = n0 - q×b0

if b0 ≠ 1 then b không có nghịch đảo theo
modulo n
-1
else b = t mod n .

XÐt thÊy d y c¸c sè t0, t1, . . . , tm có thể đợc tính toán trong thuật toán
Euclide đồng thời nh các giá trị qj và rj. Hình 4.1 trình bày thuật toán Euclide
mở rộng để tính nghịch đảo của b theo modulo n (nếu nó tồn tại). Trong thuật
toán này không phải dùng mảng (array) để ghi các giá trị qj, rj và tj vì chỉ cần
nhớ hai giá trị cuối cùng trong mỗi d y này ở một điểm bất kì trong thuật toán.
Trong bớc 10 của thuật toán ta đ viết biểu thức cho biến temp theo
cách để phép rút gọn theo modulo n đợc thực hiện đối với số dơng. (Trớc
đây ® biÕt r»ng viƯc rót gän theo modulo cđa c¸c số âm sẽ dẫn đến các kết
quả âm ở nhiêù ngôn ngữ máy tính; còn ở đây ta muốn kết thúc với kết quả
dơng). ở bớc 12 luôn có tb r (mod n) (kết quả này đ đợc chứng minh ở
định lý 4.1).


Sau đây là một ví dụ nhỏ để minh hoạ
Ví dụ 4.1.
Giả sử ta cần tính 28-1 mod 75. Thuật toán Euclide mở rộng thực hiện
nh sau:
75 = 2 ì 28 +29
73 × 28 mod 75 = 19
28 = 1 × 19 + 9
3 × 28 mod 75 = 9
19 = 2 × 9 + 1
67 × 28 mod 75 = 1
9=9×1


b−íc 6
b−íc 12
b−íc 16
b−íc 12
b−íc 16
b−íc 12
b−íc 16

V× thÕ 28-1 mod 75 = 67.
4.2.2. Định lý phần d China
Định lý này thực sự là một phơng pháp giải các hệ phơng trình
đồng d. Giả sử m1, . . . , mr là các số nguyên tố cùng nhau từng đôi một (tức
CLN(mi,mj)=1 nếu ji). Giả sử a1,. . ., ar là các số nguyên xét hệ phơng trình
đồng d sau:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
.
.
x ≡ ar (mod mr)
Định lý phần d China khẳng định rằng hệ này có nghiệm duy nhất
theo modulo M = m1ìm2ì. . . ìmr. Ta sẽ chứng minh kết quả đó trong phần
này và cũng mô tả một thuật toán hữu hiệu để giải hệ đồng d thức dạng trên.
Để thuận tiện, xét hàm : ZM
nghĩa nh sau:

Zm1ì . . .ìZmr. Hàm này đợc định

(x) = (x mod m1, . . . , x mod mr )



VÝ dơ 4.2
Gi¶ sư r = 2, m1 = 5 vµ m2 = 3, bëi vËy M = 15. Khi đó hàm có giá trị
sau
(0) = (0,0)
(3) = (3,0)
(6) = (1,0)
π(9) = (4,0)
π(12) =(2,0)

π(1) = (1,1)
π(4) = (4,1)
π(7) = (2,1)
π(10) =(0,1)
π(13) =(3,1)

π(2) = (2,2)
π(5) = (0,2)
π(8) = (3,2)
π(11) =(1,2)
π(14) =(4,2)

Việc chứng minh định lý phần d China tơng đơng với việc chứng
minh rằng hàm là một song ánh. Điều này có thể dễ dàng thấy đợc ở ví dụ
4.2. Trong thực tế có thể đa ra một công thức tờng minh tổng quát cho hàm
ngợc -1.
Với 1 i r, định nghĩa:
Mi = M/mi
Khi đó, dễ dàng thÊy r»ng
−CLN(Mi,mi) = 1
víi 1 ≤ i ≤ r. TiÕp theo, với 1 i r, định nghĩa

yi = Mi-1 mod mi
(phần tử nghịch đảo này tồn tại do CLN(Mi,mi) = 1 và có thể tìm đợc bằng
thuật toán Euclide). Cần để ý rằng
Miyi 1 (mod mi)
với 1 i r.
Bây giờ ta định nghĩa hàm : Zm1 × . . . × Zmr

(

)

r
ρ a ,...a r = ∑ a M y mod
1
i i
i=1 i

ZM nh− sau

M

Ta sÏ chøng tá r»ng ρ = π-1 , tøc lµ nó cho một công thức tờng minh để giải
hệ đồng d thức ban đầu.
Kí hiệu X = (a1, . . . ,ar) vµ cho 1 ≤ j ≤ r. XÐt số hạng aiMiyi trong tổng
trên khi rút gọn theo modulo mj. NÕu i = j th×
aiMiyi ≡ ai (mod mi)


vì


Miyi 1 (mod mi)

Mặt khác, nếu i j thì
aiMiyi 0(mod mj)
do mi Mi trong trờng hợp này. Bëi vËy chóng ta cã
X ≡ ∑ a iM
≡ a

i

(mod

i

y

i

(mod

m

j

m

j

)


)

Do ®iỊu nµy ®óng ®èi víi mäi j, 1 ≤ j r, nên X là nghiệm của hệ phơng trình
đồng d.
Tới lúc này cần phải chứng tỏ rằng nghiệm X là duy nhất theo modulo
M và điều này có thể đợc chứng tỏ bằng cách tính toán đơn giản. là hàm
từ một miền có lực lợng M sang một miỊn cã lùc l−ỵng M. Ta võa míi chøng
tá r»ng là một toàn ánh. Bởi vậy phải cũng là một đơn ánh (tức là phép
tơng ứng 1 - 1) do miền xác định và miền giá trị có cùng lực lợng. Điều đó
kéo theo là một song ánh và -1 = p. Cũng cần chú ý là -1 là một hàm tuyến
tính của các biến a1,. . ., ar.
Sau đây là một ví dụ lớn hơn để minh hoạ
Ví dụ 4.3
Giả sử r = 3, m1 = 7, m2 = 11 và m3 = 13. Khi đó M = 1001. Ta tÝnh M1
= 143, M2 = 91 và M3 = 77 và sau đó tính y1 = 5, y2 = 4 và y3 = 12. Khi đó hàm
-1: Z7ìZ11ìZ13 Z1001 có dạng:
-1(a1,a2,a3) = 715a1 +364a2 + 924a3 mod 1001
VÝ dô, nÕu x ≡ 5 (mod 7), x ≡ 3 (mod 11) vµ x ≡ 10 (mod 13) thì công thức
trên sẽ cho ta biết rằng
x = 715 × 5 + 364 × 3 + 924 × 10 mod 1001
= 13907 mod 1001
= 894 mod 1001
Điều này có thể kiểm tra đợc bằng cách rút gọn 894 theo modulo 7, 11
và 13.
Để tham khảo sau này, ta sẽ ghi các kết quả ở phần này dới dạng một
định lý


Định lý 4.3 (Định lý phần d China)
Giả sử m1, . . . ,mr là các số nguyên dơng nguyên tố cùng nhau từng đôi

một và cho a1, . . ., ar là các số nguyên. Khi đó, hệ r ®ång d− thøc x ≡ ai (mod
mi) (1 ≤ i ≤ r ) sÏ cã mét nghiÖm duy nhÊt theo modulo M = m1ì . . . ì mr đợc
cho theo c«ng thøc
r

x = ∑ a i M i y i mod M
trong đó Mi = M/mi và yi =

i =1
Mi-1 mod

mi, víi 1 ≤ i ≤ r.

4.2.3. C¸c kiÕn thức cần thiết khác
Sau đây sẽ nhắc tới một kết quả khác trong lý thuyết nhóm sơ cấp: định
lý Lagrange. Định lý này có liên quan đến cách đề cập về hệ mật RSA. Với
một nhóm nhân hữu hạn G, ta định nghĩa cấp của một phần tử g G là số
nguyên dơng m bé nhất sao cho gm = 1. Ta có kết quả sau đây (không chứng
minh ).
Định lý 4.4 (Lagrange )
Giả sử G là một nhóm cấp n và g G. Khi đó cấp của g là ớc của n.
Với mục đích đa ra, hệ qu¶ sau rÊt quan träng.
HƯ qu¶ 4.5
NÕu b ∈ Zn* thì b(n) 1 (mod n)
Chứng minh: Zn* là nhóm nhân cấp (n).
Hệ quả 4.6 (Ferma)
Giả sử p là số nguyên tố và b Zp. Khi đó bp b (mod p).
Chứng minh:
Nếu p là số nguyên tố thì (n) = p-1. Bởi vậy, với b0(mod p),
kết quả trên đợc rút ra từ hệ quả 4.5. Với b 0 (mod p), kết quả trên

vẫn đúng do 0p 0 (mod 0).
Cho tíi giê ta ® biÕt r»ng, nÕu p là số nguyên tố thì Zp* là một nhóm
cấp p-1 và một phần tử bất kì trong Zp* sẽ có bậc là ớc của p-1. Tuy nhiên,
nếu p là số nguyên tố thì nhóm Zp* là nhóm cyclic: tồn tại một phần tử Zp*


có cấp bằng p-1. Ta không chứng minh kết quả quan trọng này nhng sẽ ghi
lại để tham khảo sau này.
Định lý 4.7.
Nếu p là số nguyên tố thì Zp* là nhóm cyclic.
Một phần tử có cấp p-1 đợc gọi là phần tử nguyên thuỷ modulo p.
Xét thấy là phần tử nguyên thuỷ khi và chỉ khi:
{i : 0 i p-2} = Zp*
Bây giờ giả sử p nguyên tố và - phần tử nguyên thuỷ modulo p. Một phần
tử bất kì Zp* có thể đợc viết nh sau: = i, trong ®ã 0 ≤ i ≤ p-2 (theo
mét c¸ch duy nhÊt ). Không khó khăn có thể chứng tỏ rằng cấp cđa β = αi lµ:
p -1
UCLN(p - 1, i)

Nh− vËy bản thân là phần tử nguyên thuỷ khi và chỉ khi CLN (p-1,i) = 1.
Điều đó dẫn đến là số các phần tử nguyên thuỷ theo modulo p = (p-1).
Ví dụ 4.4:
Giả sử p=13. Bằng cách tính các luỹ thõa liªn tiÕp cđa 2 ta cã thĨ thÊy
r»ng 2 là phần tử nguyên thuỷ theo modulo 13:
20 mod 13 =1
23 mod 13 =8
26 mod 13 =12
29 mod 13 =5

21 mod 13 =2

24 mod 13 =3
27 mod 13 =11
210 mod 13 =10

22 mod 13 =4
25 mod 13 =6
28 mod 13 =9
211 mod 13 =7

Phần tử 2i là nguyên thuỷ khi vµ chØ khi −CLN(i,12) = 1; nghÜa lµ khi vµ chØ
khi i = 1, 5, 7 hc 11. Bëi vËy các phần tử nguyên thuỷ theo modulo 13 là 2,
6, 7 và 11.

4.3. hệ mật RSA
Bây giờ chúng ta có thể mô tả hệ mật RSA. Hệ mật này sử dụng các tính
toán trong Zn, trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta nhËn
thÊy r»ng φ(n) = (p-1)(q-1).


Mô tả hình thức của hệ mật đợc cho trong hình 4.2 . Ta h y kiểm tra
xem các phép m và giải m có phải là các phép toán nghịch đảo của nhau hay
không. Vì
ab 1 (mod (n))
nên ta cã
ab = t φ(n) + 1
víi mét sè nguyªn t 1 nào đó. Giả sử x Zp*; khi ®ã ta cã:
(xb)a ≡ xtφ(n)+1 (mod n)
≡ (xφ(n))t x (mod n)
≡ 1t x (mod n)
≡ x (mod n)

H×nh 4.2: Hệ mật RSA
Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P = C = Zn
và định nghĩa
K = {(n,p,q,a,b): n = p.q, p,q là các số nguyên tố, ab 1(mod (n))}
Với K = (n,p,q,a,b) ta xác định
eK (x) = xb mod n
và
dK (y) = ya mod n
(x,y) Zn. Các giá trị n và b đợc công khai , các giá trị p,q,a đợc giữ
bí mật.
đúng nh mong muốn. Xem nh một bài tập, bạn đọc h y chứng tỏ rằng (xb)a
x (mod n) nếu x Zn\ Zp*.
Sau đây là một ví dụ nhỏ (tất nhiên là không mật ) vỊ hƯ mËt RSA.
VÝ dơ 4.5:
Gi¶ sư Bob chän p = 101 và q = 113. Khi đó n = 11413 và (n) =
100ì112 = 11200. Vì 11200 = 26527, nªn cã thĨ dïng mét sè nguyªn b nh−
mét sè mũ m hoá khi và chỉ khi b không chia hết cho 2, 5 hoặc 7. (Vì thế
trong thực tế Bob sẽ không phân tích (n), anh ta sẽ kiểm tra điều kiện
CLN((n),b) = 1 bằng thuật toán Euclide. Giả sử Bob chọn b = 3533, khi đó
theo thuật toán Euclide më réng:
b-1 = 6597 mod 11200


Bởi vậy số mũ mật để giải m của Bob là a = 6597.
Bob sẽ công bố n = 11413 và b = 3533 trong một danh bạ. Bây giờ, giả
sử Alice muốn gửi bản rõ 9726 tới Bob. Cô ta tÝnh
97263533 mod 11413 = 5761
råi gưi b¶n m 5761 trên kênh. Khi đó Bob nhận đợc bản m 5761, anh ta sư
dơng sè mị a mËt ®Ĩ tÝnh:
57616597 mod 11413 = 9762

(cho tới lúc này, các phép m và giải m cho hệ mật đ khá phức tạp, tuy nhiên
ta sẽ thảo luận về các thuật toán hữu hiệu cho các phép toán này ở phần sau).
Độ mật của hệ RSA đợc dựa trên giả thiết là hàm m ek(x)= xb mod n
là hàm một chiều. Bởi vậy thám m sẽ không có khả năng về mặt tính toán ®Ĩ
gi¶i m mét b¶n m . Cưa sËp cho phÐp Bob giải m đợc chính là thông tin về
phép phân tÝch thõa sè n (n = pq). V× Bob biÕt phân tích này, anh ta có thể tính
(n) = (p-1)(q-1) và rồi tính số mũ giải m a bằng cách sử dụng thuật toán
Euclide mở rộng. Sau này chúng ta sẽ còn tiếp tục nói thêm về vấn dề này.

4.4. Thực hiện hệ mật RSA
Có nhiều khía cạnh cần thảo ln vỊ hƯ mËt RSA bao gåm c¸c chi tiÕt
vỊ viƯc thiÕt lËp hƯ mËt, tÝnh hiƯu qu¶ cđa phÐp m và giải m và độ mật của
hệ. Để thiết lập hệ thống, Bob sẽ tuân theo các bớc đợc nêu trong hình 4.3.
Hình 4.3 Thiết lập hệ mật RSA
1. Bob tạo hai số nguyên tố lớn p và q
2. Bob tÝnh n = p.q vµ φ(n) = (p-1)(q-1)
3. Bob chän mét sè ngÉu nhiªn b (0< b < φ(n)) sao cho
−CLN(b,φ(n)) = 1
4. Bob tÝnh a = b-1 mod (n) bằng cách dùng thuật toán Euclide
5.

Bob công bố n và b trong một danh bạ và chúng làm khoá c«ng
khai.


Việc Bob tiến hành các bớc này nh thế nào sẽ còn đợc tiếp tục thảo luận
trong chơng này.
Cách tấn công dễ thấy nhất hệ mật này là thám m cố gắng phân tích n
ra các thừa số nguyên tố. Nếu thực hiện đợc việc này thì có thể dễ dàng tính
đợc (n) = (p-1)(q-1) rồi tính số mũ a từ b nh Bob làm (ngời ta phỏng đoán

rằng, việc phá hệ mật RSA là tơng đơng đa thức với việc phân tích n, tuy
nhiên điều này vẫn còn cha đợc chứng minh. Hai bài toán đợc gọi là tơng
đơng đa thức nếu tồn tại một thuật toán thời gian đa thức cho bài toán này sẽ
suy ra đợc sự tồn tại một thuật toán thời gian đa thức cho bài toán kia).
Vì thế hệ mật RSA đợc coi là mật thì nhất thiết n = pq phải là một số
đủ lớn để việc phân tích nó không có khả năng về mặt tính toán. Các thuật toán
phân tích hiện thời có khả năng phân tích các số có 130 chữ số thập phân (chi
tiết hơn về bài toán phân tích thừa số nguyên tố xem trong phần 4.8). Vì vậy
để đảm bảo an toàn nên chọn các số p và q chừng 100 chữ số, khi đó n sẽ có
tới 200 chữ số. Một vài áp dụng phần cứng của RSA sử dụng mô đun có độ dài
512 bit. Tuy nhiên một mô đun 512 bit tơng ứng với một số có 154 chữ số
thập phân (vì số các bit trong biểu diễn nhị phân của một số nguyên băng
log210 lần của các chữ số thập phân) vì vậy không đủ đảm bảo an toàn lâu dài.
Bây giờ tạm thời gác lại vấn đề tìm các số nguyên tố có 100 chữ số để xem xét
việc thực hiện các phép toán số học trong m và giải m . Phép m (hoặc giải
m ) sẽ xoay quanh phép lấy luỹ thừa theo modulo n. Vì n là một số rất lớn
nên ta phải sử dụng số học lấy chính xác nhiều lần (multi precision) để thực
hiện các tính toán trong Zn và thời gian tính toán cần thiết sẽ phụ thuộc vào số
các bít trong biểu diễn nhị phân của n.
Giả sử n có k bit trong biểu diễn nhị phân, tức là k = log2 n + 1. Sư
dơng kÜ tht sè häc ë bËc trung häc, dễ dàng thấy rằng một phép cộng hai số
nguyên k bit cã thĨ thùc hiƯn trong thêi gian O(k) vµ mét phÐp nh©n cã thĨ
thùc hiƯn trong thêi gian O(k2). Cịng vËy, phÐp rót gän mét sè nguyªn theo
modulo n (sè nµy cã nhiỊu nhÊt lµ 2K bÝt )cã thĨ thùc hiƯn trong thêi gian
O(k2) (®Ĩ thùc hiƯn phÐp chia và phép tìm phần d). Bây giờ giả sử rằng
x,yZn (ở đây xem rằng 0 x,y n-1). Khi ®ã cã thĨ tÝnh xy mod n tr−íc tiªn
b»ng viƯc tính tích xy (là một số nguyên 2k bít), rồi rót gän cho modulo n. Hai
b−íc nµy cã thĨ thùc hiƯn trong thêi gian O(k2). Ta gäi phÐp tÝnh nµy là nhân
modulo.
Bây giờ xét phép lấy luỹ thừa theo modulo (tức là tính hàm dạng xc mod

n). Nh nhận xét ở trên, cả hai phép m và giải m trong RSA đều là các phép


luü thõa theo modulo. ViÖc tÝnh xc mod n cã thể thực hiện bằng c-1 phép nhân
modulo, tuy nhiên khi c lớn thì cách tính này rất cồng kềnh. Chú ý r»ng c lín
cì nh− φ(n) -1 (lµ mét sè lín cÊp l thõa so víi k).
Sư dơng biƯn ph¸p "bình phơng và nhân" đ biết sẽ làm giảm số phép
nhân modulo cần thiết, để tính x mod n nhiều nhất là 2l, trong đó l là số các
bit trong biễu diễn nhị phân của c. Vì l k nên có thể coi xc mod n đợc thực
hiện trong thời gian O(k3). Vì thế các phép m và giải m đợc thực hiện theo
thời gian đa thức (nh một hàm của k là số các bít trong một bản rõ (hoặc bản
m ).
Trong thuật toán bình phơng và nhân, ta coi rằng số mũ b đợc biểu
thị ở dạng nhị phân nh sau:
l -1

b = bi 2i 2
i =0

Trong đó bi = 0 hoặc 1, 0 i l-1. Thuật toán để tính z = xb mod n đợc mô tả
ở hình 4.4.
Hình 2.5 Thuật toán bình phơng và nhân để tính xb mod n
1.
2.
3.
4.

z=1
for i = l-1 down to 0 do
z = z2 mod n

if bi = 1 then z = z.x mod n

DƠ dµng tính đợc số các phép nhân modulo thực hiện bởi thuật toán
trên. Luôn luôn phải thực hiện l phép bình phơng (ở bớc 3). Số phép nhân
trong bớc 4 bằng số các bit "1" trong biểu diễn nhị phân của b (số này thuộc
khoảng từ 0 tới l). Bởi vậy tổng số phép nhân modulo cần thực hiện nằm trong
khoảng từ l tới 2l.
Ta sẽ minh hoạ cách sử dụng thuật toán trên bằng cách quay trở lại ví dụ
4.5.
Ví dô 4.5 (tiÕp):


Ta có n = 11413 và số mũ m hoá công khai b = 3533. Alice sẽ m hoá bản râ
9726 b»ng c¸ch tÝnh 97263533 mod 11413 theo thuËt to¸n bình phơng và
nhân nh sau:
i

bi

z

11

1

12ì 9726 = 9726

10

1


9

0

97262 ì 9726 = 2659
26592 = 5634

8

1

56342 × 9726 = 9167

7

1

91672 × 9726 = 4958

6

1

5

0

4


0

49582 × 9726 = 7783
77832 = 6298
62982 = 4629

3

1

46292 × 9726 = 10185

2

1

1

0

101852 × 9726 = 105
1052 = 11025

0

1

110252 ì 9726 = 5761

Nh vậy bản m là 5761.

Cần phải nhấn mạnh rằng, những ứng dụng phần cứng hiệu quả nhất
hiện thời của RSA chỉ đạt đợc tốc độ m hoá chừng 600Kb/s (sử dụng các mô
đun 512 bít) so với DES có tốc độ 1 Gb/s. Nói cách khác RSA chậm hơn
khoảng 1500 lần so với DES.
Đến đây, ta chỉ mới xét đợc các phép m hoá và giải m cho RSA. Để
thiết lập hệ mật RSA, ta còn phải xét việc tạo các số nguyên tố p và q (bớc 1),
bớc này sẽ đợc nghiên cứu ở phần sau. Bớc 2 khá đơn giản và đợc thực
hiện trong thời gian O((log n)2). Các bớc 3 và 4 xoay quanh thuật toán
Euclide, vì thế sẽ xét qua về độ phức tạp của thuật toán này.
Giả sử ta phải tính CLN của r0 và r1, trong đó r0 > r1 . Trong mỗi bớc
lặp đều phải tính thơng và phần d, điều này có thể thực hiện đợc trong thời
gian O((log r0)2). Nếu tìm đợc giới hạn trên cho số phép lặp thì ta sẽ có đợc
giới hạn cho độ phức tạp của thuật toán. Kết quả này đ đợc nêu trong định lý
Lamé. Định lý khẳng định rằng nếu s là số các phép lặp thì f3+2 r0 , trong đó
fi là số Fibonacci thứ i . Vì


1 + 5

fi =

2


Nên điều đó kéo theo s là O(log r0).

Điều này chứng tỏ rằng thời gian chạy của thuật toán Euclide là O((log
n)3) (trên thực tế, bằng các phân tích chi tiết hơn, có thể chứng tỏ rằng thời
gian chạy chỉ là O((log n)2).


4.5. 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ật toán cho rằng n là số nguyên tố trong khi thực tế n là hợp 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 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 st 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 tht 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ố.
Đặ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 ?

Hình 4.6. Bài toán về các thặng d bậc hai.

Đặ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 ?


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 d y2 x
(modulo p) có một nghiệm yZp 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,
2
(1) =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-11 (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)/21 (mod p). Cho p là một phần tử nguyên
thuỷ theo modulo p. Khi đó xbi (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× b 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.
Đị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à một số nguyê n tố lẻ. Víi mét sè nguyª n bÊt kú a ≥ 0 ,
a
ta dÞnh nghÜa ký hiƯu Legendre   nh− sau :
 p
0 nÕu a ≡ 0 (mod p)
a
  = 1 nếu a là thặng d bậc hai theo modulo p
p
- 1 nếu a 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× ap1
≡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

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.
a
 
r


Ký hiệu Jacobi

đợc định nghĩa nh sau:

a K  a
 = ∏

 n  i =1 p i






ei

VÝ dơ 4.7.
 6278
XÐt ký hiƯu Jacobi 
 9975
2
lµ : 9975 = 3 × 5 × 7 × 19. Bëi


 . Phan tÝch l thõa nguyª n tè cđa 9975

vËy ta cã :
2

 6278   6278   6278   6278   6278 

=

 


 9975   3   5   7   19 

2

 2  3   6  8 
2
=     
 = (− 1 )(− 1 ) (− 1 )(− 1 )
 3   5   7   19 
= - 1.
a
Gi¶ sư n > 1 là một số lẻ. Nếu n là nguyª n tè thi   ≡ a (n - 1)/2 (mod n )
n

a

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ì :
10
45
 = −1 = 10 mod 91
 9 

Tuy nhiªn có thể chứng tỏ rằng, với một hợp số lẻ n bÊt kú, sÏ cã 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 đợc nêu ở hình 4.7 là thuật toán
Monte-Carlo định hớng cóvới xác xuất sai tối đa là 1/2.

Đến đây vẫn cha xác định rõ thuật toán ttrên có theo thời gian đa thức hay
không.
Ta ® biÕt c¸ch ®¸nh gi¸ a(n-1)/2 (mod n) trong thêi gian đa thức
O((log n)3), tuy nhiên cần phải làm thế nào để tính các ký hiệu Jacobi một
cách có hiệu quả. Vì ký hiệu Jacobi đợc xác định theo các thõa sè trong ph©n


tích của n. Tuy nhiên nếu có thể phân tích đợc n thì ta đ biết nó có phải là số
nguyên tố hay không, bởi vậy cách làm này sẽ dẫn tới một vòng luẩn quẩn.
Hình 4.7. Thuật toán kiểm tra tính nguyên tố Solova-Strassen với số
nguyên lẻ n.

1. Chọn mét sè nguyªn ngÉu nhiªn a, 1 ≤ a ≤ n-1
2. Nếu

a

n

a(n-1)/2 (mod n) thì

Trả lời n là số nguyên tố
Nếu không
Trả lời n là một hợp số

Rất may là có thể đánh giá ký hiệu Jacobi mà không cần phải phân tích
n nhờ sư dơng mét sè kÕt qu¶ cđa lý thut sè, trong đó kết quả quan trọng
nhất là tính chất 4 (tổng quát hoá luật tơng hỗ bậc hai ).
Ta sẽ liệt kê mà không chứng minh các tính chất này.
1. Nếu n là một số nguyên tố lẻ và m1 ≡ m2 (mod n) th×:

 m1 


 n =



=

 m2


n



2. Nếu n là một số nguyên lẻ th×
1 nÕu n ≡ ± 1 (mod 8)
2
  =
-1 nÕu n ≡ ± 3 (mod 8)
n
3. NÕu n lµ một số nguyên lẻ thì

m 1 m 2  m 1  m 2 

=


 n   n n

Đặc biệt nếu m=2kt với t là một số lẻ thì:


k

 m 
 2   t 

 =    
 n 
 n   n 
4. Giả sử m và n là các số nguyên lẻ, khi ®ã:

=

2
 
n

 n
−  m  nÕu m ≡ n ≡ 3 (mod 4)
  

  n  trong các trờng hợp còn lại
m

Ví dụ
Để minh hoạ cho việc áp dụng các tính chất trên , ta sẽ đánh
7411



9283

giá kíhiệu Jacobi

nh trong bảng dới đây. Cần chú ý là

trong ví dụ này, ta đ sử dụng liên tiếp các tính chất4, 1,3 ,và 2.
Nói chung, bằng cách áp dụng 4 tính chất trên, có thể tính
toánkí hiệu Jacobi

m

n

trong thời gian đa thức. Các phép tính số

học dùng ở đây chỉ là rút gọn theo modulo và phân tích ra các luỹ thừa của
thuật toán đợc biểu diễn dới dạng nhị phân thì việc phân tích ra các luỹ thừa
của hai số chính là việc xác định số các số 0 tiếp sau. Bởi vậy, độ phức tạp của
thuật toán đợc xác định bởi số các phép rút gọn theo modulo cần tiến hành.
Không khó khăn lắm có thể chứng tỏ rằng, cần thực hiện nhiều nhất là.

7411
9283 

 = −

 9283 
 7411 


=
.

=
=
=
=
=

 1872 
−

 7411 
4
 2   117 
−
 

 7411   7411 
 117 
−

 7411 
 7411 
−

 117 
 40 
−


 177 
3
 2   5 
−
 

 117   117 

theo tÝnh chÊt 4
theo tÝnh chÊt 1
theo tÝnh chÊt 3
theo tÝnh chÊt 2
theo tÝnh chÊt 4
theo tÝnh chÊt 1
theo tÝnh chÊt 3


O(log n) phép rút gọn theo modulo. Mỗi phép có thể thực hiện trong thời gian
O((log n)2). Điều đó chứng tỏ rằng, độ phức tạp là O((log n)3) là đa thức theo
log n. Thực ra bằng các phân tích chính xác hơn, có thể chứng tỏ răng, độ phức
tạp chỉ cỡ O((log n)2).
Giả sử ta đ tạo đợc một số ngẫu nhiên n và đ kiểm tra tính nguyên tố
của nó theo thuật toán Soloway- Strasen. Nếu chạy thuật toán m lần thì câu trả
lời n là một số nguyên tố sẽ có mức độ tin cậy nh thế nào? Quả là liều lĩnh
nếu coi răng, xác suất này là 1-2-m. Kết luận này thờng đợc nêu trong các
giáo trình và bài báo kĩ thuật, tuy nhiên ta không thể dẫn ra theo các số liệu
cho trớc.
Cần phải thận trọng hơn khi sự dụng các tính toán xác suất. Ta sẽ định
nghĩa các biến ngẫu nhiên sau:

a- Chỉ sự kiện số nguyên lẻ n có kích thớc đ định là một hợp số.
b- Chỉ sự kiện thuật toán trả lời n là số nguyên tố m lần liên tiếp .
Điều chắc chắn là prob(b| a)2-m. Tuy nhiên xác suất mà ta thực sự quan tâm là
prob(a/b), xác suất này thờng kh«ng gièng nh− prob(b/a).


Có thể tính prob(a/b) bằng định lý Bayes (định lý2.1). Trớc hết cần phải biết
prob(a). Giả sử N n 2N. áp dụng định lý về số nguyên tố: các số nguyên
tố(lẻ) giửa N và 2N xấp xỉ bằng:
`

2N/ln 2N – N/ln N ≈ N/ ln N
≈ n/ln n

V× có N/2 n/2 số nguyên tố lẻ giửa N và 2N, ta sẽ dùng ớc lợng

Prob(a) 1 2/ln n
Sau đó có thể tính toán nh sau:
prob(ba | a)prob(a)
prob(b)
prob(b | a)prob(a)
=
prob(b | a)prob(a) + prob(b | a)prob( a )
2
prob(b | a)(1 )
ln
n
≈
2
2

prob(b | a)(1 )+
ln n ln n
prob(b | a)(ln n - 2)
=
prob(b | a)(ln n - 2) + 2

prob(a | b) =

2-m (ln n − 2)
2 −m (ln n − 2) + 2
ln n - 2
=
ln n - 2 + 2 m+ 1
≤

Chó ý r»ng trong tÝnh toán trên
một số nguyên tố.

chỉ sự kiện số nguyên lẻ ngẫu nhiên n là

Khá thú vị nếu so sánh hai hµm sau cđa m
(ln n − 2)
ln n − 2 + 2 m +1

Gi¶ sù n ≈ 2256 ≈ e177 (đây là kích thớc của các số nguyên tố sự dông