Đồ án tốt nghiệp: Phương pháp nhận biết số nguyên tố dạng 2n-1

Chia sẻ: Đào Nhiên Nhiên | Ngày: | Loại File: PDF | Số trang:67

Thêm vào BST

Báo xấu

6
lượt xem 2
download

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

Khóa luận tốt nghiệp "Phương pháp nhận biết số nguyên tố dạng 2n-1" nhằm tìm hiểu về vai trò của số nguyên tố trong an toàn bảo mật thông tin; tìm hiểu các phương pháp nhận biết số nguyên tố dạng 2n-1; cài đặt chương trình thử nghiệm. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Đồ án tốt nghiệp: Phương pháp nhận biết số nguyên tố dạng 2n-1

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG ----------------------------------- ĐỒ ÁN TỐT NGHIỆP NGÀNH : CÔNG NGHỆ THÔNG TIN Sinh viên : Đỗ Hoàng Anh Giảng viên hướng dẫn : TS Hồ Văn Canh HẢI PHÒNG – 2023
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG ----------------------------------- PHƯƠNG PHÁP NHẬN BIẾT SỐ NGUYÊN TỐ 2N-1 ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY NGÀNH: CÔNG NGHỆ THÔNG TIN Sinh viên : Đỗ Hoàng Anh Giảng viên hướng dẫn : TS Hồ Văn Canh HẢI PHÒNG – 2023
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG -------------------------------------- NHIỆM VỤ ĐỀ TÀI TỐT NGHIỆP Sinh viên: Đỗ Hoàng Anh Mã SV: 1812101004 Lớp : CT2201C Ngành : Công nghệ thông tin Tên đề tài: Phương pháp nhận biết số nguyên tố dạng 2n-1
NHIỆM VỤ ĐỀ TÀI 1. Mô tả tóm tắt đề tài: - Tìm hiểu về vai trò của số nguyên tố trong an toàn bảo mật thông tin - Tìm hiểu các phương pháp nhận biết số nguyên tố dạng 2n-1 - Cài đặt chương trình thử nghiệm. 2.Các tài liệu cần thiết [1] Hồ Văn Canh, Lê Danh Cường (2018): Mật mã và an toàn thông tin: Lý thuyết và ứng dụng. NXB: Thông tin và Truyền thông – 8/2018. [2] Mennezes, Paul C. Van Oorschot, S cott A. Vanstone (1999): Handbook of Applied Cryptography. CRC Press: Boca Raton, New York, London, Tokyo. [3] Neal Koblitz (2000): A Course in Number Theory and Cryptography. Springer-Verlag Press: New York, Berlin Heidelberg, London, Pái, and Tokyo (2000). [4] Phan Đình Diệu (2002): Mật mã và an toàn thông tin. NXB Đại học Quốc gia Hà Nội năm 2002 .[5] Trịnh Nhật Tiến ( 2003): Mật mã và an toàn CSDL. NXB ĐHQG Hà Nội năm 2003. 3.Địa điểm thực tập tốt nghiệp Công ty cổ phần đầu tư tài chính và công nghệ Datatech
CÁN BỘ HƯỚNG DẪN ĐỀ TÀI TỐT NGHIỆP Họ và tên : Hồ Văn Canh Học hàm, học vị : Đại Tá-Tiến Sĩ Cơ quan công tác : Học Viện Kỹ Thuật Mật Mã Nội dung hướng dẫn: Nội dung dự kiến - Một số khái niệm cơ bản trong số học, đại số. - Một số phương pháp kiểm tra số nguyên tố. - Ứng dụng của số nguyên tố và thử nghiệm chương trình.. Đề tài tốt nghiệp được giao ngày 17 tháng 4 năm 2023 Yêu cầu phải hoàn thành xong trước ngày 17 tháng 6 năm 2023 Đã nhận nhiệm vụ ĐTTN Đã giao nhiệm vụ ĐTTN Sinh viên Giảng viên hướng dẫn Đỗ Hoàng Anh TS. Hồ Văn Canh Hải Phòng, ngày 8 tháng 6 năm 2023 TRƯỞNG KHOA
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN TỐT NGHIỆP Họ và tên giảng viên: Hồ Văn Canh Đơn vị công tác: Cục Kỹ thuật Nghiệp Vụ-CBA Họ và tên sinh viên: Đỗ Hoàng Anh Ngành: Công nghệ thông tin Đề tài tốt nghiệp: Phương pháp nhận biết số nguyên tố dạng 2n-1. 1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… 2. Đánh giá chất lượng của đồ án/khóa luận(so với nội dung yêu cầu đã đề ra trong nhiệm vụ Đ.T. T.N trên các lý luận, thực tiễn, tính toán số liệu…) …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… 3. Ý kiến của giảng viên hướng dẫn tốt nghiệp Đạt Không đạt Điểm:…………………………………. Hải Phòng, ngày 8 tháng 6 năm 2023 Giảng viên hướng dẫn (Ký và ghi rõ họ tên)
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN CHẤM PHẢN BIỆN Họ và tên giảng viên: Đơn vị công tác: Họ và tên sinh viên: Đỗ Hoàng Anh Ngành: Công nghệ thông tin Đề tài tốt nghiệp:. 1. Phần nhận xét của giảng viên chấm phản biện …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… 2. Những mặt còn hạn chế …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… …………………………………………………………………………………… 3. Ý kiến của giảng viên chấm phản biện Được bảo vệ Không được bảo vệ Điểm………… Hải Phòng, ngày 13 tháng 6 năm 2023 Giảng viên chấm phản biện (Ký và ghi rõ họ tên)
LỜI CẢM ƠN Lời đầu tiên, em xin gửi lời cảm ơn chân thành đến các Thầy Cô trong Khoa Công Nghệ Thông, Trường Đại học Quản Lý và Công Nghệ Hải Phòng đã giảng dạy, chỉ bảo cho em kiến thức và kinh nghiệm quý báu trong suốt 4 năm học tại trường để em có thể thực hiện đồ án tốt nghiệp này. Đặc biệt em xin gửi lời cảm ơn sâu sắc tới Thầy Hồ Văn Canh người đã trực tiếp hướng dẫn và tận tình giúp đỡ em hoàn thành tốt đồ án tốt nghiệp của mình. Em cũng xin cảm ơn Cô Nguyễn Thị Xuân Hương – Lãnh đạo Khoa Công Nghệ Thông Tin đã luôn tạo điều kiện cho em và các bạn trong suốt quá trình học cũng như thực hiện các công tác tốt nghiệp. Em xin trân trọng cảm ơn Ban lãnh đạo, các Thầy Cô ở các phòng ban của Trường ĐH Quản Lý và Công Nghệ Hải Phòng đã cho em môi trường học tập tốt nhất có thể từ khi em bắt đầu đặt chân vào giảng đường và cho đến khi hoàn thành đồ án tốt nghiệp quan trọng nhất trong cuộc đời sinh viên. Trong quá trình thực tập, cũng như là trong quá trình làm đồ án tốt nghiệp em không tránh khỏi những thiếu sót về trình độ lý luận cũng như kinh nghiệm thực tiễn nên em rất mong sự đóng góp ý kiến và chỉ bảo từ Thầy, Cô để em tiến bộ hơn và có thêm nhiều kinh nghiệm và kiến thức để có thể góp ích cho những công việc sau này. Em xin chân thành cảm ơn!
LỜI CAM ĐOAN Em xin cam đoan rằng đề tài này được tiến hành một cách minh bạch, công khai. Mọi thứ được dựa trên sự cố gắng cũng như sự nỗ lực của bản thân cùng với sự giúp đỡ của thầy Hồ Văn Canh. Các số liệu và kết quả nghiên cứu được đưa ra trong đồ án là trung thực và không sao chép hay sử dụng kết quả của bất kỳ đề tài nghiên cứu nào tương tự. Nếu như phát hiện rằng có sự sao chép kết quả nghiên cứu đề những đề tài khác bản thân em xin chịu hoàn toàn trách nhiệm. Hải Phòng, ngày 13 tháng 6 năm 2022 Sinh viên (Ký và ghi rõ họ tên)
MỤC LỤC LỜI CẢM ƠN ...................................................................................................... 1 LỜI CAM ĐOAN ................................................................................................ 1 DANH MỤC HÌNH ............................................................................................. 1 DANH MỤC VIẾT TẮT .................................................................................... 1 MỞ ĐẦU .............................................................................................................. 1 CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN ....................................................... 9 1.1.MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC, ĐẠI SỐ ................................ 22 1.1.1. Khái niệm trong số học ...................................................................... 22 1.1.2.Khái niệm trong đại số ........................................................................ 22 1.2.MỘT SỐ THUẬT TOÁN .......................... Error! Bookmark not defined. 1.2.1.Thuật toán tính ước chung lớn nhất .... Error! Bookmark not defined. 1.2.2.Thuật toán tính phần từ nghịch đảo theo Modulo .... Error! Bookmark not defined. 1.2.3.Thuật toán phân tích một số ra các thừa số nguyên tố ................. Error! Bookmark not defined. 1.3. ĐỘ PHỨC TẠP TÍNH TOÁN ................. Error! Bookmark not defined. 1.3.1. Khái niệm về độ phức tạp tính toán ... Error! Bookmark not defined. 1.3.2. Lớp phức tạp....................................... Error! Bookmark not defined. 1.3.3. Hàm một phía và cửa sập một phía .... Error! Bookmark not defined. Kết luận ............................................................ Error! Bookmark not defined. CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP KIỂM TRA SỐ NGUYÊN TỐ ............................................................................. Error! Bookmark not defined. 2.1. SỐ NGUYÊN TỐ ..................................................................................... 25 2.1.1.Khái niệm số nguyên tố ....................................................................... 25 2.1.2. Tính chất của số nguyên tố................................................................. 25 2.1.3: Định lý cơ bản của số học .................................................................. 26 2.1.4: Sự phân bố của số nguyên tố.............................................................. 26 2.2. SỐ NGUYÊN TỐ CÓ DẠNG ĐẶC BIỆT ............. Error! Bookmark not defined. 2.2.1 Số nguyên tố Mersenne ....................... Error! Bookmark not defined. 2.2.2. Số nguyên tố Lucas-Lehmer .............. Error! Bookmark not defined. 2.2.3.Số nguyên tố dạng Fermat ................... Error! Bookmark not defined.
2.3. MỘT SỐ PHƯƠNG PHÁP KIỂM TRA SỐ NGUYÊN TỐ ............ Error! Bookmark not defined. 2.3.1 Phương pháp cổ điển ........................... Error! Bookmark not defined. 2.3.2 Phương pháp xác suất.......................... Error! Bookmark not defined. 2.4 Kết luận ...................................................... Error! Bookmark not defined. CHƯƠNG 3: ỨNG DỤNG CỦA SỐ NGUYÊN TỐ VÀ THỬ NGHIỆM CHƯƠNG TRÌNH ............................................................................................ 38 3.1. THỬ NGHIỆM CHƯƠNG TRÌNH ......... Error! Bookmark not defined. 3.1.1. Cấu hình hệ thống............................... Error! Bookmark not defined. 3.1.2. Chức năng chính ................................. Error! Bookmark not defined. 3.1.3. Cài đặt hệ thống.................................. Error! Bookmark not defined. KẾT LUẬN ........................................................................................................ 46 TÀI LIỆU THAM KHẢO ................................................................................ 54
DANH MỤC HÌNH Hình 1.2.1: Mô tả quá trình tính toán của thuật toán Euclid.... Error! Bookmark not defined. Hình 1.2.2: Mô tả quá trình tính toán của thuật toán Euclid mở rộng ......... Error! Bookmark not defined. Hình 1.2.3.1: Thuật toán phân tích thừa số n-1... Error! Bookmark not defined. Hình 1.3: Thuật toán phân tích thừa số(cho trước số mũ giải mã a) ........... Error! Bookmark not defined. Hình 1.4: Thuật toán phân tích cổ điển ............... Error! Bookmark not defined. Hình 2.2.1.2: Đồ thị biểu diễn các chứ số của số nguyên tố Mersenne lớn nhất đã biết theo từng năm của kỳ nguyên điện tử .......... Error! Bookmark not defined. Hình 3.1.3 Kiểm tra số nguyên tố 2,5000 ........... Error! Bookmark not defined. Hình 3.1.4 Kết quả trả về của chương trình số nguyên tố 2n -1, của 2,11213 ............................................................................. Error! Bookmark not defined. Hình 3.1.5 Kết quả nhận được sau khi liệt kê từ 1 -> 5000 ..... Error! Bookmark not defined. Hình 3.1.5 Phân tích thừa số nguyên tố 27,102,1001,5000 ..... Error! Bookmark not defined. DANH MỤC TỪ VIẾT TẮT Từ viết tắt Tiếng Anh Tiếng Việt Ged Greatest Common Divisor Ước số chung lớn nhất Lcm Least Common Multiple Bội số chung nhỏ nhất Mod Modulo
MỞ ĐẦU Ta biết rằng số nguyên tố và đặt biệt là số nguyên tố lớn đóng vai trò rất quan trọng trong nhiều lĩnh vực về an toàn – bảo mật thông tin như: Trong hạ tần cơ sở khóa công khai, trong các hệ mật mã RSA, Elgamal, trong xác thực và chữ ký điện tử, vv. Tuy nhiên một vấn đề đặt ra là làm thế nào để khẳng định mốt số nguyên dương N nào đó là số nguyên tố hay hợp số? Ta biết rằng số nguyên tố là một số chia hết cho một và chính nó. Như vậy số nguyên tố là một số nguyên (dương) lẻ? Vì nếu nó là số chẵn thì nó sẽ chia hết cho 2 và như vậy, nó không phải là một số nguyên tố. Vậy số nguyên tố (trừ số 2) là một số lẻ. Nhưng số lẻ chưa hẳn đã là số nguyên tố. ví dụ: Số 9 là số lẻ nhưng không phải là số nguyên tố. Số 15 là số lẻ nhưng cũng không phải là số nguyên tố. Vì (15 = 3.5) là hợp số. Số 2047 cũng không phải là số nguyên tố vì (2047 = 23.89) Vậy cho một số nguyên lẻ n bất kỳ làm thể nào để nhận biết được n là số nguyên tố (chỉ chia hết cho 1 và chính nó)? Đến nay đã có nhiều tài liệu nghiên cứu về vấn đề này chẳng hạn trong Knut(2004):” The Artof Programming Computer” (Tập II- 2004): “ chẳng hạn thuật toán sàng bình phương “ (Quadratic Sieve algerithin) [1: Alfred J. Menezes, Pau C.van Oorschot and Scott A.Vanstone (1998) CRC press: Boca Raton. Newyork, London and Tokyo(1998) ]. 1
Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. MỘT SỐ KHÁI NIỆM TRONG SỐ HỌC, ĐẠI SỐ 1.1.1. Khái niệm trong số học 1). Ký hiệu chia hết Cho a và b là hai số nguyên dương. Số a chia hết cho số b ký hiệu là a b  Tồn tại n  N sao cho: a=b*n Khi đó người ta nói b là ước của a và ký hiệu: b | a. 2). Ước số chung lớn nhất Cho a và b là hai số nguyên dương. Ước số chung lớn nhất của a và b là số tự nhiên m lớn nhất sao cho m | a và m | b. Khi đó ký hiệu là gcd(a, b) = m. 3). Hai số nguyên tố cùng nhau Cho a và b là hai số nguyên dương. Số a và số b được gọi là 2 nguyên tố cùng nhau  gcd(a, b) = 1. 4). Đồng dư modulo Cho n  N, n  0 và a, b  * Zn . Ký hiệu a  b (mod n) nghĩa là a đồng dư với b theo mod n  Tồn tại số nguyên k  * Zn sao cho a = b + k * n Tức là (a - b) = k * n, như vậy n | (a - b). 5). Một số tính chất của đồng dư modulo (a  b) (mod n)  [(a mod n)  (b mod n)] (mod n) (a * b) (mod n)  [(a mod n) * (b mod n)] (mod n) 1.1.2. Khái niệm trong đại số 2
1). Khái niệm nhóm Nhóm là một cặp (G, *), trong đó G là tập hợp khác rỗng, * là phép toán hai ngôi trên G thoả mãn ba điều kiện sau: 1. Phép toán có tính kết hợp: (x * y) * z = x * (y * z) với mọi x, y, z G. 2. Có phần tử phần tử trung lập e  G: x * e = e * x = x với mọi x  G. 3. Với mọi x  G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e 2). Nhóm con Cho G là một Nhóm, cho S  G và S  . S được gọi là Nhóm con của G nếu: 1/. Phần tử trung lập e của G nằm trong S. 2/. S khép kín đối với luật hợp thành trong G (tức là x * y  S với mọi x, y S). 3/. S khép kín đối với phép lấy nghịch đảo trong G (tức x-1  S với mọi xS). 3). Nhóm Cyclic a). Khái niệm Nhóm Cyclic Nhóm (G, *) được gọi là Nhóm Cyclic nếu nó được sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để g n = g * g * … * g = a (Chú ý: g * g * … * g là g * g với n lần). Khi đó g được gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. 3
Nói cách khác: G được gọi là Nhóm Cyclic nếu tồn tại g  G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. Ví dụ: Nhóm (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1. b). Cấp của Nhóm Cyclic: Cho (G, *) là Nhóm Cyclic với phần tử sinh g và phần tử trung lập e. Nếu tồn tại số tự nhiên nhỏ nhất n mà g n = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g 2 , g 3 , . . . , g n - 1 . Khi đó G được gọi là nhóm Cyclic hữu hạn cấp n. Nếu không tồn tại số tự nhiên n để g n = e, thì G có cấp . Ví dụ: (Z + , +) gồm các số nguyên dương là Cyclic với phần tử sinh g = 1, e = 0. Đó là Nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để g n = e, c). Cấp của một phần tử trong Nhóm Cyclic: Phần tử   G được gọi là có cấp d, nếu d là số nguyên dương nhỏ nhất sao cho  d = e, trong đó e là phần tử trung lập của G. Như vậy phần tử  có cấp 1, nếu  = e. 4). Tập Zn và Z* Zn = 0, 1, 2, .. . , n - 1. Tức Zn là tập các số nguyên không âm < n. Tập này cùng với phép cộng lập thành Nhóm Cyclic có phần tử sinh là 1. Đó là Nhóm hữu hạn có cấp n. Zn * = e  Zn, e là nguyên tố cùng nhau với n. Tức là e # 0. Đó là tập các số nguyên dương < n, nhưng nguyên tố cùng nhau với n. được gọi là tập Thặng dư thu gọn theo mod n, lập thành một Nhóm với phép nhân mod n. (n) là số các phần tử của tập 𝑧 ∗𝑛 . 4
5). Một số kết quả Những kết quả sau đã được chứng minh, nhắc lại để sử dụng: * Định lý Lagrange: Cho G là nhóm Cấp n và g G. Khi đó cấp của g là ước của n. * Hệ quả: Giả sử g 𝑧 ∗𝑛 có Cấp m thì m là ước của  (n). Nếu b  * 𝑧 ∗𝑛 thì b (n)  1 (mod n). Nếu p là số nguyên tố thì  (p) = p -1. Do đó với mọi b  * 𝑧 ∗𝑝 (tức b nguyên tố với p) thì b (p)  1 (mod n) hay b p -1  1 (mod n). * Định lý: Nếu p là số nguyên tố thì 𝑧 ∗𝑝 là Nhóm Cyclic. Chú ý: Phần tử   𝑧 ∗𝑛 có cấp d nếu d là số nguyên dương nhỏ nhất sao cho d = e trong 𝑧 ∗𝑛 , tức là  d  1 (mod n). 6). Khái niệm Logarit rời rạc Cho p là số nguyên tố,  là phần tử nguyên thuỷ của Zp,  𝑧 ∗𝑛 . Logarit rời rạc chính là việc giải phương trình x = log  (mod p) với ẩn x. Hay phải tìm số x duy nhất sao cho:  x   (mod p). - Bổ đề: Nếu (a, n) = 1 thì tồn tại a-1  Zn thoả mãn a * a-1  1 (mod n). - Định lý (Euler tổng quát): Nếu (a, n) = 1 thì a(n) mod n = 1. - Hệ quả: Với p là một số nguyên tố và (a, p) = 1 thì ap-1 (mod p) = 1. 1.2. MỘT SỐ THUẬT TOÁN 1.2.1. Thuật toán tính ước chung lớn nhất 5
Ký hiệu Z là tập hợp các số nguyên, Z = { ..., -2, -1, 0, 1, 2, ...}, và Z+ là tập hợp các số nguyên không âm, Z+ = {0, 1, 2, ...}. Trong mục này sẽ nhắc lại một số kiến thức về số học của các số nguyên cần cho việc trình bày lý thuyết mật mã. Vì để luận văn không quá dài dòng, các kiến thức sẽ được nhắc đến chủ yếu là các khái niệm, các mệnh đề sẽ được sử dụng, v.v..., còn các phần chứng minh sẽ được lược bỏ. Tập hợp Z là đóng kín đối với các phép cộng, trừ và nhân, nhưng không đóng kín đối với phép chia: chia một số nguyên cho một số nguyên không phải bao giờ cũng được kết quả là một số nguyên! Vì vậy, trường hợp chia hết, tức khi chia số nguyên a cho số nguyên b được thương là một số nguyên q, a = b.q, có một ý nghĩa đặc biệt. Khi đó, nói a chia hết cho b, a là bội số của b, b là ước số của a, và ký hiệu là b|a. Dễ thấy ngay rằng số 1 là ước số của mọi số nguyên bất kỳ, số 0 là bội số của mọi số nguyên bất kỳ, mọi số nguyên a đều là ước số, đồng thời là bội số của chính nó. Định lý 1.2 Nếu b > 0 và b|a thì gcd(a,b) = b. Nếu a = bq +r thì gcd(a,b) = gcd(b,r). Một số nguyên m được gọi là bội số chung của a và b nếu a|m và b|m. Số m được gọi là bội số chung bé nhất của a và b và được ký hiệu là lcm(a,b), nếu m>0, m là bội số chung của a và b, và mọi bội số chung của a và b đều là bội của m. Ví dụ lcm(14,21) = 42. Với hai số nguyên dương a và b bất kỳ ta có quan hệ lcm(a,b).gcd(a,b) = a.b. Từ định lý 1.2 ta suy ra thuật toán sau đây thực hiện việc tìm ước số chung lớn nhất của hai số nguyên bất kỳ: Thuật toán Euclide tìm ước số chung lớn nhất: INPUT: hai số nguyên không âm a và b, với a≥b. OUTPUT: ước số chung lớn nhất của a và b 6
1. Trong khi còn b>0, thực hiện: 1.1. đặt r  a mod b,a  b, b  r. 2. Cho ra kết quả (a). Ví dụ: Dùng thuật toán Euclide tìm gcd(4864, 3458), lần lượt được các giá trị gán cho các biến a, b và r như sau: Bảng 1.2.1. Mô tả quá trình tính toán của thuật toán Euclid a b c 4864 = 1.3458 + 1406 4864 3458 3458 = 2.1406 + 646 3458 1406 1406 1406 = 2.646 + 114 1406 646 646 646 = 5.114 + 76 646 114 114 114 = 1.76 +38 114 76 76 76 = 2.38 +0 76 38 38 38 0 0 Cho hai số nguyên bất kỳ a và b, b > 1. Thực hiện phép chia a cho b ta sẽ được hai số q và r sao cho a = b.q + r, 0 ≤ r 0, d là ước số chung của a và b, và mọi ước chung của a và b đều là ước số của d. Ký hiệu ước số chung lớn nhất của a và b là gcd (a,b). Ví dụ gcd (12, 18) = 6, gcd (- 18, 27) = 3. Dễ thấy rằng với mọi số nguyên dương a ta có gcd (a, 0) = a, ta cũng sẽ qui ước xem rằng gcd (0,0) = 0. 7