Số mersenne và việc phân tích

Lêi nãi ®Çu Bµi to¸n ph©n tÝch sè nguyªn ra thõa sè nguyªn tè ®· ®­îc ra ®êi tõ rÊt l©u vµ ®· cã rÊt nhiÒu nhµ to¸n häc trªn thÕ giíi nghiªn cøu vµ gi¶i quyÕt vÊn ®Ò vÒ nã. Ngoµi ý nghÜa lý thuyÕt cña b¶n th©n bµi to¸n th× ng­êi ta cßn ph¸t hiÖn ra rÊt nhiÒu ý nghÜa thùc tiÔn ®Æc biÖt lµ trong mËt m·. Thø nhÊt nã lµ c¬ së cho sù ra ®êi cña mét hÖ mËt kho¸ c«ng khai næi tiÕng ra ®êi trong n¨m 1978, ®ã lµ hÖ mËt RSA cña Revert - Shamir - Adlemal. HÖ mËt nµy mµ ®é mËt cña nã dùa vµo tÝnh khã cña viÖc ph©n tÝch sè N=pq (p, q nguyªn tè ) ra thõa sè. TiÕp ®Õn trong nh÷ng viÖc thiÕt kÕ nªn c¸c bé t¹o d·y gi¶ ngÉu nhiªn mét trong nh÷ng nguyªn liÖu cña nã lµ c¸c ®a thøc nguyªn thuû mµ ®Ó t¹o ®­îc c¸c ®a thøc nguyªn thuû bËc m th× ®iÒu ®Çu tiªn ph¶i gi¶i quyÕt lµ ph©n tÝch hoµn toµn víi 2m-1 ra thõa sè nguyªn tè. §Ó gi¶i quyÕt vÊn ®Ò ®­îc ®Æt ra trong ®å ¸n nµy, chóng t«i ®­a ra mét sè c¬ së lý thuyÕt. Ch­¬ng 1 sÏ tr×nh bÇy vÒ c¸c sè Mersenne. C¸c sè cã d¹ng Mq=2q-1 (víi q lµ nguyªn tè ) ®­îc gäi lµ c¸c sè Mersenne vµ ®· ®­îc nghiªn cøu c«ng phu. Ch­¬ng 2 xem xÐt lo¹i bµi to¸n quen thuéc h¬n ®ã lµ bµi to¸n ph©n tÝch sè nguyªn ra thõa sè. Sù ®ãng gãp cã tÝnh khoa häc cña chóng t«i thÒ hiÖn bëi viÖc tr×nh bµy c¸c thuËt to¸n vÒ ph©n tÝch sè nguyªn tè theo c¸ch hiÓu cña m×nh. Ch­¬ng 3 lµ phÇn c¬ b¶n cña ®Ò ¸n, trong ®ã tr×nh bµy c¸c t­ t­ëng cña thuËt to¸n ph©n tÝch ra thõa sè nguyªn tè cña nh÷ng sè nguyªn lín. TiÕp theo trong ch­¬ng nµy tr×nh bµy c¸c cµi ®Æt cô thÓ cho nh÷ng thuËt to¸n liªn quan ®Õn viÖc ph©n tÝch ra thõa sè nguyªn tè, vÝ dô nh­ c¸c phÐp : +, -, *, / vµ luü thõa c¸c sè lín. Chóng t«i cßn ®Æc biÖt l­u ý tíi viÖc cµi ®Æt thuËt to¸n Pollard thø nhÊt mét thuËt to¸n rÊt hiªô qu¶ trong viÖc ph©n tÝch nh÷ng hîp sè lín. Mét vÊn ®Ò kh«ng thÓ kh«ng nãi tr­íc lµ nh÷ng vÊn ®Ò ®­îc hiÓu thÊu ®¸o sÏ ®­îc chóng t«i tr×nh bµy chi tiÕt ë møc ®é thuËt to¸n kh¶ thi trong viÖc lËp tr×nh, cßn mét sè kÕt qu¶ cÇn ®Õn nh÷ng chuÈn bÞ to¸n häc cao siªu th× chØ ®­îc dÉn c¸c ®¸nh gi¸ t­¬ng øng vÒ thêi gian tÝnh ®ñ rót ra c¸c th«ng sè cÇn thiÕt ®Ó x©y dùng c¸c tiªu trÝ. Chóng t«i nghÜ r»ng chØ cã thÓ tr×nh bµy b¶n b¸o c¸o nµy theo c¸ch nh­ vËy míi ®¶m b¶o tÝnh c©n ®èi trong cÊu tróc bëi v× ®Ó lµm cho t­êng minh dï chØ mét trong nh÷ng vÊn ®Ò ®· nÐ tr¸nh trªn chóng ta còng ph¶i cÇn ®Õn hµng tËp tµi liÖu dÇy, ®Êy lµ ch­a kÓ ®Õn viÖc chóng ta cã ®ñ kiÕn thøc cÇn thiÕt ®Õn møc ®Ó cã thÓ tr×nh bµy nã cho mäi ng­êi râ hay kh«ng. Ch­¬ng i. §Æt vÊn ®Ò vµ ý nghÜa cña bµI to¸n Bµi to¸n ph©n tÝch sè nguyªn ra thõa sè nguyªn tè ®· ®­îc ra ®êi tõ rÊt l©u vµ ®· cuèn hót nhiÒu bé ãc vÜ ®¹i nhÊt trªn thÕ giíi ®Ó gi¶i quyÕt vÊn ®Ò vÒ nã. Ngoµi ý nghÜa lý thuyÕt cña b¶n th©n bµi to¸n th× ng­êi ta cßn ph¸t hiÖn ra rÊt nhiÒu ý nghÜa thùc tiÔn ®Æc biÖt lµ trong mËt m·. Thø nhÊt, nã lµ c¬ së cho sù ra ®êi cña mét hÖ mËt kho¸ c«ng khai næi tiÕng vµo n¨m 1978, ®ã lµ hÖ mËt m· RSA ( RSA lµ tõ viÕt t¾t cña ba ng­êi: Rivets – Shamir – Adleman ). HÖ mËt nµy cã néi dung ®Ò cËp ®Õn viÖc ph©n tÝch sè nguyªn tè ngÉu nhiªn lín (ch¼ng h¹n cã 80 ch÷ sè) ra thõa sè. Mét vÊn ®Ò quan träng 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. TiÕp ®Õn trong nh÷ng viÖc thiÕt kÕ nªn c¸c bé t¹o d·y gi¶ ngÉu nhiªn mét trong nh÷ng nguyªn liÖu cña nã lµ c¸c ®a thøc nguyªn thuû mµ ®Ó t¹o ®­îc c¸c ®a thøc nguyªn thuû bËc m th× ®iÒu ®Çu tiªn ph¶i gi¶i quyÕt lµ ph©n tÝch hoµn toµn víi 2m-1 ra thõa sè nguyªn tè. §Ó 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, ®©y lµ 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. B¶n ®å ¸n kh«ng ®i s©u vµo c¸c ph©n tÝch cña nh÷ng ý nghÜa nªu trªn mµ ®· ®Æt nhiÖm vô chÝnh lµ gi¶i quyÕt bµi to¸n “ph©n tÝch sè nguyªn ra thõa sè nguyªn tè nh­ lµ mét viÖc lµm trung gian cña mét øng dông thùc tiÔn cô thÓ. §· cã mét khèi l­îng khæng lå c¸c tµi liÖu vÒ c¸c thuËt to¸n ph©n tÝch thõa sè vµ viÖc nghiªn cøu kü l­ìng sÏ ®ßi hái ph¶i cã mét cuèn s¸ch dµy trang h¬n quyÓn s¸ch nµy. ë ®©y chØ cè g¾ng ®­a ra mét c¸i nh×n kh¸i qu¸t bao gåm viÖc th¶o luËn s¬ l­îc vÒ c¸c thuËt to¸n ph©n tÝch thõa sè tèt nhÊt hiÖn thêi vµ c¸ch sö dông chóng trong thùc tÕ. C¸c thuËt to¸n næi tiÕng kh¸c (nh÷ng thuËt to¸n to¸n cã tr­íc) bao gåm thuËt to¸n p+1 cña Williams, ph­¬ng ph¸p r vµ thuËt to¸n p-1 cña Pollard, thuËt to¸n liªn ph©n sè vµ dÜ nhiªn c¶ nh÷ng phÐp chia thö. Ch­¬ng iI. Sè Mersenne vµ viÖc ph©n tÝch 2.1 Sè Mersenne NÕu mét sè cã d¹ng 2m-1 lµ mét sè nguyªn tè th× m=q lµ mét sè nguyªn tè. Kh«ng khã kh¨n l¾m, cã thÓ chøng minh ®­îc r»ng nÕu 2m-1 lµ luü thõa cña mét sè Prime Power th× nã ph¶i lµ mét sè nguyªn tè vµ do vËy m còng lµ mét sè nguyªn tè. C¸c sè cã d¹ng Mq=2q-1 (víi q lµ nguyªn tè ) ®­îc gäi lµ c¸c sè Mersenne vµ ®· ®­îc nghiªn cøu c«ng phu. ë vµo thêi ®¹i cña Mersenne, ng­êi ta ®· biÕt r»ng mét vµi sè Mersenne lµ sè chÝnh ph­¬ng vµ mét vµi sè kh¸c lµ hîp sè. VÝ dô, M2=3, M3=7, M5=31, M7=127 lµ nguyªn tè, trong khi M11=23*89. Vµo n¨m 1640 , Mersenne ®· cho r»ng Mq lµ sè nguyªn tè ®èi víi q=13,17,19,31,67,127,257; «ng ®· nhÇm ®èi víi 67 vµ 257 vµ ®· kh«ng ®­a 61,89 vµ 107(nh÷ng sè nhá h¬n 257) vµo danh s¸ch trªn. Nh÷ng sè nµy còng sinh ra c¸c sè nguyªn tè Mersenne. Ph¸t hiÖn cña «ng thùc sù ®¸ng kinh ng¹c vÒ mÆt ®é lín cña c¸c sè. Mét bµi to¸n kh¸ hiÓn nhiªn lµ: XÐt xem mét sè Mersenne cã lµ sè nguyªn tè kh«ng, vµ nÕu kh«ng th× x¸c ®Þnh c¸c thõa sè cña nã ( hay cßn gäi lµ bµi to¸n ph©n tÝch ra thõa sè). Mét kÕt qu¶ cæ ®iÓn do Euler ®­a ra n¨m 1750 vµ sau ®ã ®­îc Lagrange (1775) vµ Lucas (1875) chøng minh lµ: Bµi to¸n: NÕu q lµ mét sè nguyªn tè ®ång d­ modulo 4(qº3(mod 4)) th× Mq chia hÕt cho 2q+1 khi vµ chØ khi 2q+1 lµ nguyªn tè; trong tr­êng hîp nµy, nÕu q>3 th× Mq lµ hîp sè. Chøng minh: Cho n=2q+1 lµ mét thõa sè cña M. V× 22#1 (mod n) nªn 2q#1 (mod n), vµ 22q-1=(2q+1)Mqº0 (mod n), tõ ®ã b»ng phÐp thö cña Lucas suy ra n lµ mét sè nguyªn tè. Ng­îc l¹i, cho p=2q+1 lµ mét sè nguyªn tè. V× pº7(mod 8) nªn (2/p)=1, do vËy tån t¹i m sao cho 2ºm2 (mod p). §iÒu nµy chøng tá r»ng 2qº2(p-1)/2ºmp-1º1(mod p) V× vËy Mq chia hÕt cho p. H¬n n÷a, nÕu q>3 th× Mq=2q-1>29+1=p, v× vËy Mq lµ hîp sè. V× vËy nÕu q=11, 23, 83, 131, 179, 191, 239, 251, th× Mq cã c¸c ­íc t­¬ng øng lµ 23, 47, 167, 263, 350, 383, 479, 503. Còng rÊt dÔ ®Ó x¸c ®Þnh h×nh d¹ng cña c¸c thõa sè cña c¸c sè Mersenne: "NÕu Mq chia hÕt cho n th× nº±1 (mod 8) vµ nº1 (mod q)" Chøng minh: ChØ cÇn chØ ra r»ng mäi thõa sè nguyªn tè p cña Mq cã d¹ng trªn lµ ®ñ. ThËt vËy, nÕu p lµ ­íc cña Mq=2q-1 th× 2qº1 (mod q); V× vËy theo bµi to¸n nhá cña Fermat th× q lµ ­íc cña p-1, tøc lµ p-1=2kq (v× p#2). V× vËy: (mod p). Do ®ã pº±1 mod (8). Ph­¬ng ph¸p tèt nhÊt hiÖn nay dïng ®Ó x¸c ®Þnh Mq lµ mét sè nguyªn tè hay lµ mét hîp sè ®­îc ph¸t triÓn dùa vµo viÖc tÝnh to¸n mét d·y ®Ö qui do Lucas (1878) vµ Lehmer (1930) ®­a ra. Tuy nhiªn, b»ng c¸ch nµy vÉn kh«ng t×m ra ®­îc c¸c thõa sè cô thÓ. NÕu n lÎ, n³3 th× Mn=2n-1º7 (mod 12). §ång thêi, nÕu Nº7 (mod 12) th× ký hiÖu Jacobi: 2.2. PhÐp thö nguyªn tè cho c¸c sè Mersenne Cho p=2,Q=-2 vµ xÐt c¸c d·y Lucas kÐp (Um)m³0,(Vm)m³0, cã biÖt gthøc D=12. N=Mn lµ mét sè nguyªn tè khi vµ chØ khi V(N-1)/2 chia hÕt cho N. Chøng minh: Cho N lµ mét sè nguyªn tè. Ta cã: V2(N+1)/2=VN+1+2Q(N-1)/2=VN-1-4(-2)(N-1)/2 º VN+1-4(-2/N) ºVN+1+4(mod N) V× (-2/N)=(-1/N)(2/N)=-1. V× vËy chØ cÇn chØ ra r»ng Nº7 (mod N). Theo (IV.4): 2VN-1=VNV1+DUNU1=2VN+12UN; do vËy theo (IV.14) vµ (IV.13): VN+1=VN+6VNº2+6(12/N) º2-6º-4(mod N). Ng­îc l¹i, gi¶ sö r»ng V(N+1)/2 chia hÕt cho N. ThÕ th× theo (IV.2), VN+1 chia hÕt cho N. §ång thêi, theo(IV.6): V2(N+1).2)=1 (gcd_­íc chung lín nhÊt). V× vËy gcd(N,2)=1, nªn thu phÐp thö mét (PhÇn V), N lµ mét sè nguyªn tè. §Ó cho tÝnh to¸n, ng­êi ta thay dÉy Lucas (Vm)m>=0 b»ng dÉy (Sk)k>=1 ®­îc ®Þnh nghÜa nh­ sau: S0=4; Sk+1=S2k-2; V× thÕ dÉy nµy sÏ khëi ®Çu b»ng 4,14,194,... vµ phÐp thö nguyªn tè ®­îc ph¸t biÓu l¹i nh­ sau: Mn=2n-1 lµ nguyªn tè khi vµ chØ khi Mn lµ ­íc cña Sn-2. Chøng minh: S0=4=V2/2. Gi¶ sö r»ng Sk-1=V2k/; th× Sk=S2k-1-2=. Theo phÐp thö nµy th× Mn lµ nguyªn tè khi vµ chØ khi Mn lµ ­íc cña V(Mn+1).2=, hay t­¬ng ®­¬ng Mn lµ ­íc cña Sn-2. TÝnh lÆp cña c¸c phÐp tÝnh nµy ®· lµm cho phÐp thö trë nªn phï hîp. B»ng c¸ch nµy, tÊt c¶ c¸c vÝ dô vÒ c¸c sè nguyªn tè Mersenne lín ®· ®­îc t×m ra. N¨m 1876 , Lucas ®· tù m×nh t×m ra M127 lµ nguyªn tè vµ M67 lµ hîp sè. Sau ®ã kh«ng l©u, Pervushin ®· chØ ra r»ng M61 còng lµ nguyªn tè. Cuèi cïng, vµo n¨m 1927 Lehmer chøng minh ®­îc M257 còng lµ hîp sè. Chó ý r»ng M127 cã 39 ch÷ sè vµ lµ sè nguyªn tè lín nhÊt ®­îc biÕt tíi tr­íc kû nguyªn cña m¸y tÝnh. C¸c sè nguyªn tè Mersenne víi q<= 127 ®­îc t×m ra tr­íc khi cã m¸y tÝnh ®iÖn tö. N¨m 1951, Turing ®· lÇn ®Çu tiªn thö dïng mét m¸y tÝnh ®Ó t×m c¸c sè nguyªn tè Mersenne nh­ng bÞ thÊt b¹i. N¨m 1952, Robinson ®· tiÕn hµnh phÐp thö cña Lucas trªn mét m¸y SWAC. ¤ng ®· t×m ra c¸c sè nguyªn tè Mersenne : M521, M607_nh÷ng sè ®Çu tiªn t×m ®­îc b»ng m¸y tÝnh. C¸c sè nguyªn tè M1279,M2203,M2281 còng ®­îc t×m ra trong cïng n¨m Êy. Sè nguyªn tè Mersenne lín nhÊt ®· t×m ®­îc lµ M21609, nã cã 65050 ch÷ sè do Slowinski ph¸t hiÖn n¨m 1985. Sè nguyªn tè Mersenne ®­îc t×m ra cuèi cïng lµ M110503 do Colquitt vµ Welsch ph¸t hiÖn n¨m 1988. N¨m 1989, Bateman, Selfridge vµ Wagstaff ®· ®­a ra mét pháng ®o¸n liªn quan ®Õn c¸c sè nguyªn tè Mersenne: Cho p lµ mét sè tù nhiªn lÎ (kh«ng nhÊt thiÕt ph¶i lµ nguyªn tè). NÕu hai trong c¸c ®iÒu kiÖn sau ®©y tho¶ m·n th× ®iÒu kiÖn thø 3 còng tho¶ m·n: pº2k±1 hoÆc p=4k±3 Mp lµ mét sè nguyªn tè lµ mét sè nguyªn tè Pháng ®o¸n nµy ®· ®­îc kiÓm chøng lµ ®óng ®èi víi mäi p<100.000. Nh÷ng sè nguyªn tè p<100.000 tho¶ m·n c¶ ba ®iÒu kiÖn lµ p=3, 5, 7, 13, 17, 19, 31, 61, 127. Cã thÓ tin r»ng nh÷ng sè nµy lµ c¸c sè nguyªn tè duy nhÊt tho¶ m·n c¶ ba ®iÒu kiÖn nãi trªn. Còng nh­ ®èi víi c¸c sè Fermat, hiÖn cßn cã rÊt nhiÒu vÊn ®Ò më vÒ c¸c sè Mersenne: LiÖu cã v« h¹n c¸c sè nguyªn tè Mersenne kh«ng? LiÖu cã v« h¹n c¸c sè Mersenne lµ hîp sè kh«ng? C©u tr¶ lêi cho c¶ hai c©u hái trªn ch¾c lµ “cã” (3) Cã ph¶i mäi sè Mersenne ®Òu lµ kh«ng chÝnh ph­¬ng kh«ng? Kû lôc: Cã 31 sè nguyªn tè Mersenne ®· ®­îc biÕt. D­íi ®©y lµ danh s¸ch ®Çy ®ñ cña chóng cïng víi tªn ng­êi vµ n¨m t×m ra. q N¨m Ng­êi ph¸t hiÖn 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 21701 23209 44497 86243 110503 132049 216091 1461 1588 1588 1750 1883 1911 1913 1876 1952 1952 1952 1952 1952 1957 1961 1961 1963 1963 1963 1971 1978 1979 1979 1982 1988 1983 1985 Anonymous* P.A.Cataldi P.A.Cataldi L.Euler I.M.Pervushin R.E.Powers E.Fauquembergue E.Lucas R.M.Robinson R.M.Robinson R.M.Robinson R.M.Robinson R.M.Robinson H.Riesel A.Hurwitz A.Hurwitz D.B.Gillies D.B.Gillies D.B.Gillies B.Tuckerman L.C.Noll & L.Nickel L.C. Noll H.Nelson & D. Slowinski D.Slowinski W.N.Colquitt & L. Welsch, Jr. D.Slowonski D.Slowonski “See Dickson’s History of the Theory of Numbers, Vol. I.p.6. Ch­¬ng iII. Mét sè thuËt to¸n vµ ph­¬ng ph¸p ph©n tÝch sè 3.1 ThuËt to¸n sµng Eratosthenes ThuËt to¸n ph©n tÝch sè nguyªn N ®­îc m« t¶ nh­ sau: ThuËt to¸n 3.1( sµng Eratosthenes ) (1) p=1. (2) p=p+1. (3) TÝnh r=N mod p. NÕu r>0 quay vÒ (2). Ng­îc l¹i p lµ ­íc cña N. Dõng ch­¬ng tr×nh... §©y lµ thuËt to¸n cã tÝnh phæ th«ng vµ mÆc dï nh­ chóng ta ®· biÕt lµ thuËt to¸n rÊt “tåi” v× thêi gian tÝnh cña nã lµ O() nh­ng nÕu N cã ­íc nhá th× viÖc ¸p dông thuËt to¸n nµy l¹i rÊt hiÖu qu¶. H¬n thÕ n÷a, thuËt to¸n nµy còng cã thÓ lÊy ®iÓm xuÊt ph¸t cña b­íc (1) lµ p=[] vµ tiÕn hµnh b­íc (2) lµ p=p-1 th× râ rµng nã còng hiÖu qu¶ nÕu ­íc cña N rÊt “gÇn” víi. 3.2 ThuËt to¸n sµng ®ång d­ ThuËt to¸n 3.2: LÊy ngÉu nhiªn hai sè a vµ b ngÉu nhiªn ÎZ*N. KiÓm tra gcd((a-b) mod N, N) hoÆc gcd((a+b) mod N, N)>1 lµ x¸c suÊt nh­ sau: NÕu ®óng th× gcd((a-b) mod N, N) hoÆc gcd((a+b) mod N, N)>1 lµ ­íc cña N. Dõng ch­¬ng tr×nh. Ng­îc l¹i quay vÒ (1). B©y giê chóng ta h·y t¹m dõng ®Ó ph©n tÝch thuËt to¸n d­íi gãc ®é x¸c suÊt nh­ sau: Cho p lµ ­íc nguyªn tè nhá nhÊt cña N, thÕ th× “cÇn cã tèi thiÓu bao nhiªu cÆp a, b ®­îc xÐt ®Õn x¸c suÊt { cã Ýt nhÊt mét cÆp a, b chia hÕt cho p} > 0.5”. Bµi to¸n trªn cßn ®­îc gäi lµ bµi to¸n “ trïng ngµy sinh ” vµ sè m tèi thiÓu cÇn t×m trong bµi to¸n sÏ lµ m»Cp víi C lµ mét h»ng sè tÝnh ®­îc nµo ®ã ( viÖc gi¶i chi tiÕt bµi to¸n trªn cã thÓ xem trong [Riesel]). Nh­ vËy chóng ta cã thÓ thµnh c«ng trong thuËt to¸n víi x¸c suÊt >0.5 sau kh«ng qu¸ m b­íc. HiÓn nhiªn b»ng c¸ch duyÖt dÇn th× thêi gian tÝnh cña thuËt to¸n cña chóng ta còng ch¼ng kh¸c g× thêi gian tÝnh cña phÐp sµng. Trong [Pollard], t¸c gi¶ J. M. Pollard ®· sö dông mét ph­¬ng ph¸p cßn ®­îc gäi lµ “ph­¬ng ph¸p p” nh»m chØ cÇn th«ng qua b­íc cã thÓ duyÖt ®­îc m cÆp kh¸c nhau nh­ ®· nªu trong thuËt to¸n. ViÖc thÓ hiÖn ph­¬ng ph¸p nµy cã thÓ m« t¶ nh­ sau: Chän d·y gi¶ ngÉu nhiªn {xi mod N:i=1,2,...} ®­îc x¸c ®Þnh nh­ sau xi-1º(xi2+a) mod N víi a#0 vµ #-2 cßn gi¸ trÞ ®Çu x0 tuú ý. 3.3 ThuËt to¸n sµng bËc hai Tö t­ëng chñ ®¹o cña mét lo¹t kh¸ lín c¸c thuËt to¸n ph©n tÝch sè nh­ ph­¬ng ph¸p ®Æc biÖt cña Euler, ph­¬ng ph¸p ph©n tÝch c¸c d¹ng chÝnh ph­¬ng cña Danien Shanks, ph­¬ng ph¸p khai triÓn liªn ph©n sè cña Morrison vµ Brillhart, ph­¬ng ph¸p sµng bËc hai cña Pomerance... lµ cè t×m ®ång d­ thøc x2=y2 mod N sao cho x#±y mod N, cßn kü thuËt t×m cô thÓ nh­ thÕ nµo th× chÝnh lµ néi dung riªng cña tõng thuËt to¸n. §èi víi thuËt to¸n sµng bËc hai cña Pomerance ®­îc thùc hiÖn nh­ sau: - Chän k sè nguyªn tè ®Çu tiªn vµ gäi lµ c¬ së ph©n tÝch. - Chän B lµ mét sè nµo ®ã gäi lµ ng­ìng t×m c¸c thÆng d­ bËc hai nhá. - T×m k+1 c¸c thÆng d­ bËc hai nhá h¬n B vµ ph©n tÝch ®­îc hoµn toµn trong tËp c¬ së trong líp c¸c sè d¹ng Q(x)º((m+x)2-N mod N víi k lµ sè phÇn tö cña c¬ së, m= cßn x=0, ±1, ±2,... - X©y dùng ®ång d­ thøc x2ºy2 mod N tõ k+1 thÆng d­ bËc hai t×m ®­îc trªn. C¬ së cña thuËt to¸n chñ yÕu dùa vµo thø nhÊt lµ kh¶ n¨ng t×m ®­îc k+1 thÆng d­ bËc hai vµ tiÕp ®Õn lµ viÖc x©y dùng ®ång d­ thøc x2ºy2 mod N nh­ thÕ nµo. Tr­íc hÕt chóng ta cïng xem xÐt ®Õn vÊn ®Ò thø hai. Gi¶ sö thÆng d­ bËc hai thø i t×m ®­îc ë trªn lµ ri=xi2=qa11.qa12...qakk( qj lµ sè nguyªn tè thø j cña B), ta ®Æt t­¬ng øng víi vÐc t¬ viÎGF(2)2 nh­ sau vi=(a1mod 2, a2 mod 2,..., ak mod 2). Chý ý r»ng cã thÓ cã nhiÒu gi¸ trÞ ri kh¸c nhau ®­îc øng cïng víi mét vÐc t¬ v nh­ng mét c¸ch h×nh thøc ta cã thÓ coi k+1 vÐc t¬ kh¸c nhau thu tõ viÖc øng k+1 gi¸ trÞ r cã ®­îc ë trªn. HiÓn nhiªn trong kh«ng gian k chiÒu GF(2)k th× tËp k+1 vÐc t¬ vi (i=1,2,...k+1) ch¾n ch¾n phô thuéc tuyÕn tÝnh, gi¶ sö ta cã tæ hîp tuyÕn tÝnh ®Æc tr­ng cho sù phô thuéc ®ã lµ: , víi q lµ vÐc t¬ kh«ng vµ ai kh«ng ®ång thêi b»ng kh«ng. Khi ®ã theo ®Þnh nghÜa sÏ lµ x2 mod N, mÆt kh¸c do ®iÒu kiÖn ®Æt ra ë trªn lµ Q(xi) ph©n tÝch ®­îc hoµn toµn trong tËp c¬ së cïng víi ®iÒu kiÖn tøc lµ vÕ ph¶i cña tÝch chøa toµn c¸c sè mò ch½n ®èi víi c¸c thõa sè trong c¬ së do vËy nã còng lµ mét thÆng d­ bËc hai y2 nµo ®ã. NÕu x¹±y mod N th× chóng ta sÏ thµnh c«ng trong viÖc ph©n tÝch N víi c¸c thõa sè t­¬ng øng lµ gcd(x±y, N). Ng­êi ta còng chØ ra r»ng kh¶ n¨ng thµnh c«ng x¶y ra víi x¸c suÊt lµ do vËy thêi gian tÝnh cña thuËt to¸n chñ yÕu phô thuéc tuyÕn tÝnh (th«ng th­êng b»ng phÐp khö Gauss). Víi viÖc t×m c¸c thÆng d­ bËc hai nhá tho¹t nhäön chóng ta nhËn thÊy r»ng do Q(x+rpa)º[(m+x+rpa )2-N mod Nº{[(m+x)2-N]+rpa[2(m+x)+rpa]}mod NºQ(x)+rpa[2(m+x)+rpa] mod N nªn: NÕu pa lµ ­íc cña Q(x) th× nã còng lµ ­íc cña Q(x+rpa) víi mäi sè nguyªn r. Tõ kÕt qu¶ trªn chóng ta thÊy r»ng nÕu tån t¹i gi¸ trÞ x theo yªu cÇu Q(x) ph©n tÝch hoµn toµn trong c¬ së vµ kh«ng qu¸ B th× ta cã thÓ t×m ®­îc nã chØ cÇn trong l©n cËn B cña 0. Ngoµi ra mét sè kÕt qu¶ (xem [Riesel]) kh¸c còng kh«ng kÐm phÇn quan träng ®ã lµ: §iÒu kiÖn cÇn vµ ®ñ ®Ó $x sao cho p lµ ­íc cña Q(x) lµ kÝ hiÖu Legendge (N/p)=1. Nh­ vËy kh«ng ph¶i toµn bé c¸c sè nguyªn tè trong ®Òu cÇn ph¶i ®­îc biÓu diÔn (®óng h¬n lµ chØ cã kho¶ng mét nöa sè nguyªn tè trong c¬ së lµ cã mÆt trong biÓu diÔn cña c¸c Q(x)) do ®ã ®Ó thu ®­îc hÖ phô thuéc tuyÕn tÝnh nªu trong ph©n tÝch trªn th× th­êng chØ cÇn sè ph­¬ng tr×nh kho¶ng giµ nöa sè c¸c nguyªn tè trong c¬ së lµ ®ñ. NÕu pº3 mod 4 th× gi¸ trÞ xºm±N(p+1)/4 mod p lµ c¸c gi¸ trÞ <p tho¶ m·n p lµ ­íc cña Q(x). NÕu pº1 mod 4 th× viÖc t×m c¸c gi¸ trÞ x t­¬ng tù cã thÓ b»ng mét thuËt to¸n gÇn ®a thøc. NÕu x<pa tho¶ m·n pa lµ ­íc cña Q(x) vµ pa+1 kh«ng lµ ­íc cña Q(x) th× gi¸ trÞ y<pa+1 cã pa+1 lµ ­íc cña Q(y) cã thÓ t×m ®­îc lµ y=x+rpa víi r lµ nghiÖm cña ph­¬ng tr×nh ®ång d­ bËc nhÊt sau mod p ( chó ý r»ng ph­¬ng tr×nh trªn lu«n lu«n cã duy nhÊt nghiÖm). Víi hai kÕt qu¶ trªn râ rµng chóng ta lu«n t×m ®­îc toµn bé gi¸ trÞ x trong mét ph¹m vi B cho tr­íc nµo ®ã mµ víi chóng Q(x) cã ­íc lÎ trong tËp c¬ së ph©n tÝch. Tr­êng hîp p=2 viÖc thu ®­îc kÕt qu¶ na n¸ nh­ trªn cã phøc t¹p h¬n, chóng t«i kh«ng ®ñ tµi liÖu ®Ó m« t¶ t­êng minh viÖc dß t×m ®ã ë ®©y. Tãm l¹i qu¸ tr×nh t×m c¸c thÆng d­ bËc hai nhá cã thÓ m« t¶ nh­ sau: - Chän mét ng­ìng B nµo ®ã vµ sµng ®Ó t×m c¸c gi¸ trÞ x nhá nhÊt < B mµ víi chóng pa lµ ­íc cña Q(x). - C¸c thÆng d­ bËc hai nhá Q(x)=R2=qa11.qa22...qakk, ë ®©y x0 lµ gi¸ trÞ nhá nhÊt ®Ó qa11.qa22...qakk lµ ­íc cña Q(x) mµ ta cã thÓ ph¸t hiÖn ®­îc ë b­íc trªn. TÊt c¶ c¸c ph©n tÝch ®­îc nªu ë trªn mÆc dï ch­a ®ñ chÆt chÏ cho sù ®¶m b¶o thµnh c«ng cña viÖc t×m c¸c thÆng d­ bËc hai nhá trong líp Q(x) mµ chØ dõng ë møc ®é thÓ hiÖn mét m« t¶ b­íc t×m kiÕm nµy sÏ ®­îc th«ng qua mét qu¸ tr×nh “sµng” theo c¬ së cña nh÷ng kÕt qu¶ nªu trªn nh»m lo¹i bá c¸c gi¸ trÞ kh«ng thÓ lµ øng cö viªn cho c¸c thÆng d­ bËc hai nhá. Mét sè tµi liÖu (xem [Dixon], [Lenstra],...) ®· ph©n tÝch vÒ thêi gian tÝnh cña thuËt to¸n vµ sè liÖu kh¶ quan nhÊt vÒ vÊn ®Ò nµy cña Lenstra lµ: víi O(1) lµ mét hµm tiÕn tíi 0 khi N tiÕn tíi ¥. 3.4 ThuËt to¸n Dixon vµ sµng bËc hai ThuËt to¸n Dixon ®­îc x©y dùng trªn ý t­ëng ®ã lµ: nÕu t×m ®­îc x ¹ ±y (mod n) sao cho x2ºy2 (mod n) th× UCLN(x-y,n) lµ ­íc kh«ng tÇm th­êng cña n. Ph­¬ng ph¸p nµy sö dông c¬ së nh©n tö lµ mét tËp b chøa c¸c sè nguyªn tè bÐ. Tr­íc tiªn ta nhËn ®­îc mét vµi sè nguyªn x sao cho tÊt c¶ c¸c thõa sè nguyªn tècña x2 (mod n) n»m trong c¬ së b (c¸ch thùc hiÖn ®iÒu nµy sÏ ®­îc th¶o luËn sau). ý t­ëng thùc hiªn ë ®©y lµ lÊy tÝch cña mét vµi gi¸ trÜ sao cho mçi sè nguyªn tè trong c¬ së ®­îc sö dông mét sè ch½n lÇn. §iÒu nµy dÉn ®Õn mét ®ång d­ thøc d¹ng mong muèn x2 º y2 (mod n) mµ ta hy väng sÏ ®­a ®Õn viÖc ph©n tÝch n. Ta sÏ minh ho¹ b»ng mét vÝ dô ®· ®­îc dù tÝnh kü l­ìng. VÝ dô : Gi¶ sö n=15770708441. Gi¶ sö b = {2,3,5,7,11,13}. XÐt ba ®ång thøc sau: 83409341562 º 3 ´ 7 (mod n) 120449429442 º 1 ´ 7 ´ 13 (mod n) 27737000112 =2 ´ 3 ´ 13 (mod n) NÕu lÊy tÝch cña ba ®ång d­ thøc trªn: (8340934156 ´ 2044942944´2773700011)2 º(2´ 3´ 7´ 13)2 (mod n) Rót gän c¸c biÓu thøc bªn trong c¸c dÊu ngÆc theo modulo n, ta cã: 95034357852 º 5462 (mod n) Sau ®ã tÝnh: UCLN(9503435785-546, 15770708441)=115759 Ta thÊy 115759 lµ mét thõa sè cña n. Gi¶ sö B = {p1, . . . .pB}lµ mét c¬ së nh©n tö. Gi¶ sö c lín h¬n B mét chót (ch¼ng h¹n C=B+10) vµ gi¶ sö ta ®· cã C ®ång d­ thøc: xj2 º p1a1j ´ p2a2j ´ . . .´ pBaBj(mod n) víi 1£ j £ C. Víi mçi j xÐt vÐctor : aj = (a1j mod 2, a2j mod 2, . . ., aBj mod 2) Î (Z2)B NÕu cã thÓ t×m ®­îc mét tËp con c¸c aj sao cho tæng theo modulo 2 lµ vector (0,. . ., 0) th× tÝch cña c¸c xj t­¬ng øng sÏ sö dông mçi nh©n tö trong B mét sè ch½n lÇn. Ta sÏ minh ho¹ b»ng c¸ch trë l¹i vÝ dô trªn. Trong tr­êng hîp nµy nÕu C < B, vÉn t×m ®­îc sù phô thuéc tuyÕn tÝnh. VÝ dô :(tiÕp) Cho 3 vector a1, a2, a3 : a1 =(0, 1, 0, 1, 0, 0) a2 =(1, 0, 0, 1, 0, 1) a3 = (1, 1, 0, 0, 0, 1) DÔ dµng thÊy r»ng: a1 +a2 + a3 = (0, 0, 0, 0, 0, 0) mod 2 §©y lµ lý do cho thÊy ®ång d­ thøc (thiÕt lËp theo tÝch) sÏ ph©n tÝch thµnh c«ng ®­îc n. NhËn thÊy r»ng, bµi to¸n t×m mét tËp con C vector a1, a2, . . ., aC sao cho tæng theo modulo 2 lµ mét vector toµn chøa sè 0 chÝnh lµ bµi to¸n t×m sù phô thuéc tuyÕn tÝnh (trªn Z2) cña c¸c vector nµy. Víi C > B, sù phô thuéc tuyÕn tÝnh nµy nhÊt ®Þnh ph¶i tån t¹i vµ ta cã thÓ dÔ dµng t×m ®­îc b»ng ph­¬ng ph¸p lo¹i trõ Gaux. Lý do gi¶i thÝch t¹i sao lÊy C > B+1 lµ do kh«ng cã g× b¶o ®¶m ®Ó mét ®ång d­ thøc cho tr­íc bÊt kú sÏ t¹o ®­îc ph©n tÝch n. Kho¶ng 50% thuËt to¸n cho ra x º ±y (mod n). Tuy nhiªn nÕu C > B+1 th× cã thÓ nhËn ®­îc mét vµi ®ång d­ thøc nh­ vËy. (N¶y sinh tõ c¸c phô thuéc tuyÕn tÝnh kh¸c cña c¸c aj). Hy väng lµ Ýt nhÊt mét trong c¸c ®ång d­ thøc kÕt qu¶ sÏ dÉn ®Õn viÖc ph©n tÝch n. VÊn ®Ò cßn l¹i lµ ph¶i lµm thÕ nµo ®Ó nhËn ®­îc c¸c sè nguyªn xj mµ c¸c gi¸ trÞ xj2 mod n cã thÓ ph©n tÝch hoµn toµn trªn c¬ së b. Mét vµi ph­¬ng ph¸p cã thÓ thùc hiÖn ®­îc ®iÒu ®ã. BiÖn ph¸p sµng bËc hai do Pomerance ®­a ra dïng c¸c sè nguyªn d¹ng xj=j + ,j=1,2...... Tªn “sµng bËc hai” lÊy tõ thñ tôc sµng (kh«ng m« t¶ ë ®©y) dïng ®Ó x¸c ®Þnh c¸c xj ph©n tÝch ®­îc trªn b. ë ®©y dÜ nhiªn lµ mét sù tho¶ hiÖp: nÕu B = | B | lµ mét sè lín th× thÝch hîp h¬n c¶ lµ nªn ph©n tÝch sè nguyªn xj trªn b. Tuy nhiªn khi B cµng lín th× ta cµng ph¶i gom nhiÒu ®ång d­ thøc h¬n tr­íc khi cã thÓ t×m ®­îc mét quan hÖ phô thuéc. 3.5 Ph­¬ng ph¸p p-1: ThuËt to¸n Pollard thø nhÊt ThuËt to¸n kiÓu p-1 lµ thuËt to¸n ph©n tÝch sè nguyªn N dùa vµo ph©n tÝch cña p-1 víi p lµ mét ­íc nguyªn tè cña N. ThuËt to¸n cßn ®­îc gäi lµ thuËt to¸n ph©n tÝch thø nhÊt cña Pollard, ®©y lµ mét thuËt to¸n cã t¸c dông nÕu ta biÕt ®­îc c¸c ­íc nguyªn tè cña mét thõa sè p cña N nãi chung vµ ®Æc biÖt nÕu N cã mét thõa sè nguyªn tè p mµ p-1 chØ gåm nh÷ng ­íc nguyªn tè nhá th× thuËt to¸n ®­îc tr×nh bµy trong phÇn nµy sÏ cã hiÖu qu¶. ý t­ëng cña thuËt to¸n lµ t×m mét c¸ch ngÉu nhiªn sè aÎZ*n cã bËc kh«ng lµ ­íc cña p-1. Sè a nÕu t×m ®­îc hiÓn nhiªn ph¶i tho¶ m·n bºap-1 mod N#1, ®iÒu nµy cã ý nghÜa N kh«ng lµ ­íc cña b-1. MÆt kh¸c do p nguyªn tè nªn theo ®Þnh lý Fermat ta cã b mod pº(ap-1 mod N) mod p=1 nh­ vËy b-1 º0 mod p vµ do ®ã cã ngay p | gcd(b-1,N). Hai ®iÒu kÐo theo p=gcd(b-1,N). Mét sè vÊn ®Ò ch­a t­êng minh trong viÖc thùc hiÖn nãi trªn lµ: Do p lµ sè ch­a biÕt nªn dÊu hiÖu nhËn biÕt gi¸ trÞ a cÇn t×m lµ ap-1 mod N#1 còng ch­a x¸c ®Þnh. TÊt nhiªn ë ®©y ®iÒu kiÖn nhËn biÕt cã thÓ ®­îc lµm “nhÑ” bít ®ã lµ ta cã thÓ thay sè p-1 ch­a biÕt b»ng sè Q gi¶ ®Þnh cã thÓ lµ chän tr­íc vµ tÝnh bºaQ mod N, nÕu N>gcd(b-1, N)>0 th× viÖc chän cña chóng ta ®· thµnh c«ng vµ cã p=gcd(b-1, N). HiÓn nhiªn viÖc gi¶ ®Þnh Q chØ cã nghÜa khi vµ chØ khi p-1 lµ ­íc cña Q, trong tr­êng hîp p-1 chØ cã c¸c ­íc nguyªn tè nhá tøc lµ p-1=. TÊt nhiªn c¸c sè mò trong khai triÓn cña Q lµ qu¸ d­ thõa do ®ã c¸c lùa chän tiÕp theo cña chóng ta sÏ lµ cè gi¶m c¸c sè mò nµy ®Õn møc thÊp nhÊt cã thÓ, c¸ch lµm cô thÓ cho viÖc nµy sÏ ®­îc m« t¶ cô thÓ trong thuËt to¸n. VÊn ®Ò kÕ tiÕp lµ viÖc t×m kiÕm cã kh¶ thi hay kh«ng, nãi mét c¸ch kh¸c chóng ta ph¶i tr¶ lêi c©u hái “ liÖu cã tån t¹i hay kh«ng sè a cã bËc kh«ng lµ ­íc cña p-1?”. Tr­íc hÕt chóng ta giíi h¹n ph¹m vi sè N cÇn ®­îc ph©n tÝch lµ N=pq víi p vµ q lµ c¸c sè nguyªn tè kh¸c nhau, khi nµy bËc cao nhÊt cña c¸c phÇn tö trong Z*N sÏ lµ g(N)=1cm(p-1, q-1). Do p kh¸c q nªn ch¾c ch¾n hoÆc p-1 hoÆc q-1 lµ ­íc thùc sù cña g(N) vµ c©u hái ®· ®­îc tr¶ lêi “cã”. §Õn ®©y møc ®é “khã hay dÔ” cña viÖc t×m ®­îc sè a sÏ liªn quan ®Õn mËt ®é nµy nh­ sau: MËt ®é nãi trªn sÏ nghÞch biÕn víi gcd(p-1,q-1). Nh­ vËy nÕu gcd(p-1,q-1) nhá th× viÖc t×m ra a sÏ thuËn lîi, ng­îc l¹i trong tr­êng hîp khã kh¨n h¬n (gcd(p-1,q-1) lín) th× trong phÇn 2.3 sau nµy chóng t«i sÏ chØ ra mét ph­¬ng ph¸p ph©n tÝch hiÖu qu¶ h¬n. C¸c b­íc cña thuËt to¸n Pollard. (dïng ®Ó ph©n tÝch N cã ­íc p víi p-1 chØ gåm c¸c ­íc nguyªn tè trong k sè nguyªn tè ®Çu tiªn). (1) Q=, i=1,j=0. (2) LÊy a ngÉu nhiªn trong Z*N, tÝnh bºaQ mod N. (3) XÐt ®¼ng thøc b=1. NÕu ®óng chuyÓn sang (4). Ng­îc l¹i chuyÓn sang (6). (4) XÐt j<logqiN. NÕu ®óng th× j=i+