BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC THĂNG LONG
NGUYỄN THỊ THANH HUYỀN
MỘT SỐ THUẬT TOÁN TRONG SỐ HỌC ỨNG DỤNG
TÓM TẮT LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Phương pháp toán sơ cấp
Mã số: 8 46 01 13
HÀ NỘI, 2018
Công trình được hoàn thành tại:
Trường đại học Thăng Long
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS TSKH HÀ HUY KHOÁI
Phản biện 1:
Phản biện 2:
Luận văn được bảo vệ trước Hội đồng chấm luận văn tại:
Trường đại học Thăng Long
Vào hồi 09 giờ 00 ngày 28 tháng 12 năm 2018
ContentsTrangMởđầu1Chương1Thuậttoánvàtưduythuậttoán21.1Thuậttoán..............................21.2Độphứctạpcủathuậttoán.....................21.3Tưduythuậttoán..........................3Chương2Mộtsốthuậttoánsốhọcthôngdụng42.1Kiếnthứccơbản...........................42.1.1Tínhchiahết.........................42.1.2Sốnguyêntố.........................52.1.3Đồngdư............................52.1.4Hệthặngdưvàlớpthặngdư................62.1.5Phânsốliêntục.......................62.2Mộtsốthuậttoántìmướcchunglớnnhất.............72.2.1ThuậttoánEuclid......................72.2.2ThuậttoánJ.Stein......................72.2.3ThuậttoánEuclidmởrộng.................72.2.4ĐịnhlýFermatnhỏ.....................92.3Mộtsốthuậttoánphântíchsốnguyênthànhtíchcácthừasốnguyêntốđặcbiệt..........................112.3.1PhântíchsốnguyênbằngsàngErathostenes.......112.3.2Pollard’srhomethod.....................112.3.3ĐườngcongEliptic......................132.3.4PhươngphápcủaFermat..................152.3.5PhươngphápSqufof.....................162.3.6ThuậttoánDixon......................162.3.7ThuậttoánSàngbậchai-QuadraticSieve.........17iii
Chương3HệmãkhóaRSA,chữkýsốvàhàmbămmậtmã193.1HệmãhóaRSA............................193.2Tạokhóa,mãhóa,giảimãcủahệRSA..............193.3Chữkýđiệntử-Chữkýsố......................203.4Hàmbăm................................213.4.1PhươngthứcmãhóaMD5.................213.4.2PhươngthứcmãhóaSHA1.................25Kếtluận31Tàiliệuthamkhảo32iv
MởđầuSốhọclàmộtmônkhoahọclýthú,hấpdẫnnhữngngườihọcvàlàmtoán,cácgiáoviên,họcsinhtrênkhắpthếgiới.Mặcdùkhoahọckỹthuậtngàynayrấtpháttriểnnhưngcónhữngbàitoántừthờicổđạivẫncòngiátrịđếntậnbâygiờvàviệcđitìmmộtthuậttoánphântíchsốnguyênratíchcácthừasốnguyêntốlàmộttrongnhữngthuậttoánnhưvậy.Chínhnhờđộkhócủaviệcphântíchsốnguyênthànhtíchcácthừasốnguyêntốđãlàcơsởchosựrađờicủamậtmãhọc.Luậnvănnàytrìnhbàymộtsốthuậttoánsốhọcvàứngdụng.ThuậttoánphântíchmộtsốnguyênracácthừasốnguyêntốbắtđầutừsàngEratosthennes,phươngphápRHOcủaPollard,phântíchFermat,phươngphápSqufof,thuậttoánDixon,thuậttoánsàngbậchai.Luậnvănđượcchialàmbachương:1.Chương1:Thuậttoánvàtưduythuậttoántrìnhbàynhữngkháiniệmcơbảnvềthuậttoán,độphứctạpvàtưduythuậttoán.2.Chương2:Mộtsốthuậttoánthôngdụngtrìnhbàymộtsốkiếnthứccơbảnvềmộtsốthuậttoánsốhọcthôngdụng.3.Chương3:HệmãkhóaRSAvàchữkýsốtrìnhbàymộtsốứngdụngcủathuậttoánphântíchsốnguyênthànhtíchcácthừasốnguyêntốvàomậtmãvàtạochữkýsố.1