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

Trước những năm 70 của thế kỷ XX, Số học thường được xem là mộttrong những ngành toán học thuần tuý, chỉ có ý nghĩa lý thuyết. Đối tượngnghiê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ạitrong Số học là các giả thuyết số nguyên tố. Thậm chí, có những nhà toánhọ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ó! (theocâu nói của G.H. Hardy, A Mathematicians Apology, 1940)....
Nội dung trích xuất từ tài liệu:
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 2009Số 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 2009Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vnMôc lôc Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 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 ................................. 182 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 1Số 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×nhvµ 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 gianvµ 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íngnghiÖp vµ Gi¸o dôc thêng xuyªn tØnh Qu¶ng Ninh, ®· t¹o ®iÒukiÖ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¹yvµ t¹o mäi ®iÒu kiÖn thuËn lîi cho t«i hoµn thµnh kho¸ häc. T«icòng xin c¶m ¬n b¹n bÌ vµ gia ®×nh ®· ®éng viªn vµ gióp ®ì t«itrong suèt qu¸ tr×nh häc tËp t¹i Trêng §¹i häc Khoa häc - §¹ihäc Th¸i Nguyªn. 2Số 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éttrong nh÷ng ngµnh to¸n häc thuÇn tuý, chØ cã ý nghÜa lý thuyÕt. §èi tîngnghiª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¹itrong Sè häc lµ c¸c gi¶ thuyÕt sè nguyªn tè. ThËm chÝ, cã nh÷ng nhµ to¸nhäc cho r»ng vÎ ®Ñp cña Sè ...