Bài giảng Nhập môn Số học thuật toán: Chương 1, 2 - Nguyễn Đạt Thông

Bài giảng Nhập môn Số học thuật toán - Chương 1, 2 cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học. Trong chương này các bạn sẽ cùng tìm hiểu một số vấn đề cơ bản về thuật toán và số nguyên. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn Số học thuật toán: Chương 1, 2 - Nguyễn Đạt ThôngGiới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục Nhập môn SỐ HỌC THUẬT TOÁN Nguyễn Đạt Thông ndthong@math.hcmus.edu.vn Bộ môn Ứng dụng Tin học Khoa Toán - Tin học 2010Nhập môn Số học và Thuật toán 1/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcGiới thiệu Tên học phần: Nhập môn số học thuật toán. Số tín chỉ: 4. Chuyên ngành: Phương pháp Toán trong Tin học. Học phần tiên quyết: Đại số đại cương. Học phần liên quan: Phân tích thuật toán. Lý thuyết mã hóa thông tin.Nhập môn Số học và Thuật toán 2/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcMục tiêu Cung cấp cho sinh viên các kiến thức cơ bản của số học và thuật toán, bao gồm các định nghĩa, định lý, các bài toán cũng như các vấn đề tiêu biểu trong số học. Trình bày các ý tưởng và các cài đặt cơ bản của các thuật toán liên quan đến việc biểu diễn, tính toán, giải quyết các vấn đề của số học trên máy tính. Giới thiệu một số ứng dụng tiêu biểu của số học trong các lĩnh vực mật mã và mã hóa.Nhập môn Số học và Thuật toán 3/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcYêu cầu Sinh viên cần tham dự các buổi học lý thuyết và thực hành, tham khảo tài liệu, làm bài tập nhóm, ... để có thể nắm đầy đủ nội dung chương trình. Sinh viên cần có các kỹ năng tính toán, suy luận, chứng minh, ... để có thể hiểu rõ và nắm vững các kiến thức nền tảng của số học. Sinh viên cần có các kỹ năng tư duy logic, lập trình, debug, ... để có thể cài đặt và kiểm tra các thuật toán của số học.Nhập môn Số học và Thuật toán 4/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcNội dung lý thuyết 1 Thuật toán 2 Số nguyên 3 Các hàm số học 4 Thặng dư bình phương 5 Đường cong Elliptic 6 Một số thuật toán phân tích số nguyên 7 Một số thuật toán giải bài toán logarit rời rạc 8 Ứng dụng số học vào lý thuyết mật mãNhập môn Số học và Thuật toán 5/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcNội dung thực hành 1 Ngôn ngữ lập trình Python 2 Tính toán trên số nguyên 3 Các hàm số học và tính thặng dư bình phương 4 Tính toán đường cong Elliptic trên trường Zp 5 Kiểm tra số nguyên tố 6 Tìm căn theo modulo n 7 Phân tích số nguyên 8 Giải bài toán logarit rời rạcNhập môn Số học và Thuật toán 6/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcTài liệu tham khảo 1 Hà Huy Khoái, Phạm Huy Điển, Số học thuật toán, Hà Nội, 2002, NXB Đại học Quốc Gia Hà Nội. 2 Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, Handbook of Applied Cryptography, 1997, CRC Press. 3 Douglas R. Stinson, Cryptography - Theory and Practice, 3rd Edition, Ontario, 1995, CRC Press. 4 David M. Burton, Elementary Number Theory, 2nd Edition, Massachusetts, 1980, Allyn and Bacon. 5 Allen Downey, ThinkPython, Massachusetts, 2008, Green Tee Press.Nhập môn Số học và Thuật toán 7/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcTài liệu tham khảo 6 H. C. William, M. C. Wunderlich, On the Parallel Generation of the Residues for the Contrinued Fraction Factoring Algorithm, Mathematics of Computation Vol 48, 1987, American Mathematical Society. 7 Donald E. Knuth, The Art of Computer Programming, Vol. 2 - Seminumerical Algorithms, 3rd Edition, Canada, 1998, Addison Wesley. 8 T. M. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, 2001, The MIT Press.Nhập môn Số học và Thuật toán 8/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcPhương pháp đánh giá Bài tập lý thuyết và thực hành: 20% Kiểm tra giữa kỳ: 15% Thảo luận đề tài: 15% Kiểm tra cuối kỳ: 50%Nhập môn Số học và Thuật toán 9/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tụcCâu hỏi Q&ANhập môn Số học và Thuật toán 10/54Giới thiệu Thuật toán Số nguyên Số nguyên tố Euclide Alg. CRT Phân số liên tục ...