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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Mét sè kiÕn thøc c¬ b¶n 1.1 1.2 1.3 2 5 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 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 1.2.2 ThuËt to¸n Euclid vµ më réng 2.2 2.3 10 . . . . . . . . . . . . . . . 10 . . . . . . . . . . . . . . . . . . . . . . 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 Ph©n sè liªn tôc 1.3.1 Kh¸i niÖm. 1.3.2 TÝnh chÊt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Mét sè øng dông cña sè häc trong lý thuyÕt mËt m· 2.1 2 21 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 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 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 DiffieHellman, 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µ ho¸ víi kho¸ c«ng khai, m· 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 X[1], X[2], ..., X[n]. T×m m vµ j sao cho j n sè tù nhiªn 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Þ xem m = X[n] tr­êng hîp j = n. vµ X[n]. Trong b­íc thø nhÊt ta t¹m thêi X[n] TiÕp theo ta so s¸nh vµ X[n − 1]. Trong 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 M2. (§· kiÓm tra xong?). M3. (So s¸nh). NÕu M4. (Thay ®æi m). j ←− n, k ←− n − 1, m ←− X[n]. NÕu k = 0, thuËt to¸n kÕt thóc. X[k] ≤ m, chuyÓn sang M5. §Æ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 ®ã lµ phÐp thay chç. ←− dïng ®Ó chØ mét phÐp to¸n quan träng, 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). to¸n t×m cùc ®¹i trªn, ®Çu vµo chÝnh lµ c¸c sè Mét thuËt to¸n cã thÓ cã nhiÒu ®¹i trªn, ®Çu ra lµ c¸c sè Ch¼ng h¹n, trong thuËt X[1], X[2], ..., X[n]. ®Çu ra (output). Trong thuËt to¸n t×m cùc 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µ 6 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tÝnh h÷u h¹n vµ tÝnh chÝnh x¸c. 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µ thuËt to¸n. §é phøc t¹p cña thuËt to¸n cã thÓ ®o b»ng dung l­îng bé nhí ®é phøc t¹p cña kh«ng gian, tøc lµ 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 t¾t: bãng ®Ìn s¸ng chØ sè dïng hÖ ®Õm c¬ sè hiÖu 0 vµ diÔn bëi 1. k 2, 0. bãng ®Ìn t¾t chØ sè V× thÕ thuËn tiÖn nhÊt lµ trong ®ã ®Ó biÓu diÔn mét sè, ta chØ cÇn dïng hai kÝ Mét kÝ hiÖu ch÷ sè 1, s¸ng, 0 vµ 1 ®­îc gäi lµ mét bÝt. 1 vµ ch÷ sè 0 ®­îc gäi lµ sè k -bÝt. môc tiÕp theo ta sÏ thÊy r»ng sè tù nhiªn Mét sè nguyªn n biÓu Trong môc nµy vµ c¸c 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) d­¬ng. Ta nãi f = O(g), vµ f (n) g(n) lµ hai hµm x¸c ®Þnh trªn tËp hîp c¸c sè nguyªn cã bËc O lín cña nÕu tån t¹i mét sè C > 0, g(n) vµ viÕt sao cho n f (n) = O(g(n)) ®ñ lín, c¸c hµm hoÆc 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) n→∞ g(n) lim 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µ 8 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên d lµ sè nguyªn d­¬ng nµo http://www.Lrc-tnu.edu.vn ®ã. Nãi c¸ch kh¸c, nÕu ®Çu vµo lµ c¸c sè to¸n lµ k -bÝt th× thêi gian thùc hiÖn thuËt O(k d ), 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, nh­ng 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 l­u ý thªm mét ®iÓm sau ®©y. MÆc dï ®Þnh nghÜa thuËt to¸n mµ chóng ta ®­a ra ch­a 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 l­u ý 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 50 10 1,4.10 3,9 giê 75 12 9,0.10 104 ngµy 100 15 2,3.10 74 n¨m 200 23 1,2.10 9 3,8.10 n¨m 300 29 1,5.10 15 4,9.10 n¨m 500 39 1,3.10 25 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, 1 < a, b < n . Do ®Þnh nghÜa cña cña c¸c sè nguyªn tè, nghÜa lµ n n, c¸c sè n a ph¶i lµ hîp sè, vµ b n = a.b víi ph©n tÝch ®­a thµnh tÝch 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 thõa sè cña tÝch chia hÕt cho nguyªn tè kh¸c víi qj1 qj1 qj1 vµ do ®ã ph¶i tån t¹i mét : ®iÒu ®ã v« lý, v× ®©y lµ tÝch cña c¸c sè . 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 M2. (Chia Euclid). b = 0, in ra a vµ kÕt thóc thuËt to¸n. §Æ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 11 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên t×m (u1 , u2 , u3 ) sao cho 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 ?). M3. (Chia, trõ). §Æt NÕu v3 = 0, thuËt to¸n kÕt thóc. q ←− [ uv33 ], vµ sau ®ã ®Æt (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 víi ∈ N, sè l­îng c¸c sè tù nhiªn bÐ h¬n n vµ nguyªn tè cïng nhau 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ö Gi¶ sö r lµ mét sè nguyªn kh«ng v­ît qu¸ (m, r) = d > 1. tè cïng nhau víi m.n, m. Khi ®ã, kh«ng sè nµo trong dßng thø r nguyªn km + r, vµ mçi phÇn tö cña dßng ®ã ®Òu cã d¹ng 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 cÇn xem dßng thø sè r víi (m, r) = 1. m.n, ta chØ Ta xÐt mét dßng nh­ vËy, nã chøa c¸c 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 VËy, n n. sè nguyªn trong dßng lËp thµnh hÖ thÆng d­ ®Çy ®ñ Do c¸c sè ®ã còng nguyªn tè cïng nhau víi nhau víi m modulo m. nªn chóng nguyªn tè cïng 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 d­ víi nhau §Ó chØ lµ mét sè nguyªn d­¬ng. Ta nãi, hai sè nguyªn a vµ b modulo m nÕu m chia hÕt hiÖu a − b 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, sao cho a ≡ b (mod m) khi vµ chØ khi tån t¹i sè nguyªn k, a = b + km Mét sè tÝnh chÊt cña ®ång d­ : 1. a ≡ a (mod m) 2. NÕu (1.2.3.1) 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 lµ ®ång a ≡ c (mod m) th× 4. NÕu (1.2.3.3) a ≡ b (mod m), c ≡ d (mod m) a ± c ≡ b ± d (mod m), a.c ≡ b.d (mod m) th× (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 s¾p xÕp theo thø tù nµo ®ã. Tõ ®ã theo tÝnh chÊt 14 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1.2.3.4), {r1 , . . . , rϕ(m) }, ta cã: 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: p−1 a ] = a 2 (mod p) p Vµ   nÕu a chia hÕt cho p 0 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 L(a, p) := [ lµ nguyªn tè, nh­ng chØ xÐt nh÷ng sè ph¶i a trong tËp thÆng d­ rót gän cña p. Ký hiÖu Jacobi: Víi sè nguyªn a n»m trong tËp n = p1 .p2 . . . pk thÆng d­ rót gän pi , i = 1, k ; cña lµ c¸c sè nguyªn tè cßn 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 , b = r 0 a1 + r 1 , (0 ≤ r0 < b) (0 ≤ r1 < r0 ) ......... (0 ≤ rn−1 < rn−2 ) rn−3 = rn−2 an−1 + rn−1 , rn−2 = rn−1 an . a cã thÓ viÕt Nh­ vËy, ph©n sè b a r0 1 1 = a0 + = a0 + = . . . = a0 + 1 b b b a1 + 1 r0 . . . + 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. §Ó ®¬n gi¶n, ta dïng c¸ch viÕt a = [a0 ; a1 , . . . , an ]. b Ph©n sè liªn tôc [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 x 0 = x − a0 Víi mçi nµo ®ã, lµ mét sè thùc tuú ý. §Æt a0 = [x], a1 = [ lµ phÇn lÎ cña x. TiÕp theo ®ã ta ®Æt i = 1, 2, . . . , ®Æt ai = [ 1 xi−1 ], xi = phÇn nguyªn cña x, vµ 1 xi−1 1 1 ], x1 = − a1 . x0 x0 − ai . NÕu ë b­íc thø i 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: x = a0 + 1 1 1 + + ... + + ... a1 + a2 + an + C¸c ph©n sè liªn tôc ®Þnh nghÜa nh­ trªn víi c¸c sè ph©n sè liªn tôc ®¬n gi¶n. Khi kh«ng ®ßi hái ai nguyªn gäi lµ c¸c 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 + + ... + . a1 + a2 + an tôc x = [a0 ; a1 , . . . , an , . . .], x = [a0 ; a1 , . . . , an ] = a0 + Khi cã mét ph©n sè liªn lµ c¸c ph©n sè héi tô riªng (thø ta gäi c¸c sè sau ®©y k ) cña x : Ck = [a0 ; a1 , . . . , ak ]. 1.3.2 TÝnh chÊt §Þnh lý 1.3.2.1 Gi¶ sö §Æt a0 , a1 , . . . , an , . . . lµ c¸c sè thùc, trong ®ã a1 , . . . , an > 0. 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 ®ã: (i) Ck = [a0 ; a1 , . . . , ak ] = (ii) Víi mçi k ≥ 1, ta cã bk qk bk qk+1 − bk+1 qk = (−1)k+1 . §Þnh lý 1.3.2.2 bk qk αk , Qk , Pk Gi¶ sö n lµ sè tù nhiªn kh«ng chÝnh ph­¬ng vµ riªng cña sau: √ n. Ta ®Æt √ Pk + n αk = , Qk α0 = √ n, vµ c¸c sè lµ c¸c ph©n sè héi tô ®­îc ®Þnh nghÜa nh­ ak = [αk ], 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