Luận văn: MỘT SỐ ỨNG DỤNG CỦA SỐ HỌC TRONG LÝ THUYẾT MẬT MÃ

Chia sẻ: Qsczaxewd Qsczaxewd | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

123
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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)....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: 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 70 Tríc nh÷ng n¨m 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 thay thÕ ch×a. th«ng qua phÐp theo 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
m· 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é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 n ®Æt ra cho thuËt to¸n, ta xÐt mét vÝ dô cô thÓ sau: Cho sè tù nhiªn X [1], X [2], ..., X [n]. T×m m vµ j j sao cho 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
X [n]. ®¹t cùc ®¹i, ta xuÊt ph¸t tõ gi¸ trÞ Trong bíc thø nhÊt ta t¹m thêi X [n − 1]. m = X [n] j = n. X [n] xem vµ TiÕp theo ta so s¸nh vµ Trong n − 1 = 0, tøc n = 1, thuËt to¸n kÕt thóc. NÕu X [n − 1] ≤ X [n], trêng hîp X [n − 2]. X [n] ta chuyÓn sang so s¸nh víi 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]). m = X [n − 1] vµ j = n − 1. Víi c¸ch lµm nh trªn Khi ®ã ta ph¶i thay ®æi ta lu«n nhËn ®îc sè cùc ®¹i trong nh÷ng sè ®· xÐt, vµ còng nhËn ®îc chØ j sè lín nhÊt 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). j ←− n, k ←− n − 1, m ←− X [n]. §Æt M2. (§· kiÓm tra xong?). k = 0, thuËt to¸n kÕt thóc. NÕu M3. (So s¸nh). X [k ] ≤ m, chuyÓn sang M5. NÕu M4. (Thay ®æi m). j ←− k, m ←− X [k ] m §Æt (ta hiÓu t¹m thêi ®ang lµ cùc ®¹i). M5. (Gi¶m k ). k ←− k − 1, quay vÒ M2. §Æt ←− dïng ®Ó chØ mét phÐp to¸n quan träng, Trong b¶ng ghi trªn ®©y, dÊu thay chç. ®ã lµ phÐp 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 ch¬ng tr×nh. m¸y tÝnh, ta cã mét Trong thuËt to¸n, cã nh÷ng sè liÖu ban ®Çu ®îc cho tríc khi thuËt to¸n ®Çu vµo (input). b¾t ®Çu lµm viÖc. Ta gäi chóng lµ Ch¼ng h¹n, trong thuËt X [1], X [2], ..., X [n]. to¸n t×m cùc ®¹i trªn, ®Çu vµo chÝnh lµ c¸c sè ®Çu ra (output). Mét thuËt to¸n cã thÓ cã nhiÒu Trong thuËt to¸n t×m cùc m vµ j . ®¹i trªn, ®Çu ra lµ c¸c sè 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 tÝnh h÷u h¹n tÝnh chÝnh x¸c. cÇu cña mét thuËt to¸n nãi chung, ®ã lµ vµ 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 ®é phøc t¹p cña cña chóng ta. V× thÕ, ta cßn ph¶i chó ý ®Õn c¸i gäi lµ thuËt to¸n. kh«ng gian, §é phøc t¹p cña thuËt to¸n cã thÓ ®o b»ng 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 thêi gian m¸y tÝnh lµm viÖc. b»ng thêi gian, tøc lµ 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 cì hµm nµy, mµ chØ cÇn biÕt 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
s¸ng, 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: 1, 0. bãng ®Ìn s¸ng chØ sè bãng ®Ìn t¾t chØ sè V× thÕ thuËn tiÖn nhÊt lµ 2, dïng hÖ ®Õm c¬ sè trong ®ã ®Ó biÓu diÔn mét sè, ta chØ cÇn dïng hai kÝ mét bÝt. 1. 0 1 n hiÖu 0 vµ Mét kÝ hiÖu vµ ®îc gäi lµ Mét sè nguyªn biÓu k 1 vµ ch÷ sè 0 ®îc gäi lµ sè k -bÝt. diÔn bëi ch÷ sè Trong môc nµy vµ c¸c n sÏ lµ mét sè k -bÝt víi k = [log2 n] môc tiÕp theo ta sÏ thÊy r»ng sè tù nhiª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: f (n) g (n) Gi¶ sö vµ lµ hai hµm x¸c ®Þnh trªn tËp hîp c¸c sè nguyªn f (n) g (n) f (n) = O(g (n)) d¬ng. Ta nãi cã bËc O lín cña vµ viÕt hoÆc f = O(g ), C > 0, n f (n) nÕu tån t¹i mét sè sao cho ®ñ lín, c¸c hµm vµ g (n) ®Òu d¬ng, ®ång thêi f (n) < C.g (n). VÝ dô: f (n) = ai ni + ai−1 ni−1 + . . . + a1 n + a0 , ai > 0. Cho trong ®ã Khi ®ã f (n) = O(ni ). Chóng ta cã thÓ kiÓm tra ®îc r»ng: f1 (n) = O(g (n)), f2 (n) = O(g (n)) th× f1 (n) + f2 (n) = O(g (n)); NÕu f1 (n) = O(g1 (n)), f2 (n) = O(g1 (n)) th× (f1 f2 )(n) = O(g1 g1 (n)). vµ nÕu 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), n d trong ®ã, lµ ®é lín cña ®Çu vµo vµ 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
®ã. k -bÝt Nãi c¸ch kh¸c, nÕu ®Çu vµo lµ c¸c sè 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 . to¸n lµ O(nα ), α > 0, C¸c thuËt to¸n víi thêi gian ®î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 thuËt to¸n díi mò. t¹p trung gian gi÷a ®a thøc vµ mò. Ta thêng gäi ®ã lµ Ch¼ng h¹n, thuËt to¸n nhanh nhÊt ®îc biÕt ®Õn hiÖn nay ®Ó ph©n tÝch mét n ra thõa sè lµ thuËt to¸n cã ®é phøc t¹p sè nguyªn √ 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 n ra thõa sè b»ng thuËt to¸n thêi gian cÇn thiÕt ®Ó ph©n tÝch mét sè nguyª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 1,4.10 50 3,9 giê 12 9,0.10 75 104 ngµy 15 2,3.10 100 74 n¨m 23 9 1,2.10 3,8.10 n¨m 200 29 15 1,5.10 4,9.10 300 n¨m 39 25 1,3.10 4,2.10 500 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 n n = a.b lµ sè bÐ nhÊt trong c¸c sè ®ã. Nh vËy, ph¶i lµ hîp sè, víi 1 < a, b < n . n, a b Do ®Þnh nghÜa cña c¸c sè vµ ph©n tÝch ®a thµnh tÝch n cña c¸c sè nguyªn tè, nghÜa lµ 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 , p1 , p2 , . . . , ps ; q1 , q2 , . . . , qr trong ®ã 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ã qj1 mÆt c¶ ë hai vÕ. Nh vËy, vÕ tr¸i chia hÕt cho vµ do ®ã ph¶i tån t¹i mét qj1 thõa sè cña tÝch chia hÕt cho : ®iÒu ®ã v« lý, v× ®©y lµ tÝch cña c¸c sè qj1 nguyªn tè kh¸c víi . 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?). b = 0, in ra a vµ kÕt thóc thuËt to¸n. NÕu M2. (Chia Euclid). r ←− a mod b, a ←− b, b ←− r, vµ quay vÒ M1. §Æt 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 u, v (u1 , u2 , u3 ) sao cho Cho hai sè nguyªn kh«ng ©m t×m 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 (v1 , v2 , v3 ), (t1 , t2 , t3 ) Trong tÝnh to¸n, ta thªm vµo c¸c Èn phô 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). (u1 , u2 , u3 ) ←− (1, 0, u), (v1 , v2 , v3 ) ←− (0, 1, v ). §Æt M2. (KiÓm tra v3 = 0 ?). v3 = 0, thuËt to¸n kÕt thóc. NÕu q ←− [ u3 ], vµ sau ®ã ®Æt M3. (Chia, trõ). 3 §Æt v (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: ∈ N, n Víi n sè lîng c¸c sè tù nhiªn bÐ h¬n vµ nguyªn tè cïng nhau n ®îc ký hiÖu lµ ϕ(n) víi VÝ dô: ϕ(4) = 2 ; ϕ(5) = 4 ; ϕ(6) = 2 ; ϕ(7) = 6 ; ϕ(8) = 4 §Þnh lý m, n lµ c¸c sè nguyªn d¬ng nguyªn tè cïng nhau, th× NÕu ϕ(m, n) = ϕ(m).ϕ(n) Chøng minh: m, n thµnh b¶ng sau: Ta viÕt c¸c sè nguyªn d¬ng kh«ng vît qu¸ 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
r m. B©y giê gi¶ sö lµ mét sè nguyªn kh«ng vît qu¸ (m, r) = d > 1. r Gi¶ sö Khi ®ã, kh«ng sè nµo trong dßng thø nguyªn m.n, km + r, tè cïng nhau víi 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. m.n, VËy, ®Ó t×m c¸c sè trong b¶ng mµ nguyªn tè cïng nhau víi ta chØ r (m, r) = 1. cÇn xem dßng thø víi 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 sè n. ®Òu nguyªn tè cïng nhau víi n modulo m. VËy, sè nguyªn trong dßng lËp thµnh hÖ thÆng d ®Çy ®ñ m Do c¸c sè ®ã còng nguyªn tè cïng nhau víi nªn chóng nguyªn tè cïng m.n, nªn ta suy ra ϕ(m, n) = ϕ(m).ϕ(n) nhau víi 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 : m a b Gi¶ sö lµ mét sè nguyªn d¬ng. Ta nãi, hai sè nguyªn vµ lµ ®ång modulo m nÕu m chia hÕt hiÖu a − b d víi nhau a ®ång d víi b modulo m ta ký hiÖu: §Ó chØ a ≡ b (mod m) ( Gäi lµ ®ång d thøc) a ≡ b (mod m) khi vµ chØ khi tån t¹i sè nguyªn k, Nh vËy, a = b + km sao cho Mét sè tÝnh chÊt cña ®ång d : a ≡ a (mod m) 1. (1.2.3.1) a ≡ b (mod m) th× b ≡ a (mod m) 2. NÕu (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
a ≡ c (mod m) th× (1.2.3.3) a ≡ b (mod m), c ≡ d (mod m) 4. NÕu 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) gcd(a, m) = 1 th× cã ngay nghiÖm x ≡ a−1 b (mod m) Khi gcd(a, m) = g Khi 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 (a/g )x ≡ (b/g ) (mod m/g ) vµ (a/g, m/g ) = 1 (®· xÐt ë trªn) tr×nh g b, th× ph¬ng tr×nh v« nghiÖm. (2) NÕu kh«ng chia hÕt 1.2.5 §Þnh lý Fermat vµ c¸c më réng §Þnh lý Fermat bÐ : 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) NÕu VÝ dô: 65−1 ≡ 1 (mod 5); 105−1 ≡ 0 (mod 5) 65 ≡ 6 (mod 5); §Þnh lý më réng (Euler) gcd(a, m) = 1 th× aϕ(m) ≡ 1 (mod m) NÕu Chøng minh: {r1 , r2 , . . . , rϕ(m) } Gi¶ sö 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 ri ≡ rj (mod m) (i = j ) → ari ≡ arj (mod m) vµ {r1 , . . . , rϕ(m) }, Do ®ã thÆng d kh«ng ©m bÐ nhÊt cña hÖ nµy sÏ lµ tËp hîp (1.2.3.4), s¾p xÕp theo thø tù nµo ®ã. Tõ ®ã theo tÝnh chÊt 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) (ri , m) = 1 nªn chia 2 vÕ cña ®ång d thøc trªn cho r1 .r2 . . . rϕ(m) V× aϕ(m) ≡ 1 (mod m) ta ®îc §Þ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 gcd(c, m) = 1 vµ a ≡ b (mod ϕ(m)) víi a, b lµ c¸c sè tù nhiªn, th× NÕu ca ≡ cb (mod m) HÖ qu¶ 1.2.4.2 e, d lµ c¸c sè nguyªn tháa m·n e.d ≡ 1 (mod ϕ(m)) th× víi mäi sè NÕu 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ô: 70923 mod 3137 TÝnh 20 + 21 + 22 + 24 Ta cã 23 = 1+2+4+16 = 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 24 , 22 , 21 , 20 ( rót gän theo modulo 3137) vµ thu Ta lÊy tÝch c¸c lòy thõa bËc 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 p. Sè nguyªn a ≤ p ®îc gäi lµ thÆng d b×nh ph¬ng Cho sè nguyªn tè (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ô p = 11 a=4 LÊy ta cã 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 p > 2 vµ sè nguyªn bÊt kú a, ngêi ta ký hiÖu: Víi sè nguyªn tè 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 a trong tËp thÆng d rót gän cña p. lµ nguyªn tè, nhng chØ xÐt nh÷ng sè Ký hiÖu Jacobi: n = p1 .p2 . . . pk pi , i = 1, k Víi sè nguyªn ; lµ c¸c sè nguyªn tè cßn thÆng d rót gän n, ta ký hiÖu: a n»m trong tËp cña J (a, n) = L(a, p1 )L(a, p2 ) . . . L(a, pk ) n lµ sè nguyªn tè th× J (a, n) = L(a, n) Nh vËy khi 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. a, b lµ c¸c sè nguyªn, b > 0. Thùc hiÖn thuËt to¸n Euclid ta ®îc: Cho (0 ≤ r0 < b) a = ba0 + r0 , (0 ≤ r1 < r0 ) b = r 0 a1 + r 1 , ......... (0 ≤ rn−1 < rn−2 ) rn−3 = rn−2 an−1 + rn−1 , rn−2 = rn−1 an . a Nh vËy, ph©n sè cã thÓ viÕt 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. a = [a0 ; a1 , . . . , an ]. §Ó ®¬n gi¶n, ta dïng c¸ch viÕt 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û. x a0 = [x], Gi¶ sö lµ mét sè thùc tuú ý. §Æt phÇn nguyªn cña x, vµ 1 1 x 0 = x − a0 − a1 . a1 = [ ], x1 = lµ phÇn lÎ cña x. TiÕp theo ®ã ta ®Æt x0 x0 1 1 − ai . i = 1, 2, . . . ai = [ ], xi = Víi mçi , ®Æt NÕu ë bíc thø i xi−1 xi−1 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è nµo ®ã, x biÓu diÔn díi d¹ng ph©n sè liªn tôc v« h¹n: h÷u tû ). Ngîc l¹i, ta cã 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 + ai C¸c ph©n sè liªn tôc ®Þnh nghÜa nh trªn víi c¸c sè nguyªn gäi lµ c¸c ai lµ c¸c sè nguyªn, mµ cã thÓ ph©n sè liªn tôc ®¬n gi¶n. Khi kh«ng ®ßi hái lµ sè thùc tuú ý, ta dïng c¸ch viÕt 1 1 1 x = [a0 ; a1 , . . . , an ] = a0 + + + ... + . a1 + a2 + an tôc x = [a0 ; a1 , . . . , an , . . .], Khi cã mét ph©n sè liªn ta gäi c¸c sè sau ®©y k ) cña x : lµ c¸c ph©n sè héi tô riªng (thø Ck = [a0 ; a1 , . . . , ak ]. 1.3.2 TÝnh chÊt §Þnh lý 1.3.2.1 a0 , a1 , . . . , an , . . . lµ c¸c sè thùc, trong ®ã a1 , . . . , an > 0. Gi¶ sö b0 = a0 , b1 = a1 b0 + 1, q0 = 1, q1 = a vµ víi mäi k ≥ 2, §Æt bk = ak bk−1 + bk−2 , qk = ak qk−1 + qk−2 . Khi ®ã: bk (i) Ck = [a0 ; a1 , . . . , ak ] = qk bk qk+1 − bk+1 qk = (−1)k+1 . k ≥ 1, ta cã (ii) Víi mçi §Þ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ô qk √ √ n. α0 = n, αk , Qk , Pk riªng cña Ta ®Æt vµ c¸c sè ®î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