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

Ứng dụng của số học trong lý thuyết mật mã của Vũ Thị Thanh Hậu, Luận văn Ths Toán. Download 1. Download 2.