Các thuật toán phân tích thừa số

Đã có một khối lượng khổng lồ các tìa 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 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 tichs thừa số tốt nhất hiện thời và cách sử dụng chúng trong thực tế. Ba thuật toán hiệu quả nhất trên các số thật lớn là sàng bậc hai, thuật toán đường cong elliptic và sàng trường số....
Nội dung trích xuất từ tài liệu:
Các thuật toán phân tích thừa số H×nh 4.14. Ph©n tÝch modulus cña rabin víi mét ch¬ng tr×nh con gi¶i m· cho tríc. 1. Chän mét sè ngÉu nhiªn r , 1≤ r ≤ n- 1 2- 2 2. TÝnh y = r B /4 mod n 3. Gäi ch¬ng tr×nh con A(y) ®Ó t×m b¶n gi¶i m· x 4. TÝnh x1 = x+B/2 5. If x1 ≡ ± r (mod n) then quit (kh«ng thµnh c«ng) Else UCLN(x1+r,n)=p hoÆc q (thµnh c«ng)Bëi vËy gi¸ trÞ x sÏ thu ®îc ë bíc 3. TiÕp theo xÐt bíc 4. NhËnthÊy r»ng x12 = r2 (mod n). §iÒu ®ã dÉn tíi x1 ≡ ± r (mod n)hoÆc x1 ≡ ± wr (mod n), trong ®ã w lµ mét trong c¸c c¨n bËchai kh«ng tÇm thêng cña 1 modulo n. Trong trêng hîp thø haita cã : n 1-r )(x1+r) (xsong n kh«ng ph¶i lµ íc cña mét thõa sè nµo ë vÕ ph¶i. BëivËy, viÖc tÝnh UCLN(x1 +r,n)(hoÆc UCLN(x1-r, n)) ph¶i dÉntíi hoÆc p hoÆc q, vµ nh vËy phÐp ph©n tÝch n ®îc hoµnthµnh. Ta sÏ tÝnh x¸c suÊt thµnh c«ng cña thuËt to¸n nµy trªntÊt c¶ (n-1) phÐp chän ngÉu nhiªn r. Víi hai thÆng d kh¸ckh«ng r1 vµ r2 , ®Þnh nghÜa: r1 ~ r2 ⇔ r12 ≡ r22 (mod n) DÔ dµng thÊy r»ng r ~ r víi mäi r, r1 ~ r2 còng cã nghÜa lµr2 ~ r1; r1 ~ r2 vµ r2 ~ r3 th× r1 ~ r3 . §iÒu ®ã cho ta thÊy r»ngquan hÖ ~ lµ mét quan hÖ t¬ng ®¬ng. C¸c líp t¬ng ®¬ng cñaZn{0} ®Òu cã bèn phÇn tö, líp t¬ng ®¬ng chøa r lµ tËp [r] = {± r, ± wr (mod n)}trong ®ã w lµ c¨n bËc hai kh«ng tÇm thêng cña 1 modulo n. Trong thuËt to¸n ®îc tr×nh bµy ë h×nh 4.14, hai gi¸ trÞ rbÊt kú trong cïng mét líp t¬ng ®¬ng sÏ dÉn tíi cïng mét gi¸ trÞy. B©y giê xÐt gi¸ trÞ x thu ®îc tõ ch¬ng tr×nh con A khi ®·biÕt y. Ta cã: [y]={± y, ± wy}NÕu r=± y th× thuËt to¸n kh«ng thµnh c«ng; trong khi nÕur=± wy th× thuËt to¸n sÏ thµnh c«ng. V× r ®îc chän ngÉu nhiªn,nªn mét gi¸ trÞ bÊt kú trong bèn gi¸ trÞ cã thÓ ®Òu cïng kh¶n¨ng. Ta kÕt luËn r»ng x¸c suÊt thµnh c«ng cña thuËt to¸n lµ1/2. §iÒu thó vÞ lµ hÖ mËt rabin lµ an toµn ®èi víi ph¬ngph¸p tÊn c«ng b¶n râ chän läc, mhmg hÖ nµy l¹i hoµn toµnkh«ng an toµn®èi víi ph¬ng ph¸p tÊn c«ng b¶m m· chän läc.ThuËt to¸n ë h×nh 4.14, phÇn dïng ®Ó chøng minh sù an toµn®èi víi phÐp tÊn c«ng b¶n râ chän läc còng cã thÓ ®îc dïng®Ó ph¸ hÖ mËt Rabin khi thùc hiÖn tÊn c«ng b¶n m· chänläc!. Trong ph¬ng ph¸p tÊn c«ng b¶n m· chän läc, ch¬ng tr×nhcon A ®îc thay b»ng thuËt to¸n gi¶i m· cña Bob.4.8. C¸c thuËt to¸n ph©n tÝch thõa sè. §· cã mét khèi lîng khæng lå c¸c t×a liÖu vÒ c¸c thuËtto¸n ph©n tÝch thõa sè vµ viÖc nghiªn cøu kü lìng sÏ ®ßi háiph¶i cã mét cuèn s¸ch dµy 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 tichs thõa sè tèt nhÊt hiÖn thêi vµc¸ch sö dông chóng trong thùc tÕ. Ba thuËt to¸n hiÖu qu¶nhÊt trªn c¸c sè thËt lín lµ sµng bËc hai, thuËt to¸n ®êng congelliptic vµ sµng trêng sè. C¸c thuËt to¸n næi tiÕng kh¸c (nh÷ngthuËt to¸n to¸n cã tríc) bao gåm ph¬ng ph¸p ρ vµ thuËt to¸n p-1cña Pollard, thuËt to¸n p+1 cña Williams, thuËt to¸n liªn ph©nsè vµ dÜ nhiªn c¶ nh÷ng phÐp chia thö. Trong toµn bé phÇn nµy, xchóng ta cá×ng sè nguyªn ncÇn ph©n tÝch ra thõa sè lµ mét sè lÎ. PhÐp chia thö bao gåmviÖc chia ncho tõng sè nguyªn lÎ cho tíi [ n] . NÕu n < 10 12 th× ®©y lµmétph¬ng ph¸p ph©n tÝch thõa sè hîp lý mét c¸ch hoµn h¶o, tuynhiªn víi n lín h¬n nãi chung ta ph¶i dïng c¸c kü thuËt tinh tÕh¬n.4.8.1. Ph¬ng ph¸p p-1 ThuËt to¸n p-1 cña Pollar (®a ra vµo n¨m 1947) lµ métthÝ dô vÒ mét thuËt to¸n ®¬n gi¶n ®¬n khi ®îc ¸p dông víi c¸csè nguyªn lín. ThuËt to¸n nµy (tr×nh bµy trªn h×nh 4.15) cã hai®Çu vµo: sè nguyªn lÎ n cÇn ®îc ph©n tÝch vµ mét cËn B. CãthÓ m« t¶ thuËt to¸n nh sau: H×nh 4.15. ThuËt to¸n ph©n tÝch thõa sè p-1. §Çu vµo: n vµ B 1. a=2 2. For j=2 to B do a = aj mod n 3. d = UCLN(a-1,n) 4. if 1 < d < n then d lµ mét thõa sè cña n else kh«ng t×m ®îc thõa sè cña n (kh«ng thµnh c«ng) Gi¶ sö p lµ íc mhuyªn tè cña n vµ q ≤ B , víi mçi mònguyªn tè p(p-1). Khi ®ã (p-1)B! ë cuèi vßng lÆp for (bíc 2) a ≡ 2B! (mod n) nªn a ≡ 2B! (mod p) v× p nªn theo ®Þnh ý Fermat ta cã : n. ≡  ≡   ≡ 135979 × 115979Trong trêng hîp nµy, phÐp ph©n tÝch sÏ thµnh c«ng do135978 chØ gåm c¸c thõa sè nguyªn tè nhá:V× thÕ 135978 = 2 × 3 × 131 × 173nÕu lÊy B ≥ 173 th× ch¾c ch¨n r»ng 135978 nh mong B!muèn. ...