Nội dung tài liệu: Một số ứng dụng của số học trong lý thuyết mật mã
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC **************** VŨ THỊ THANH HẬU MỘT SỐ ỨNG DỤNG CỦA SỐ HỌC TRONG LÝ THUYẾT MẬT Mà LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC **************** VŨ THỊ THANH HẬU MỘT SỐ ỨNG DỤNG CỦA SỐ HỌC TRONG LÝ THUYẾT MẬT Mà Chuyên ngành : Phương pháp toán sơ cấp Mã số : 60.46.40 LUẬN VĂN THẠC SĨ KHOA HỌC TOÁN HỌC Người hướng dẫn khoa học : GS.TSKH. Hà Huy Khoái Thái Nguyên, năm 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Môc lôc Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 Mét sè kiÕn thøc c¬ b¶n 5 1.1 ThuËt to¸n vµ ®é phøc t¹p cña thuËt to¸n . . . . . . . . . . . . . . . . . . . . 5 1.1.1 Kh¸i niÖm: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 §é phøc t¹p cña thuËt to¸n . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 PhÐp tÝnh ®ång d vµ c¸c vÊn ®Ò liªn quan . . . . . . . . . . . . . . . . . . . 10 1.2.1 Sè nguyªn tè vµ ®Þnh lý c¬ b¶n cña sè häc . . . . . . . . . . . . . . . 10 1.2.2 ThuËt to¸n Euclid vµ më réng . . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Phi - hµm Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.4 PhÐp tÝnh ®ång d vµ ph¬ng tr×nh ®ång d . . . . . . . . . . . . . . 13 1.2.5 §Þnh lý Fermat vµ c¸c më réng . . . . . . . . . . . . . . . . . . . . . 14 1.2.6 TÝnh to¸n víi ®ång d cña luü thõa bËc lín . . . . . . . . . . . . . . . 15 1.2.7 ThÆng d b×nh ph¬ng vµ ký hiÖu Legendre . . . . . . . . . . . . . . . 16 1.3 Ph©n sè liªn tôc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.1 Kh¸i niÖm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3.2 TÝnh chÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Mét sè øng dông cña sè häc trong lý thuyÕt mËt m· 21 2.1 Nguyªn t¾c chung vµ mét sè hÖ m· ®¬n gi¶n . . . . . . . . . . . . . . . . . . 21 2.1.1 HÖ m· Ceasar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1.2 HÖ M· Khèi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Mét sè hÖ m· mò th«ng dông . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 HÖ m· mò cña Pohligvµ Hellman . . . . . . . . . . . . . . . . . . . . 26 2.2.2 Giao thøc trao ®æi ch×a kho¸ cña Diffie - Hellman . . . . . . . . . . . 29 2.2.3 HÖ m· ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.4 HÖ m· RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Ph©n tÝch ra thõa sè nguyªn tè . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.1 Ph©n tÝch Fermat vµ më réng cña nã . . . . . . . . . . . . . . . . . . 35 2.3.2 Ph©n tÝch sö dông liªn ph©n sè. . . . . . . . . . . . . . . . . . . . . . 40 2.3.3 Ph©n tÝch dïng ph¬ng ph¸p cña Pollard . . . . . . . . . . . . . . . . . 43 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Lêi c¶m ¬n LuËn v¨n nµy ®îc hoµn thµnh díi sù híng dÉn tËn t×nh vµ nghiªm kh¾c cña GS.TSKH. Hµ Huy Kho¸i. Nh©n dÞp nµy, t«i xin bµy tá lßng kÝnh träng vµ biÕt ¬n s©u s¾c tíi GS.TSKH. Hµ Huy Kho¸i, ngêi ThÇy mÉu mùc ®· giµnh nhiÒu thêi gian vµ c«ng søc ®Ó híng dÉn t«i hoµn thµnh luËn v¨n nµy. T«i xin ch©n thµnh c¶m ¬n Trung t©m §µo t¹o sau ®¹i häc, Phßng §¹i sè, Trêng §¹i häc Khoa häc - §¹i häc Th¸i Nguyªn, Së Gi¸o dôc vµ §µo t¹o tØnh Qu¶ng Ninh, Trung t©m Híng nghiÖp vµ Gi¸o dôc thêng xuyªn tØnh Qu¶ng Ninh, ®· t¹o ®iÒu kiÖn thuËn lîi ®Ó t«i hoµn thµnh luËn v¨n nµy. Nh©n dÞp nµy, t«i xin bµy tá lßng biÕt ¬n tíi c¸c Gi¸o s, Phã gi¸o s, TiÕn sÜ cña ViÖn To¸n häc vµ Trêng §¹i häc Khoa häc - §¹i häc Th¸i Nguyªn, nh÷ng ngêi thÇy ®· tËn t×nh gi¶ng d¹y vµ t¹o mäi ®iÒu kiÖn thuËn lîi cho t«i hoµn thµnh kho¸ häc. T«i còng xin c¶m ¬n b¹n bÌ vµ gia ®×nh ®· ®éng viªn vµ gióp ®ì t«i trong suèt qu¸ tr×nh häc tËp t¹i Trêng §¹i häc Khoa häc - §¹i häc Th¸i Nguyªn. 2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Lêi nãi ®Çu Tríc nh÷ng n¨m 70 cña thÕ kû XX, Sè häc thêng ®îc xem lµ mét trong nh÷ng ngµnh to¸n häc thuÇn tuý, chØ cã ý nghÜa lý thuyÕt. §èi tîng nghiªn cøu cña Sè häc lµ c¸c quy luËt trong tËp hîp sè, gi¶ thuyÕt lín tån t¹i trong Sè häc lµ c¸c gi¶ thuyÕt sè nguyªn tè. ThËm chÝ, cã nh÷ng nhµ to¸n häc cho r»ng vÎ ®Ñp cña Sè häc cã ®îc nhê sù xa rêi thùc tiÔn cña nã! (theo c©u nãi cña G.H. Hardy, A Mathematician's Apology, 1940). Ngµy nay, thËt khã ®ång ý víi Hardy, khi mµ vÎ ®Ñp cña Sè häc kh«ng chØ thÓ hiÖn trong ý nghÜa "thuÇn tuý" cña nã, mµ c¶ trong nh÷ng øng dông bÊt ngê vµo thùc tiÔn. C¸ch ®©y kho¶ng 30 n¨m, khã cã thÓ h×nh dung ®îc r»ng, mét sè kÕt qu¶ lý thuyÕt sè trong Sè häc l¹i lµm nªn mét cuéc c¸ch m¹ng trong b¶o mËt th«ng tin. C¬ së cña nh÷ng øng dông ®ã l¹i chÝnh lµ Sè häc thuËt to¸n, lÜnh vùc nghiªn cøu c¸c thuËt to¸n trong Sè häc. Cã thÓ nãi, mËt m· ®· cã tõ thêi cæ ®¹i. Ngêi ®Çu tiªn ¸p dông mËt m· mét c¸ch cã hÖ thèng ®Ó ®¶m b¶o bÝ mËt th«ng tin qu©n sù lµ nhµ qu©n sù thiªn tµi cña ngêi La M· cæ ®¹i, Julius Caesar. HÖ m· cæ nhÊt lµ hÖ m· Ceasar, th«ng qua phÐp m· thay thÕ mçi ký tù thay bëi ký tù ®øng ngay sau nã 3 vÞ trÝ (hoÆc k vÞ trÝ). Vµo nh÷ng n¨m ®Çu thÕ kû XX hÖ m· míi cã tÝnh b¶o mËt cao h¬n ®îc xuÊt hiÖn víi sù ra ®êi cña hÖ m· British Playfair n¨m 1910, ®ã lµ m· khèi th«ng qua phÐp thay thÕ theo ch×a. Song song víi qu¸ tr×nh ph¸t triÓn cña lÞch sö vµ nhu cÇu vÒ b¶o mËt th«ng tin trªn nhiÒu lÜnh vùc ®· thóc ®Èy c¸c hÖ m· míi ra ®êi cã tÝnh b¶o mËt ngµy cµng cao, nh hÖ m· mò cña Pohlig vµ Hellman (n¨m 1978), tiÕp theo lµ giao thøc trao ®æi ch×a kho¸ cña Diffie- Hellman, sau n÷a lµ hÖ m· ElGamal. Mét nÐt chung cña hai hÖ m· trªn lµ 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn cho phÐp c«ng bè c«ng khai mét phÇn th«ng tin cho viÖc lËp m· gäi lµ m· ho¸ víi kho¸ c«ng khai, mét m« h×nh hoµn h¶o cho hÖ m· kiÓu nµy ®îc c«ng bè bëi Rivest, Shamir vµ Adleman vµo n¨m 1978, mang tªn RSA. HÖ m· RSA vÉn ®ang lµ mét th¸ch thøc lín ®èi víi nh÷ng nhµ th¸m m·. Môc ®Ých cña b¶n luËn v¨n nµy nh»m tr×nh bµy c¬ së cña viÖc ¸p dông lý thuyÕt sè vµo mËt m·, ®Æc biÖt lµ m· ho¸ RSA vµ mét sè thuËt to¸n ph©n tÝch sè nguyªn ®ang sö dông trong th¸m m·. LuËn v¨n gåm hai ch¬ng. Ch¬ng I tr×nh bµy c¸c kiÕn thøc chuÈn bÞ phôc vô cho ch¬ng sau nh c¸c kh¸i niÖm vÒ thuËt to¸n, ®é phøc t¹p cña thuËt to¸n, c¸c kiÕn thøc vÒ ®ång d vµ ph©n sè liªn tôc. Ch¬ng II tr×nh bµy mét sè hÖ m· ®¬n gi¶n, hÖ m· th«ng dông, hÖ m· RSA vµ øng dông cña sè häc vµo mËt m· kho¸ c«ng khai nh ph©n tÝch Fecmat, ph©n tÝch Fecmat më réng, ph©n tÝch sö dông ph©n sè liªn tôc, ph©n tÝch dïng ph¬ng ph¸p cña Pollard. Tõ ®ã viÕt mét sè thñ tôc ph©n tÝch sè, thñ tôc lËp m· vµ gi¶i m· ch¹y trªn Maple. 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Ch¬ng 1 Mét sè kiÕn thøc c¬ b¶n Trong ch¬ng nµy chóng t«i tr×nh bµy mét sè kiÕn thøc chuÈn bÞ. TiÕt 1.1 nh¾c l¹i c¸c kh¸i niÖm vÒ thuËt to¸n vµ ®é phøc t¹p cña thuËt to¸n. §ång thêi ®Ó tiÖn theo dâi, chóng t«i tr×nh bµy trong tiÕt 1.2 mét sè kiÕn thøc vÒ phÐp tÝnh ®ång d vµ c¸c vÊn ®Ò liªn quan, trong tiÕt 1.3 lµ mét sè kiÕn thøc vÒ ph©n sè liªn tôc. 1.1 ThuËt to¸n vµ ®é phøc t¹p cña thuËt to¸n 1.1.1 Kh¸i niÖm: Cã thÓ ®Þnh nghÜa thuËt to¸n theo nhiÒu c¸ch kh¸c nhau. Trong luËn v¨n nµy, chóng ta cã thÓ hiÓu kh¸i niÖm thuËt to¸n theo c¸ch th«ng thêng nhÊt. ThuËt to¸n lµ mét qui t¾c ®Ó víi nh÷ng d÷ kiÖn ban ®Çu ®· cho, t×m ®îc lêi gi¶i cña bµi to¸n ®îc xÐt sau mét kho¶ng thêi gian h÷u h¹n. §Ó minh häa c¸ch ghi mét thuËt to¸n, còng nh t×m hiÓu c¸c yªu cÇu ®Æt ra cho thuËt to¸n, ta xÐt mét vÝ dô cô thÓ sau: Cho n sè tù nhiªn X[1], X[2], ..., X[n]. T×m m vµ j sao cho j lµ sè lín nhÊt tho¶ m·n: m = X[j] = max X[k]. 1≤k≤n Bµi to¸n nµy còng cã nghÜa lµ t×m cùc ®¹i cña c¸c sè ®· cho vµ t×m chØ sè lín nhÊt trong c¸c sè ®¹t cùc ®¹i. V× cÇn t×m chØ sè lín nhÊt trong c¸c sè 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn ®¹t cùc ®¹i, ta xuÊt ph¸t tõ gi¸ trÞ X[n]. Trong bíc thø nhÊt ta t¹m thêi xem m = X[n] vµ j = n. TiÕp theo ta so s¸nh X[n] vµ X[n − 1]. Trong trêng hîp n − 1 = 0, tøc n = 1, thuËt to¸n kÕt thóc. NÕu X[n − 1] ≤ X[n], ta chuyÓn sang so s¸nh X[n] víi X[n − 2]. Trong trêng hîp ngîc l¹i, X[n − 1] chÝnh lµ sè cùc ®¹i trong hai sè ®· xÐt (hai sè X[n] vµ X[n − 1]). Khi ®ã ta ph¶i thay ®æi m = X[n − 1] vµ j = n − 1. Víi c¸ch lµm nh trªn ta lu«n nhËn ®îc sè cùc ®¹i trong nh÷ng sè ®· xÐt, vµ còng nhËn ®îc chØ sè lín nhÊt j trong c¸c chØ sè cña c¸c sè ®¹t cùc ®¹i ®ã. Bíc tiÕp theo ®ã lµ so s¸nh nã víi sè ®øng ngay tríc nh÷ng sè ®· xÐt, hoÆc kÕt thóc thuËt to¸n trong trêng hîp kh«ng cßn sè nµo ®øng tríc nã. B©y giê ta cã thÓ ghi l¹i thuËt to¸n trªn nh sau : ThuËt to¸n t×m cùc ®¹i. M1. (Bíc xuÊt ph¸t). §Æt j ←− n, k ←− n − 1, m ←− X[n]. M2. (§· kiÓm tra xong?). NÕu k = 0, thuËt to¸n kÕt thóc. M3. (So s¸nh). NÕu X[k] ≤ m, chuyÓn sang M5. M4. (Thay ®æi m). §Æt j ←− k, m ←− X[k] (ta hiÓu m t¹m thêi ®ang lµ cùc ®¹i). M5. (Gi¶m k ). §Æt k ←− k − 1, quay vÒ M2. Trong b¶ng ghi trªn ®©y, dÊu ←− dïng ®Ó chØ mét phÐp to¸n quan träng, ®ã lµ phÐp thay chç. Trªn ®©y ta ®· ghi mét thuËt to¸n b»ng ng«n ng÷ th«ng thêng. Trong trêng hîp thuËt to¸n ®îc viÕt b»ng ng«n ng÷ lµm viÖc cña m¸y tÝnh, ta cã mét ch¬ng tr×nh. Trong thuËt to¸n, cã nh÷ng sè liÖu ban ®Çu ®îc cho tríc khi thuËt to¸n b¾t ®Çu lµm viÖc. Ta gäi chóng lµ ®Çu vµo (input). Ch¼ng h¹n, trong thuËt to¸n t×m cùc ®¹i trªn, ®Çu vµo chÝnh lµ c¸c sè X[1], X[2], ..., X[n]. Mét thuËt to¸n cã thÓ cã nhiÒu ®Çu ra (output). Trong thuËt to¸n t×m cùc ®¹i trªn, ®Çu ra lµ c¸c sè m vµ j . Cã thÓ thÊy r»ng thuËt to¸n t×m cùc ®¹i m« t¶ trªn tho¶ m·n nh÷ng yªu cÇu cña mét thuËt to¸n nãi chung, ®ã lµ tÝnh h÷u h¹n vµ tÝnh chÝnh x¸c. 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn TÝnh h÷u h¹n. ThuËt to¸n cÇn ph¶i kÕt thóc sau mét sè h÷u h¹n bíc. Khi thuËt to¸n ngõng lµm viÖc, ta ph¶i thu ®îc c©u tr¶ lêi cho vÊn ®Ò ®Æt ra. ThuËt to¸n t×m cùc ®¹i m« t¶ trªn ®©y râ rµng tho¶ m·n ®iÒu kiÖn nµy v× ë mçi bíc ta chuyÓn ®îc tõ viÖc xÐt mét sè sang sè ®øng tríc nã, vµ sè c¸c sè cÇn xÐt lµ h÷u h¹n. TÝnh x¸c ®Þnh.¥ mçi bíc, thuËt to¸n cÇn ph¶i x¸c ®Þnh, nghÜa lµ chØ râ viÖc cÇn lµm. ThuËt to¸n t×m cùc ®¹i ë trªn chØ ra râ rµng nh÷ng viÖc cÇn lµm cña mçi bíc. Ngoµi nh÷ng yÕu tè kÓ trªn, ta cßn ph¶i xÐt ®Õn tÝnh hiÖu qu¶ cña thuËt to¸n. Cã rÊt nhiÒu thuËt to¸n vÒ mÆt lý thuyÕt lµ kÕt thóc sau mét sè h÷u h¹n bíc, tuy nhiªn thêi gian lµm viÖc ®ã l¹i vît qu¸ kh¶ n¨ng lµm viÖc cña chóng ta. V× thÕ, ta cßn ph¶i chó ý ®Õn c¸i gäi lµ ®é phøc t¹p cña thuËt to¸n. §é phøc t¹p cña thuËt to¸n cã thÓ ®o b»ng kh«ng gian, tøc lµ dung lîng bé nhí cña m¸y tÝnh cÇn thiÕt ®Ó thùc hiÖn thuËt to¸n, vµ ®o b»ng thêi gian, tøc lµ thêi gian m¸y tÝnh lµm viÖc. Trong luËn v¨n nµy, khi nãi ®Õn ®é phøc t¹p cña thuËt to¸n, ta lu«n lu«n hiÓu lµ ®é phøc t¹p thêi gian. 1.1.2 §é phøc t¹p cña thuËt to¸n DÜ nhiªn, thêi gian lµm viÖc cña m¸y tÝnh khi ch¹y mét thuËt to¸n nµo ®ã kh«ng chØ phô thuéc vµo thuËt to¸n, mµ cßn phô thuéc vµo m¸y tÝnh sö dông ®Ó ch¹y thuËt to¸n ®ã. V× thÕ, ®Ó cã mét tiªu chuÈn chung, ta sÏ ®o ®é phøc t¹p cña mét thuËt to¸n b»ng sè c¸c phÐp tÝnh ph¶i lµm khi thùc hiÖn thuËt to¸n. Khi tiÕn hµnh cïng mét thuËt to¸n, sè c¸c phÐp tÝnh ph¶i lµm khi thùc hiÖn cßn phô thuéc vµo cì cña bµi to¸n, tøc lµ phô thuéc vµo ®é lín cña ®Çu vµo. V× thÕ ®é phøc t¹p cña thuËt to¸n sÏ lµ mét hµm sè cña ®é lín cña ®Çu vµo. Trong nh÷ng øng dông thùc tiÔn, chóng ta kh«ng cÇn biÕt chÝnh x¸c hµm nµy, mµ chØ cÇn biÕt cì cña chóng, tøc lµ cÇn cã mét íc lîng ®ñ tèt cña chóng. 7 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Khi lµm viÖc, m¸y tÝnh thêng ghi c¸c ch÷ sè b»ng nh÷ng bãng ®Ìn s¸ng, t¾t: bãng ®Ìn s¸ng chØ sè 1, bãng ®Ìn t¾t chØ sè 0. V× thÕ thuËn tiÖn nhÊt lµ dïng hÖ ®Õm c¬ sè 2, trong ®ã ®Ó biÓu diÔn mét sè, ta chØ cÇn dïng hai kÝ hiÖu 0 vµ 1. Mét kÝ hiÖu 0 vµ 1 ®îc gäi lµ mét bÝt. Mét sè nguyªn n biÓu diÔn bëi k ch÷ sè 1 vµ ch÷ sè 0 ®îc gäi lµ sè k -bÝt. Trong môc nµy vµ c¸c môc tiÕp theo ta sÏ thÊy r»ng sè tù nhiªn n sÏ lµ mét sè k -bÝt víi k = [log2 n] (dÊu [ ] lµ kÝ hiÖu phÇn nguyªn cña mét sè). §é phøc t¹p cña thuËt to¸n ®îc ®o b»ng sè c¸c phÐp tÝnh bÝt. PhÐp tÝnh bÝt lµ mét phÐp tÝnh l«gic hay sè häc thùc hiÖn trªn c¸c sè mét bÝt 0 vµ 1 §Ó íc lîng ®é phøc t¹p cña thuËt to¸n ta dïng kh¸i niÖm bËc O-lín. §Þnh nghÜa 1: Gi¶ sö f (n) vµ g(n) lµ hai hµm x¸c ®Þnh trªn tËp hîp c¸c sè nguyªn d¬ng. Ta nãi f (n) cã bËc O lín cña g(n) vµ viÕt f (n) = O(g(n)) hoÆc f = O(g), nÕu tån t¹i mét sè C > 0, sao cho n ®ñ lín, c¸c hµm f (n) vµ g(n) ®Òu d¬ng, ®ång thêi f (n) < C.g(n). VÝ dô: Cho f (n) = ai ni + ai−1 ni−1 + . . . + a1 n + a0 , trong ®ã ai > 0. Khi ®ã f (n) = O(ni ). Chóng ta cã thÓ kiÓm tra ®îc r»ng: NÕu f1 (n) = O(g(n)), f2 (n) = O(g(n)) th× f1 (n) + f2 (n) = O(g(n)); vµ nÕu f1 (n) = O(g1 (n)), f2 (n) = O(g1 (n)) th× (f1 f2 )(n) = O(g1 g1 (n)). H¬n n÷a nÕu tån t¹i giíi h¹n h÷u h¹n f (n) lim n→∞ g(n) th× f(n) = O(g(n)) §Þnh nghÜa 2: Mét thuËt to¸n ®îc gäi lµ cã ®é phøc t¹p ®a thøc hoÆc cã thêi gian ®a thøc, nÕu sè c¸c phÐp tÝnh cÇn thiÕt khi thùc hiÖn thuËt to¸n kh«ng vît qu¸ O(log d n), trong ®ã, n lµ ®é lín cña ®Çu vµo vµ d lµ sè nguyªn d¬ng nµo 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn ®ã. Nãi c¸ch kh¸c, nÕu ®Çu vµo lµ c¸c sè k -bÝt th× thêi gian thùc hiÖn thuËt d to¸n lµ O(k ), tøc lµ t¬ng ®¬ng víi mét ®a thøc cña k . α C¸c thuËt to¸n víi thêi gian O(n ), α > 0, ®îc gäi c¸c thuËt to¸n víi ®é phøc t¹p mò, hay thêi gian mò. Còng cã nh÷ng thuËt to¸n cã ®é phøc t¹p trung gian gi÷a ®a thøc vµ mò. Ta thêng gäi ®ã lµ thuËt to¸n díi mò. Ch¼ng h¹n, thuËt to¸n nhanh nhÊt ®îc biÕt ®Õn hiÖn nay ®Ó ph©n tÝch mét sè nguyªn n ra thõa sè lµ thuËt to¸n cã ®é phøc t¹p √ exp( lognloglogn) Khi gi¶i mét bµi to¸n, chóng ta kh«ng nh÷ng cÇn t×m ra mét thuËt to¸n nµo ®ã, mµ cßn muèn t×m ra thuËt to¸n "tèt nhÊt". §¸nh gi¸ ®é phøc t¹p cña thuËt to¸n lµ mét trong nh÷ng c¸ch ®Ó so s¸nh, ph©n tÝch vµ t×m ra thuËt to¸n tèi u. Tuy nhiªn ®é phøc t¹p kh«ng ph¶i lµ tiªu chuÈn duy nhÊt ®Ó ®¸nh gi¸ thuËt to¸n. Cã nh÷ng thuËt to¸n vÒ mÆt lý thuyÕt th× ®é phøc t¹p cao h¬n mét thuËt to¸n kh¸c, nhng khi sö dông l¹i cã hiÖu qu¶ (gÇn ®óng) nhanh h¬n nhiÒu. §iÒu nµy phô thuéc vµo nh÷ng bµi to¸n cô thÓ, nh÷ng môc tiªu cô thÓ, vµ c¶ kinh nghiÖm cña ngêi sö dông. ThuËt to¸n "x¸c suÊt". Chóng ta cÇn lu ý thªm mét ®iÓm sau ®©y. MÆc dï ®Þnh nghÜa thuËt to¸n mµ chóng ta ®a ra cha ph¶i lµ chÆt chÏ, nã vÉn qu¸ "cøng nh¾c" trong nh÷ng øng dông thùc tÕ. Bëi vËy chóng ta cßn cÇn ®Õn nh÷ng thuËt to¸n"x¸c suÊt", tøc lµ nh÷ng thuËt to¸n phô thuéc vµo mét hay nhiÒu tham sè ngÉu nhiªn. Nh÷ng thuËt to¸n nµy vÒ nguyªn t¾c kh«ng ®îc gäi lµ thuËt to¸n, v× chóng cã thÓ, víi x¸c suÊt rÊt bÐ, kh«ng bao giê kÕt thóc. Tuy nhiªn, thùc nghiÖm chØ ra r»ng, c¸c thuËt to¸n x¸c suÊt thêng h÷u hiÖu h¬n c¸c thuËt to¸n tÊt ®Þnh. ThËm chÝ, trong rÊt nhiÒu trêng hîp, chØ cã c¸c thuËt to¸n x¸c suÊt lµ sö dông ®îc. Khi lµm viÖc víi c¸c thuËt to¸n x¸c suÊt, ta thêng hay ph¶i sö dông c¸c sè "ngÉu nhiªn". Kh¸i niÖm chän sè nhÉu nhiªn còng cÇn ®îc chÝnh x¸c ho¸. Thêng th× ngêi ta sö dông mét "m¸y" s¶n suÊt sè gi¶ ngÉu nhiªn nµo ®ã. Còng cÇn lu ý ngay 9 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn r»ng, ®èi víi c¸c thuËt to¸n x¸c suÊt, kh«ng thÓ nãi ®Õn thêi gian tuyÖt ®èi mµ chØ cã thÓ nãi ®Õn thêi gian hy väng. §Ó h×nh dung ®îc phÇn nµo "®é phøc t¹p" cña c¸c thuËt to¸n (tÊt ®Þnh vµ x¸c suÊt) khi lµm viÖc víi nh÷ng sè lín, ta xem b¶ng díi ®©y cho kho¶ng thêi gian cÇn thiÕt ®Ó ph©n tÝch mét sè nguyªn n ra thõa sè b»ng thuËt to¸n nhanh nhÊt ®îc biÕt hiÖn nay (ta xem m¸y tÝnh sö dông vµo viÖc nµy cã tèc ®é mét triÖu phÐp tÝnh trong 1 gi©y). Sè ch÷ sè thËp ph©n Sè phÐp tÝnh bit Thêi gian 10 50 1,4.10 3,9 giê 12 75 9,0.10 104 ngµy 15 100 2,3.10 74 n¨m 23 9 200 1,2.10 3,8.10 n¨m 29 15 300 1,5.10 4,9.10 n¨m 39 25 500 1,3.10 4,2.10 n¨m Tõ b¶ng trªn ®©y ta thÊy r»ng, ngay víi mét thuËt to¸n díi mò, thêi gian lµm viÖc cña c¸c sè nguyªn lín lµ qu¸ l©u. V× thÕ, nãi chung ngêi ta lu«n cè g¾ng t×m nh÷ng thuËt to¸n ®a thøc. 1.2 PhÐp tÝnh ®ång d vµ c¸c vÊn ®Ò liªn quan 1.2.1 Sè nguyªn tè vµ ®Þnh lý c¬ b¶n cña sè häc Sè nguyªn tè. Sè nguyªn tè lµ sè nguyªn lín h¬n 1, kh«ng chia hÕt cho sè nguyªn nµo ngoµi 1 vµ chÝnh nã. Sè nguyªn lín h¬n 1 kh«ng ph¶i lµ sè nguyªn tè ®îc gäi lµ hîp sè. 10 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn §Þnh lý c¬ b¶n cña sè häc Mäi sè tù nhiªn lín h¬n 1 ®Òu ph©n tÝch ®îc mét c¸ch duy nhÊt thµnh tÝch c¸c thõa sè nguyªn tè, trong ®ã c¸c thõa sè ®îc viÕt theo thø tù kh«ng gi¶m. chøng minh Gi¶ sö tån t¹i nh÷ng sè kh«ng viÕt ®îc thµnh tÝch c¸c sè nguyªn tè. Gäi n lµ sè bÐ nhÊt trong c¸c sè ®ã. Nh vËy, n ph¶i lµ hîp sè, n = a.b víi 1 < a, b < n. Do ®Þnh nghÜa cña n, c¸c sè a vµ b ph©n tÝch ®a thµnh tÝch cña c¸c sè nguyªn tè, nghÜa lµ n còng ph©n tÝch ®îc. M©u thuÉn víi gi¶ thiÕt. VËy mäi sè ®Òu ph©n tÝch ®îc thµnh tÝch cña c¸c sè nguyªn tè. Chóng ta cßn ph¶i chøng minh ph©n tÝch lµ duy nhÊt. Gi¶ sö ta cã: n = p 1 p 2 . . . p s = q1 q2 . . . qr , trong ®ã p1 , p2 , . . . , ps ; q1 , q2 , . . . , qr lµ c¸c sè nguyªn tè. Gi¶n íc nh÷ng sè nguyªn tè b»ng nhau cã mÆt trong hai vÕ, ta ®îc ®¼ng thøc pi1 pi2 . . . piu = qj1 qj2 . . . qjv , trong ®ã kh«ng cã sè nguyªn tè nµo cã mÆt c¶ ë hai vÕ. Nh vËy, vÕ tr¸i chia hÕt cho qj1 vµ do ®ã ph¶i tån t¹i mét thõa sè cña tÝch chia hÕt cho qj1 : ®iÒu ®ã v« lý, v× ®©y lµ tÝch cña c¸c sè nguyªn tè kh¸c víi qj1 . Ta gäi ph©n tÝch sè nguyªn ra thõa sè nguyªn tè lµ ph©n tÝch sè nguyªn. 1.2.2 ThuËt to¸n Euclid vµ më réng ThuËt to¸n Euclid M1. (KÕt thóc?). NÕu b = 0, in ra a vµ kÕt thóc thuËt to¸n. M2. (Chia Euclid). §Æt r ←− a mod b, a ←− b, b ←− r , vµ quay vÒ M1. VÝ dô: Ta tÝnh gcd(345,1127) b»ng thuËt to¸n Euclid. Ta cã: d = (345,1127) = (92,345) = (69,92) = (69,23) =(0,23) = 23. Nh vËy, gcd(345,1127) = 23 ThuËt to¸n Euclid më réng Cho hai sè nguyªn kh«ng ©m u, v t×m (u1 , u2 , u3 ) sao cho 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn (u, v) = u3 = uu1 + vu2 Trong tÝnh to¸n, ta thªm vµo c¸c Èn phô (v1 , v2 , v3 ), (t1 , t2 , t3 ) vµ lu«n cã trong mäi bíc c¸c ®¼ng thøc sau ®©y: ut1 + vt2 = t3 , uv1 + vv2 = v3 , uu1 + vu2 = u3 M1. (XuÊt ph¸t). §Æt (u1 , u2 , u3 ) ←− (1, 0, u), (v1 , v2 , v3 ) ←− (0, 1, v). M2. (KiÓm tra v3 = 0 ?). NÕu v3 = 0, thuËt to¸n kÕt thóc. M3. (Chia, trõ). §Æt q ←− [ uv 3 ], vµ sau ®ã ®Æt 3 (t1 , t2 , t3 ) ←− (u1 , u2 , u3 ) − q(v1 , v2 , v3 ), (u1 , u2 , u3 ) ←− (v1 , v2 , v3 ), (v1 , v2 , v3 ) ←− (t1 , t2 , t3 ) vµ quay vÒ bíc M2. 1.2.3 Phi - hµm Euler §Þnh nghÜa: Víi n ∈ N, sè lîng c¸c sè tù nhiªn bÐ h¬n n vµ nguyªn tè cïng nhau víi n ®îc ký hiÖu lµ ϕ(n) VÝ dô: ϕ(4) = 2 ; ϕ(5) = 4 ; ϕ(6) = 2 ; ϕ(7) = 6 ; ϕ(8) = 4 §Þnh lý NÕu m, n lµ c¸c sè nguyªn d¬ng nguyªn tè cïng nhau, th× ϕ(m, n) = ϕ(m).ϕ(n) Chøng minh: Ta viÕt c¸c sè nguyªn d¬ng kh«ng vît qu¸ m, n thµnh b¶ng sau: 1 m+1 2m+1 ... (n - 1)m+1 2 m+2 2m+2 ... (n - 1)m+2 3 m+3 2m+3 ... (n - 1)m+3 ... ... ... ... ... m m+m 3m ... m.n 12 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn B©y giê gi¶ sö r lµ mét sè nguyªn kh«ng vît qu¸ m. Gi¶ sö (m, r) = d > 1. Khi ®ã, kh«ng sè nµo trong dßng thø r nguyªn tè cïng nhau víi m.n, vµ mçi phÇn tö cña dßng ®ã ®Òu cã d¹ng km + r , 1 ≤ k ≤ n − 1, d|(km + r) v× d|m, d|r. VËy, ®Ó t×m c¸c sè trong b¶ng mµ nguyªn tè cïng nhau víi m.n, ta chØ cÇn xem dßng thø r víi (m, r) = 1. Ta xÐt mét dßng nh vËy, nã chøa c¸c sè r, m + r, ..., (n − 1)m + r . V× (r, m) = 1 nªn mçi sè nguyªn trong dßng ®Òu nguyªn tè cïng nhau víi n. VËy, n sè nguyªn trong dßng lËp thµnh hÖ thÆng d ®Çy ®ñ modulo m. Do c¸c sè ®ã còng nguyªn tè cïng nhau víi m nªn chóng nguyªn tè cïng nhau víi m.n, nªn ta suy ra ϕ(m, n) = ϕ(m).ϕ(n) 1.2.4 PhÐp tÝnh ®ång d vµ ph¬ng tr×nh ®ång d §Þnh nghÜa phÐp tÝnh ®ång d : Gi¶ sö m lµ mét sè nguyªn d¬ng. Ta nãi, hai sè nguyªn a vµ b lµ ®ång d víi nhau modulo m nÕu m chia hÕt hiÖu a − b §Ó chØ a ®ång d víi b modulo m ta ký hiÖu: a ≡ b (mod m) ( Gäi lµ ®ång d thøc) Nh vËy, a ≡ b (mod m) khi vµ chØ khi tån t¹i sè nguyªn k, sao cho a = b + km Mét sè tÝnh chÊt cña ®ång d : 1. a ≡ a (mod m) (1.2.3.1) 2. NÕu a ≡ b (mod m) th× b ≡ a (mod m) (1.2.3.2) 3. NÕu ( a ≡ b (mod m) b ≡ c (mod m) 13 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn th× a ≡ c (mod m) (1.2.3.3) 4. NÕu a ≡ b (mod m), c ≡ d (mod m) th× a ± c ≡ b ± d (mod m), a.c ≡ b.d (mod m) (1.2.3.4) Ph¬ng tr×nh ®ång d tuyÕn tÝnh ax ≡ b (mod m) Khi gcd(a, m) = 1 th× cã ngay nghiÖm x ≡ a−1 b (mod m) Khi gcd(a, m) = g th× cã hai kh¶ n¨ng x¶y ra: (1) NÕu g chia hÕt b, th× ph¬ng tr×nh ®· cho t¬ng ®¬ng víi ph¬ng tr×nh (a/g)x ≡ (b/g) (mod m/g) vµ (a/g, m/g) = 1 (®· xÐt ë trªn) (2) NÕu g kh«ng chia hÕt b, th× ph¬ng tr×nh v« nghiÖm. 1.2.5 §Þnh lý Fermat vµ c¸c më réng §Þnh lý Fermat bÐ : NÕu p lµ mét sè nguyªn tè cßn a lµ mét sè nguyªn th× ap ≡ a (mod p) NÕu p kh«ng chia hÕt a th× ap−1 ≡ 1 (mod p) VÝ dô: 65 ≡ 6 (mod 5); 65−1 ≡ 1 (mod 5); 105−1 ≡ 0 (mod 5) §Þnh lý më réng (Euler) NÕu gcd(a, m) = 1 th× aϕ(m) ≡ 1 (mod m) Chøng minh: Gi¶ sö {r1 , r2 , . . . , rϕ(m) } lµ hÖ thÆng d thu gän kh«ng ©m bÐ nhÊt modulo m. Khi ®ã {ar1 , ar2 , . . . , arϕ(m) } còng lµ mét hÖ thÆng d thu gän: V× ( (a, m) = 1 . (ri , m) = 1, i = 1, . . . , ϕ(m) ⇒ (r1 r2 . . . rϕ(m) , m) = 1 vµ ri 6≡ rj (mod m) (i 6= j) → ari 6≡ arj (mod m) Do ®ã thÆng d kh«ng ©m bÐ nhÊt cña hÖ nµy sÏ lµ tËp hîp {r1 , . . . , rϕ(m) }, s¾p xÕp theo thø tù nµo ®ã. Tõ ®ã theo tÝnh chÊt (1.2.3.4), ta cã: 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn ar1 .ar2 . . . arϕ(m) ≡ r1 .r2 . . . rϕ(m) (mod m) Nh vËy aϕ(m) .r1 .r2 . . . rϕ(m) ≡ r1 .r2 . . . rϕ(m) (mod m) V× (ri , m) = 1 nªn chia 2 vÕ cña ®ång d thøc trªn cho r1 .r2 . . . rϕ(m) ta ®îc aϕ(m) ≡ 1 (mod m) §Þnh lý ®îc chøng minh. (Trong trêng hîp riªng, khi m lµ sè nguyªn th× ϕ(m) = m − 1 vµ ta cã ®Þnh lý Fermat ) HÖ qu¶ 1.2.4.1 NÕu gcd(c, m) = 1 vµ a ≡ b (mod ϕ(m)) víi a, b lµ c¸c sè tù nhiªn, th× ca ≡ cb (mod m) HÖ qu¶ 1.2.4.2 NÕu e, d lµ c¸c sè nguyªn tháa m·n e.d ≡ 1 (mod ϕ(m)) th× víi mäi sè c nguyªn tè cïng nhau víi m, ta cã (ce )d ≡ c (mod m). NhËn xÐt : HÖ qu¶ nµy ®ãng vai trß then chèt trong viÖc thiÕt lËp c¸c hÖ m· mò vµ m· RSA ë ch¬ng II 1.2.6 TÝnh to¸n víi ®ång d cña luü thõa bËc lín Ngoµi viÖc sö dông hÖ qu¶ cña §Þnh lý Euler ®Ó tÝnh to¸n ngêi ta cßn thêng hay sö dông nhÊt lµ ph¬ng ph¸p b×nh ph¬ng liªn tiÕp sau ®©y. §Ó hiÓu râ ph¬ng ph¸p nµy chØ cÇn xem vÝ dô sau: VÝ dô: TÝnh 70923 mod 3137 Ta cã 23 = 1+2+4+16 = 20 + 21 + 22 + 24 7091 (mod 3137) = 709 7092 (mod 3137) = 761 7094 (mod 3137) = 7612 (mod 3137) = 1913 7098 (mod 3137) = 19132 (mod 3137) = 1827 70916 (mod 3137) = 18272 (mod 3137) = 161 Ta lÊy tÝch c¸c lòy thõa bËc 24 , 22 , 21 , 20 ( rót gän theo modulo 3137) vµ thu 15 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn ®îc kÕt qu¶ 70923 (mod 3137) = 709.761.1913.161. (mod 3137) = 907 1.2.7 ThÆng d b×nh ph¬ng vµ ký hiÖu Legendre §Þnh nghÜa Cho sè nguyªn tè p. Sè nguyªn a ≤ p ®îc gäi lµ thÆng d b×nh ph¬ng (mod p) nÕu nh tån t¹i sè nguyªn x tho¶ m·n ph¬ng tr×nh x2 ≡ a (mod p) Ta cã nguyªn lý thó vÞ sau: Nguyªn lý c¨n bËc 2 Mét trong hai "nghiÖm" cña thÆng d b×nh ph¬ng còng lµ mét thÆng d b×nh ph¬ng. VÝ dô LÊy p = 11 ta cã a = 4 lµ mét thÆng d b×nh ph¬ng. Nã cã hai nghiÖm lµ 2 vµ 9, trong ®ã 9 lµ mét thÆng d b×nh ph¬ng (DÔ dµng kiÓm tra 32 ≡ 9 (mod 11) hoÆc 82 ≡ 9 (mod 11) Ký hiÖu Legendre Víi sè nguyªn tè p > 2 vµ sè nguyªn bÊt kú a, ngêi ta ký hiÖu: a p−1 L(a, p) := [ ] = a 2 (mod p) p Vµ 0 nÕu a chia hÕt cho p a L(a, p) := [ ] = 1 nÕu a lµ mét thÆng d b×nh ph¬ng (mod p) p −1 c¸c trêng hîp cßn l¹i Ta cã thÓ më réng kh¸i niÖm ký hiÖu trªn cho trêng hîp p kh«ng ph¶i lµ nguyªn tè, nhng chØ xÐt nh÷ng sè a trong tËp thÆng d rót gän cña p. Ký hiÖu Jacobi: Víi sè nguyªn n = p1 .p2 . . . pk ; pi , i = 1, k lµ c¸c sè nguyªn tè cßn a n»m trong tËp thÆng d rót gän cña n, ta ký hiÖu: J(a, n) = L(a, p1 )L(a, p2 ) . . . L(a, pk ) Nh vËy khi n lµ sè nguyªn tè th× J(a, n) = L(a, n) 16 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 1.3 Ph©n sè liªn tôc 1.3.1 Kh¸i niÖm. Cho a, b lµ c¸c sè nguyªn, b > 0. Thùc hiÖn thuËt to¸n Euclid ta ®îc: a = ba0 + r0 , (0 ≤ r0 < b) b = r 0 a1 + r 1 , (0 ≤ r1 < r0 ) ......... rn−3 = rn−2 an−1 + rn−1 , (0 ≤ rn−1 < rn−2 ) rn−2 = rn−1 an . a Nh vËy, ph©n sè cã thÓ viÕt b a r0 1 1 = a0 + = a0 + = . . . = a0 + b b b 1 a1 + r0 1 . . . + an−1 + an a C¸ch viÕt nh trªn ®îc gäi lµ biÓu diÔn sè h÷u tû díi d¹ng ph©n sè liªn b tôc. a §Ó ®¬n gi¶n, ta dïng c¸ch viÕt = [a0 ; a1 , . . . , an ]. Ph©n sè liªn tôc b [a0 ; a1 , . . . , an ] ®îc gäi lµ ph©n sè liªn tôc h÷u h¹n. Dïng thuËt to¸n Euclid, cã thÓ biÓu diÔn mäi sè h÷u tû díi d¹ng ph©n sè liªn tôc h÷u h¹n. Ngîc l¹i, râ rµng mçi ph©n sè liªn tôc h÷u h¹n lµ mét sè h÷u tû. Gi¶ sö x lµ mét sè thùc tuú ý. §Æt a0 = [x], phÇn nguyªn cña x, vµ 1 1 x0 = x − a0 lµ phÇn lÎ cña x. TiÕp theo ®ã ta ®Æt a1 = [ ], x1 = − a1 . x0 x0 1 1 Víi mçi i = 1, 2, . . . , ®Æt ai = [ ], xi = − ai . NÕu ë bíc thø i xi−1 xi−1 nµo ®ã, xi = 0 th× qóa tr×nh kÕt thóc (§iÒu nµy x¶y ra khi vµ chØ khi x lµ sè h÷u tû ). Ngîc l¹i, ta cã x biÓu diÔn díi d¹ng ph©n sè liªn tôc v« h¹n: 17 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn 1 x = a0 + 1 a1 + 1 ... + an + . . . §Ó thuËn tiÖn, ta cßn cã thÓ dïng c¸ch viÕt sau ®©y: 1 1 1 x = a0 + + + ... + + ... a1 + a2 + an + C¸c ph©n sè liªn tôc ®Þnh nghÜa nh trªn víi c¸c sè ai nguyªn gäi lµ c¸c ph©n sè liªn tôc ®¬n gi¶n. Khi kh«ng ®ßi hái ai lµ c¸c sè nguyªn, mµ cã thÓ lµ sè thùc tuú ý, ta dïng c¸ch viÕt 1 1 1 + x = [a0 ; a1 , . . . , an ] = a0 + + ... + . a1 + a2 + an Khi cã mét ph©n sè liªn tôc x = [a0 ; a1 , . . . , an , . . .], ta gäi c¸c sè sau ®©y lµ c¸c ph©n sè héi tô riªng (thø k ) cña x: Ck = [a0 ; a1 , . . . , ak ]. 1.3.2 TÝnh chÊt §Þnh lý 1.3.2.1 Gi¶ sö a0 , a1 , . . . , an , . . . lµ c¸c sè thùc, trong ®ã a1 , . . . , an > 0. §Æt b0 = a0 , b1 = a1 b0 + 1, q0 = 1, q1 = a vµ víi mäi k ≥ 2, bk = ak bk−1 + bk−2 , qk = ak qk−1 + qk−2 . Khi ®ã: bk (i) Ck = [a0 ; a1 , . . . , ak ] = qk k+1 (ii) Víi mçi k ≥ 1, ta cã bk qk+1 − bk+1 qk = (−1) . §Þnh lý 1.3.2.2 bk Gi¶ sö n lµ sè tù nhiªn kh«ng chÝnh ph¬ng vµ lµ c¸c ph©n sè héi tô √ √ q k riªng cña n. Ta ®Æt α0 = n, vµ c¸c sè αk , Qk , Pk ®îc ®Þnh nghÜa nh sau: √ Pk + n αk = , ak = [αk ], Qk 18 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn