Các hệ thống khóa công khai thác phần 5

Ta chỉ cần xem xét các đa thức có thành phần hằng số bằng 1 vì một đa thức bất kì có thành phần hằng số bằng 0 sẽ chia hết cho x và bởi vậy nó là một đa thức bất khả quy .
Nội dung trích xuất từ tài liệu:
Các hệ thống khóa công khai thác phần 5Vietebooks Nguyễn Hoàng Cương X©y dùng mét tr−êng 8 phÇn tö. §iÒu nµy cã thÓ thùc hiÖn b»ng c¸cht×m mét ®a thøc bÊt kh¶ quy bËc 3 trong Z2[x]. Ta chØ cÇn xem xÐt c¸c ®athøc cã thµnh phÇn h»ng sè b»ng 1 v× mét ®a thøc bÊt k× cã thµnh phÇn h»ngsè b»ng 0 sÏ chia hÕt cho x vµ bëi vËy nã lµ mét ®a thøc bÊt kh¶ quy . Cã tÊtc¶ 4 ®a thøc nh− vËy. f1(x) = x3 + 1 f2(x) = x3 + x + 1 f3(x) = x3 + x2 + 1 f4(x) = x3 + x2 + x + 1XÐt thÊy f1(x) lµ kh¶ quy v×: x3 +1 = (x+1)(x2+x+1)(cÇn ®Ó ý lµ tÊt c¶ c¸c hÖ sè ®−îc rót gän theo modulo 2). T−¬ng tù, f4(x)còng kh¶ quy v×: x3+x2+x+1 = (x+1)(x2+1)Tuy nhiªn c¶ hai ®a thøc f2(x) va f3(x) l¹i ®Òu lµ ®a thøc bÊt kh¶ quy vµ cãthÓ dïng hai ®a thøc nµy ®Ó x©y dùng tr−êng 8 phÇn tö . Gi¶ sö dïng f2(x) ®Ó x©y dùng tr−êng Z2[x]/(x3+x+1). 8 phÇn tö cñatr−êng lµ 8 ®a thøc : 0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1 §Ó tÝnh tÝch cña hai phÇn tö cña tr−êng, nh©n hai ®a thøc víi nhau vµrót gän theo modulo x3+x+1 (tøc chia cho (x3+x+1) vµ t×m ®a thøc d−). V× tachia mét ®a thøc bËc 3 nªn ®a thøc d− cã bËc nhiÒu nhÊt lµ 2 vµ v× thÕ nã lµmét phÇn tö cña tr−êng. VÝ dô, ta h·y tÝnh (x2+1)(x2+x+1) trong Z2[x]/(x3+x+1). Tr−íc hÕt tÝnhtÝch trong Z2[x] lµ x4+x3+x+1. Khi chia cho x3+x+1, ta nhËn ®−îc biÓu thøcsau: x4+x3+x+1 = (x+1)(x3+x+1) +x2+xBëi vËy, trong tr−êng Z2[x]/(x3+x+1) ta cã : (x2+1)(x2+x+1) = x2+x Trang 21Vietebooks Nguyễn Hoàng CươngD−íi ®©y sÏ ®−a ra b¶ng dÇy ®ñ cho c¸ phÇn tö kh¸c 0 cña tr−êng. §Ó ®¬ngi¶n, ta viÕt ®a thøc : a2x2+a1x+a0 theo bé ba ®−îc s¾p a2a1a0. 001 010 011 100 101 110 111 001 001 010 011 100 101 110 111 010 010 100 110 011 001 111 101 011 011 110 101 111 100 001 010 100 100 011 111 110 010 101 001 101 101 001 100 010 111 011 110 110 110 111 001 101 011 010 100 111 111 101 010 001 110 100 011 ViÖc tÝnh c¸c phÇn tö nghÞch ®¶o ®−îc tùc hiÖn theo thuËt to¸n Euclidemë réng cã biÕn ®æi ®«i chót. Cuèi cïng, ta th©ý r»ng nhãm nh©n cña c¸c ®a thøc kh¸c 0 trongtr−êng lµ mét nhãm cyclic cÊp 7. V× 7 lµ sè nguyªn tè nªn suy ra mäi phÇntö kh¸c 0 cña tr−êng ®Òu lµ phÇn tö sinh cña nhãm nµy (tøc lµ phÇn tönguyªn thuû).VÝ dô, nÕu tÝnh c¸c luü thõa cña x, ta cã: x1 = x x2 =x2 x3 = x+1 x4 = x2+1 x5 = x2+ x+1 x6 = x2+1 x7 = 1sÏ bao gåm tÊt c¶ c¸c phÇn tö kh¸c 0 cña tr−êng. VÊn ®Ò cßn l¹i lµ sù tån t¹i vµ tÝnh duy nhÊt cña c¸c tr−êng d¹ng nµy.Cã thÓ chØ ra r»ng, cã Ýt nhÊt mét ®a thøc bÊt kh¶ quy bËc bÊt k× n ≥1 trongZp[x]. Bëi vËy, sÏ cã mét tr−êng h÷u h¹n pn phÇn tö ®èi víi mäi nguyªn tè pvµ mäi sè nguyªn n≥1. Th«ng th−¬ng cã kh¸ nhiÒu ®a thøc bÊt kh¶ quy bËc ntrong Zp[x]. Tuy nhiªn, nh÷ng tr−êng h÷u h¹n ®−îc x©y dùng tõ hai ®a thøcbÊt kh¶ quy bÊt k× bËc n ®Òu cã thÓ chøng tá ®−îc chóng lµ ®aöng cÊu víinhau. Bëi vËy, chØ cã mét tr−¬ng h÷u h¹n duy nhÊt cÊp pn tuú ý (p - sènguyªn tè, n≥ 1) lµ tr−êng GF(pn). Trong tr−êng hîp n = 1, tr−¬ng GF(p)còng chÝnh lµ Zp. Cuèi cïng, cã thÓ chØ ra r»ng, kh«ng tån t¹i mét tr−êng h÷u Trang 22Vietebooks Nguyễn Hoàng Cươngh¹n r phÇn tö trõ phi r = pn víi p lµ sè nguyªn tè , n lµ sè nguyªn nµo ®ã(n≥1). Ta ®· nhËn thÊy lµ nhãm nh©n Zp* (p - sè nguyªn tè) lµ mét nhãmcyclic cÊp p-1. Thùc tÕ, nhãm nh©n cña tr−êng h÷u h¹n bÊt k× ®Òu lµ nhãmcyclic: GF(pn){0} lµ mét nhãm cyclic cÊp pn-1. Nhãm nµy sÏ cho c¸c vÝ dôvÒ c¸c nhãm cyclic trong ®ã bµi to¸n DL cã thÓ ®−îc nghiªn cøu. Thùc tÕ c¸c tr−êng h÷u h¹n GF(2n) ®· ®−îc nghiªn cøu kh¸ kÜ. C¶ haithuËt to¸n logarithm rêi r¹c Shanks vµ Pohlig-Hellman ®Òu lµm viÖc trªn c¸ctr−êng GF(2n). Ph−¬ng ph¸p tÝnh to¸n chØ sè cã thÓ söa ®æi ®Ó lµm viÖc trªnc¸c tr−¬ng nµy. Thêi gian tiÒn tÝnh to¸n cña thuËt to¸n tÝnh to¸n chØ sèkho¶ng ( ) O e (1, 405+O (1))n (ln n ) 2/ 3 1/ 3cßn thêi gian ®Ó t×m mét gi¸ trÞ logarithm rêi r¹c riªng kho¶ng ( ) O e (1, 098+O (1))n (ln n ) ...