Ktl-icon-tai-lieu

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

Được đăng lên bởi bai-tap-lon
Số trang: 8 trang   |   Lượt xem: 659 lần   |   Lượt tải: 0 lần
Vietebooks Nguyn 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
log
2
n, 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ù.
Kiểm tra tính nguyên tố xác suất - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Kiểm tra tính nguyên tố xác suất - Người đăng: bai-tap-lon
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
8 Vietnamese
Kiểm tra tính nguyên tố xác suất 9 10 666