Đồ án tìm hiểu và mô phỏng thuật giải RSA trên MATLAB - ĐH Sư phạm Kỹ thuật TP.HCM

Đồ án tìm hiểu và mô phỏng thuật giải RSA trên MATLAB ngành Điện - Điện tử ĐH Sư phạm Kỹ thuật TP.HCM. Phân tích thuật toán mã hóa khóa công khai chi tiết.

• Tác giả: Nguyễn Đức Huy
• Người hướng dẫn: ThS. Lê Minh Thanh
• Trường học: Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh
• Chuyên ngành: Kỹ thuật Điện - Điện tử
• Đề tài: Tìm hiểu và mô phỏng thuật giải RSA trên MATLAB
• Loại tài liệu: Đồ án tốt nghiệp
• Năm xuất bản: 2012
• Địa điểm: Hồ Chí Minh

Tóm tắt

I. Tổng quan về mô phỏng thuật giải RSA trên MATLAB

Đề tài tốt nghiệp tại Đại học Sư phạm Kỹ thuật TP.HCM tập trung nghiên cứu an toàn thông tin số. Thuật giải RSA là hệ thống mã hóa bất đối xứng tiêu biểu. Hệ thống sử dụng cặp khóa công khai và khóa bí mật. Quá trình bảo mật dựa trên độ khó của bài toán phân tích thừa số nguyên tố lớn. Phần mềm MATLAB cung cấp môi trường tính toán ma trận mạnh mẽ. Công cụ hỗ trợ xử lý số nguyên lớn và thuật toán đại số phức tạp. Nghiên cứu kết hợp lý thuyết mật mã học và kỹ thuật lập trình mô phỏng. Đồ án xây dựng giao diện trực quan và khối lệnh xử lý hoàn chỉnh. Người học dễ dàng quan sát quy trình biến đổi thông điệp rõ ràng. Mô phỏng giúp đơn giản hóa lý thuyết trừu tượng trong truyền thông dữ liệu. Các phép tính lũy thừa modulo được thực hiện chuẩn xác. Tốc độ xử lý của MATLAB đáp ứng tốt yêu cầu thực nghiệm học thuật. Công trình khẳng định giá trị ứng dụng của mô phỏng trong đào tạo kỹ thuật điện tử viễn thông.

1.1. Bối cảnh nghiên cứu tại ĐH Sư phạm Kỹ thuật TP.HCM

Ngành Kỹ thuật Điện - Điện tử trường ĐH Sư phạm Kỹ thuật TP.HCM luôn chú trọng thực hành. Sự phát triển mạnh của viễn thông đòi hỏi các giải pháp an ninh mạng tối ưu. Sinh viên thực hiện đề tài tốt nghiệp dưới sự hướng dẫn của ThS. Lê Minh Thanh. Mục tiêu đề tài là làm sáng tỏ bản chất an toàn của hệ thống mật mã phi đối xứng. Việc triển khai trên máy tính giúp kiểm chứng lý thuyết toán rời rạc một cách trực quan. Sinh viên xây dựng các kịch bản mã hóa thực tế để đánh giá hiệu năng. Kết quả đề tài cung cấp tài liệu tham khảo giá trị cho sinh viên khóa sau. Công trình phản ánh tinh thần nghiên cứu ứng dụng thực tiễn của nhà trường.

1.2. Mục tiêu và phạm vi của mô phỏng thuật toán RSA

Đề tài xác định hai mục tiêu chính gồm phân tích toán học và lập trình thực nghiệm. Phạm vi nghiên cứu tập trung vào cơ chế sinh khóa, mã hóa và giải mã chuỗi ký tự. MATLAB đóng vai trò là nền tảng xử lý dữ liệu và mô phỏng giao diện. Các thuật toán hỗ trợ gồm tìm số nguyên tố, ước chung lớn nhất và hàm Euler. Đề tài không đi sâu vào việc giải mã tấn công thô bạo trên khóa dài. Trọng tâm hướng tới tính chính xác của thuật toán và tốc độ tính toán. Mô hình mô phỏng cho phép nhập bản rõ tùy ý và kiểm tra bản mã sinh ra. Dữ liệu giải mã được so sánh trực tiếp với bản gốc để xác thực tính toàn vẹn.

II. Phân tích nguyên lý toán học của thuật giải RSA trên MATLAB

Độ an toàn của thuật toán RSA phụ thuộc trực tiếp vào nền tảng số học modulo. Thuật toán đòi hỏi lựa chọn hai số nguyên tố ngẫu nhiên p và q rất lớn. Tích số n = p * q tạo thành mô-đun cho cả khóa công khai và khóa bí mật. Việc tính toán hàm Euler phi(n) = (p - 1) * (q - 1) là bước then chốt. Người dùng chọn khóa công khai e nguyên tố cùng nhau với phi(n). Khóa bí mật d là phần tử nghịch đảo modulo của e theo phi(n). Định lý Euclid mở rộng giải quyết phương trình e * d = 1 mod phi(n). Thách thức lớn nằm ở việc phân tích thừa số n nếu kẻ tấn công chỉ biết e và n. Khi kích thước khóa tăng lên, chi phí tính toán để phá mã trở nên bất khả thi. Tuy nhiên, việc tính toán lũy thừa số mũ lớn gây ra hiện tượng tràn bộ nhớ máy tính. MATLAB cần các thuật toán nhân lũy thừa nhanh để giảm thiểu độ phức tạp thời gian. Quy trình tính toán đòi hỏi độ chính xác tuyệt đối ở từng phép tính modulo.

2.1. Phép toán modulo và phần tử nghịch đảo số học

Phép chia lấy dư modulo là nền tảng cốt lõi của lý thuyết mật mã. Hai số a và b đồng dư theo modulo n khi chúng có cùng số dư khi chia cho n. Phần tử nghịch đảo modulo a^-1 tồn tại khi và chỉ khi a và n nguyên tố cùng nhau. Điều kiện này bảo đảm tính duy nhất của nghiệm toán học. Thuật toán Euclid mở rộng được dùng để tìm phần tử nghịch đảo này một cách hiệu quả. Phép tính cho phép tái tạo thông điệp gốc từ chuỗi mã hóa mà không làm mất thông tin. Nếu điều kiện nguyên tố cùng nhau bị vi phạm, quá trình giải mã hoàn toàn thất bại. Phép modulo tạo thành vòng lặp hữu hạn vững chắc cho không gian khóa.

2.2. Vấn đề an toàn số nguyên tố và hàm phi Euler

Độ bảo mật của hệ thống phụ thuộc hoàn toàn vào kích thước của hai số nguyên tố p và q. Hàm phi Euler phi(n) giữ vai trò then chốt trong cấu trúc sinh khóa bí mật. Khi hai số nguyên tố đủ lớn, việc tính toán phi(n) từ số n công khai là cực kỳ khó khăn. Các máy tính tiêu chuẩn không thể phân tích n thành tích hai số thừa số trong thời gian hữu hạn. Tuy nhiên, nếu thuật toán sinh số ngẫu nhiên kém an toàn, khóa sẽ dễ bị suy đoán. Kẻ tấn công có thể áp dụng các thuật pháp vét cạn hoặc thuật toán Fermat. Do đó, việc sinh số nguyên tố ngẫu nhiên và kiểm tra tính nguyên tố chuẩn xác là yêu cầu sống còn. Cơ chế này đảm bảo dữ liệu được bảo vệ an toàn tối đa.

III. Phương pháp mô phỏng thuật giải RSA trên MATLAB chi tiết

Mô phỏng thuật toán trên MATLAB được thiết kế theo cấu trúc module hóa rõ ràng. Chương trình gồm bốn module chính: sinh khóa, nhập văn bản, mã hóa và giải mã. Bước đầu tiên sử dụng các lệnh ngẫu nhiên để chọn cặp số nguyên tố p và q. Hệ thống tính giá trị tích n và hàm Euler phi(n) tự động. Khóa công khai e được xác định qua hàm kiểm tra ước chung lớn nhất gcd. Khóa riêng d được giải bằng thuật toán Euclid mở rộng. Khi mã hóa, chuỗi ký tự bản rõ được chuyển đổi thành mã ASCII tương ứng. Lệnh tính toán lũy thừa modulo xử lý từng khối số nguyên: c = m^e mod n. Khi nhận được bản mã c, bên nhận thực hiện phép giải mã: m = c^d mod n. MATLAB cung cấp các lệnh lập trình mạnh như eval, vòng lặp for và toán tử quan hệ. Cấu trúc ma trận giúp tăng tốc độ xử lý hàng loạt ký tự đồng thời. Kết quả bản rõ sau giải mã được khôi phục chính xác so với bản gốc ban đầu.

3.1. Các hàm lập trình và lệnh điều khiển trong MATLAB

Môi trường MATLAB cung cấp hệ thống toán tử phong phú phục vụ tính toán số học. Nhóm lệnh điều khiển gồm cấu trúc vòng lặp for và rẽ nhánh if - else xử lý luồng thuật toán. Lệnh eval chuyển đổi linh hoạt chuỗi ký tự thành biểu thức thực thi trực tiếp. Toán tử logic AND, OR, NOT kết hợp toán tử quan hệ hỗ trợ kiểm tra điều kiện nguyên số. Các ký hiệu đặc biệt như dấu ngoặc vuông và dấu chấm phẩy quản lý cấu trúc ma trận hiệu quả. Dấu phần trăm dùng ghi chú thích mã nguồn rõ ràng, thuận tiện cho việc hiệu chỉnh. Kỹ thuật lập trình vector hóa của MATLAB tối ưu hóa tốc độ tính toán cho các phép tính modulo lớn.

3.2. Quy trình mã hóa và giải mã thông điệp trên phần mềm

Quy trình xử lý bắt đầu khi người dùng nhập chuỗi văn bản từ giao diện chương trình. Mỗi ký tự lập tức được chuyển đổi sang số nguyên theo bảng mã chuẩn ASCII. Hệ thống áp dụng công thức mã hóa lũy thừa modulo trên từng phần tử số. Bản mã sinh ra tồn tại dưới dạng chuỗi số nguyên phân cách nhau rõ ràng. Chuỗi số này được gửi qua kênh truyền mô phỏng tới bộ phận giải mã. Bên nhận sử dụng khóa bí mật d cùng khóa mô-đun n để thực thi giải mã. Phép tính lũy thừa modulo nghịch đảo chuyển đổi bản mã về các số ASCII ban đầu. Cuối cùng, hàm ký tự khôi phục hoàn chỉnh nội dung văn bản nguyên bản mà không gặp lỗi.

IV. Đánh giá ứng dụng mô phỏng thuật giải RSA trên MATLAB

Đồ án tốt nghiệp tại Đại học Sư phạm Kỹ thuật TP.HCM đạt được các kết quả thực nghiệm chuẩn xác. Mô hình mô phỏng chứng minh tính khả thi và độ tin cậy của thuật giải RSA. Phần mềm MATLAB thể hiện năng lực vượt trội trong xử lý toán học ma trận và số nguyên lớn. Kết quả giải mã trùng khớp hoàn toàn với thông điệp đầu vào của hệ thống. Ứng dụng giúp sinh viên nắm vững nguyên lý mật mã học một cách trực quan và sinh động. Công trình là cơ sở để phát triển các hệ thống bảo mật trong mạng truyền thông thực tế. Tuy nhiên, giới hạn tốc độ tính toán xuất hiện khi kích thước khóa RSA vượt ngưỡng lớn. Các nghiên cứu tiếp theo có thể tích hợp thuật toán tăng tốc phần cứng chuyên dụng. Việc kết hợp MATLAB với ngôn ngữ C hoặc VHDL sẽ mở ra hướng triển khai vi mạch bảo mật cao cấp. Đề tài đóng góp tài liệu học thuật thiết thực cho ngành kỹ thuật điện tử và viễn thông.

4.1. Hiệu quả ứng dụng trong giảng dạy và nghiên cứu kỹ thuật

Mô phỏng thuật giải RSA mang lại giá trị thực tiễn cao trong môi trường giáo dục đại học. Sinh viên có thể trực tiếp tương tác, thay đổi các thông số đầu vào và quan sát kết quả. Phương pháp này biến những khái niệm lý thuyết trừu tượng thành trải nghiệm trực quan dễ hiểu. Giảng viên có thể ứng dụng mã nguồn đề tài làm giáo cụ trực quan cho môn an toàn mạng. Người học phát triển tư duy thuật toán, kỹ năng lập trình số học và khả năng phân tích lỗi. Đồ án tạo tiền đề vững chắc cho việc tiếp cận các chuẩn mật mã hiện đại như AES hay ECC. Mô hình đào tạo thực nghiệm này nâng cao chất lượng học tập rõ rệt.

4.2. Hướng phát triển và tối ưu hóa hệ thống mã hóa RSA

Đề tài mở ra nhiều hướng mở rộng thiết thực cho các nghiên cứu tiếp theo. Hướng phát triển ưu tiên là nâng cấp thuật toán xử lý số nguyên lớn vượt giới hạn chuẩn. Các kỹ thuật như phép nhân Montgomery có thể giảm thời gian tính lũy thừa modulo đáng kể. Việc tích hợp giao diện người dùng đồ họa GUI sẽ tăng cường tính thân thiện khi vận hành. Ngoài ra, việc nhúng thuật toán lên các chip xử lý tín hiệu DSP hoặc vi điều khiển ARM là giải pháp triển vọng. Hướng đi này giúp đưa thuật toán vào các thiết bị IoT và hệ thống viễn thông thực tế. Việc kết hợp mã hóa lai giữa RSA và AES cũng là giải pháp tối ưu cho bảo mật dữ liệu tốc độ cao.

Trích đoạn nội dung tài liệu

Chương 1: Tổng quan về mật mã và mã hóa Tìm hiểu và mô phỏng thuật giải RSA trên matlab $ Trang 19 Public key: Được sử dụng để mã hoá những thông tin ma ta muốn chia sẻ với bắt cứ ai. Chính vì vậy ta có thể tự do phân phát nó cho bất cứ ai mà ta cần chia sẻ thông tin ở dạng mã hoá. Privite key: Đúng như cái tên, Key này thuộc sở hữu riêng tư của bạn(ứng véi public key) và nó được sử dụng đề giải mã thông tin. Chỉ mình bạn sở hữu nó, Key này không được phép và không lên phân phát cho bắt cứ ai.

Nghĩa là mỗi người sẽ giữ 2 key 1 dùng để mã hóa, key này được công bố rộng rãi, | dùng đẻ giải mã, key này giữ kín, Khi ai đó có nhú cầu trao đối thông tìn với bạn, sẻ đùng public key ma bạn công hế để mã hóa thông tin va gui cho bạn, khí nhận được bạn dùng private key để giải tà Những người khác dù có nhận được thông tin nhưng không biết được private key thị cứng kháng thể giái mã và đọc được thong tín. Public-key Private-key, người nhận g2: nhắn | Ban tin for Bản tin mật —~ + - Ban tin rõ Mã hóa Giai ma 1.Mô hình mã hóa công khai 1.Cơ sờ lý thuyết cho hình thức mã hóa công khai Hàm một phía. Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất khó để tính ngược lại. Ví như : biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f{x) thì rất khó tính ra được x.

Trong trường hợp này “khó” có nghĩa là để tính ra được kết quả thì phải mắt hàng triệu năm để tính toán, thậm chí tất cả máy tính trên thế giới này đều tính toán công việc đó. Vậy thì hàm một phía tốt ở những gì ? Chúng ta không thể sử dụng chúng cho sự mã hoá. Một thông báo mã hoá với hàm một phía là không hữu ích, bất kỳ ai Chương 1: Tong quan vê mật mã và mã hóa Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 20 cũng không giải mã được. Đối với mã hoá chúng ta cần một vài điều gọi là cửa sập hàm một phía.(khóa) Hộp thư là một ví dụ rất tuyệt về hàm một phía cũng như hình thức mã hóa này.

Bất kỳ ai cũng có thể bỏ thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không phải là hành động công cộng. Nó là việc khó khăn, khi bạn không có chìa khóa ứng với thùng thư.

Hơn nữa nếu bạn có điều bí mật (chìa khoá), nó thật dễ dàng mở hộp thư. Hệ mã hoá công khai có rất nhiều điều giống như vậy. Chương 1: Tổng quan về mật mã và mã hóa PHÁN B NOI DUNG Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 21 Chương 2 THUẬT GIẢI RSA 2. Giới thiệu hệ mật mã khóa công khai Vào năm 1976 Whitefile Deffie và Martin Hellman đưa ra ý tưởng xây dựng một hệ mật mã mới trên cơ sở hoàn toàn khác các hệ mật mã trước đây.

Hệ mật mã nảy dùng thuật toán mã hóa khác biệt so với thuật toán đối xứng, thỏa các yêu cầu sau: Khóa mã hỏa khòng đổi xứng với khóa giải mã nghĩa là dùng một khóa để mã hóa. dùng khóa khúc đẻ giái mã. Hai khóa này độc lập và khác biệt nhau. Mô tả tông quát các thuật toán không đối xứng Nguyên tắc hoạt động của các hệ mã lá mối bén tham gia truyền tin sẽ có 2 khóa, triết khóa gọi là khóa bí mật và mội khóa cóng khái.

Khóa bí mật là khóa dụng đẻ giải mã và được giữ bí mật (dụ), khóa công khai la khéa dùng để sinh mã được công khai để bất kì ai cũng có thể sử dụng khóa sáy gứi tín cho người chủ của hé ma (e,). ngay nay chúng ta có thé thấy rõ nguyên tác náy trong việc gửi email, mọi người đều có thể gửi email tới một địa chỉ email nao đó, nhưng chỉ có người sở hừu của địa chỉ email đó mới có thể đọc được nội dung của bức thư, còn những người khác thì không. Với các hệ mã khóa công khai việc phân phỏi khóa sẽ trở nên dé dang hon qua các kênh cung cấp khóa công cộng, số lượng khỏa hệ thống quản lý cũng sẽ ít hơn. Các dịch vụ mới như chữ ký điện tử, thỏa thuận khóa cũng được xây dựng dựa trên các hệ mã này.

Các yêu cầu của loại hệ mã này: e_ Việc sinh cặp khóa công khai e, và bí mật d, phải được thực hiện một cách dễ dàng Người gửi A có khóa công khai của người nhận B khi muốn gửi thông điệp M thì cần dùng khóa công khai ey của B để mã hóa bản rõ P thành bản mã C. e« Tiến trình mã hóa thực hiện trong thời gian đa thức. ø„(P) = € Người nhận B khi nhận được thông điệp đã được mã hóa C, dùng khóa bí mật d, cảu mình để giải mã thông điệp C thu được thông điệp ban đầu P. e _ Tiến trình giải mã được thực hiện trong thời gian đa thức.

Chương 2: Thuật giải RSA Tìm hiểu và mô phỏng thuật giài RSA trén matlab Trang 22 d.(c) = d,(e,(P)) =P e©_ Nếu biếtn khóa céng khai e,, thi viée tinh toan dé dé tìm khóa bí mật dụ không thể thực hiện trong thời gian đa thức, không khả thi về thời gian ® Nếu biết được cặp (ey, C) thì không tìm được lời giải để khôi phục bản rõ P. bài toán khó với số phép thử là vô cùng lớn, không kha thi. ® lượt đồ chữ ký số: tạo chữ ký số có tính chất như chữ ký tay và khó giả mạo hơn chữa ký tay, Khóa công, |Khóa bí khai (ey) tật (d¿) Platntext | eecanins dl S| Plaintext A : a B ————m>n Mãhóa Mãahóúa |——> Ciphetext _——————— Hình 2.1: mô hình sử dụng của các hệ mã *háa công khai 2. Nguyên tắc cấu tạo của hệ mã khóa công khai Các hệ mã khóa công khai được xây dựng dựa trên các hàm được gọi là các hàm 1 phía hay hàm 1 chiều (one - way functions).

Hàm một chiều f:X — Y là một hàm nếu biết x e X ta có thể dé dang tính được y = f(x). Nhưng với y bất kỳ e Y việc tìm x eX sao cho x = y~'(y) là khó. Có nghĩa là tìm hàm ngược ƒ * là rất khó. “Dé” nghia là tính được trong thời gian đa thức, “khó” là không tính được trong thời gian đa thức.

Ví dụ nếu có các số nguyên tố Pạ, P; ., P„ thì việc tính n = P,*P,».w P, là đễ nhưng nếu có N thì việc tính ngược lại là một bài toán khó với N lớn. Để thuận tiện các hàm một phía được sử dụng trong các hệ mã khóa công khai thường được trang bị các cửa bẫy (trapdoor) hàm ƒ(x) được gọi là hàm cửa sập một Chương 2: Thuật giải RSA Tìm hiểu và mô phỏng thuật giải RSA trên matlab_ ' Trang 23 chiéu, néu tinh y=f(x) la dé, tinh x = f~*(y) la rdt khó, nhưng có cửa sập z để tính x =f '(y) la dé. Ngày nay, việc dùng các hệ mật mã để mã hóa thông tin đảm bảo an toàn thông tin trong quá trình trao đổi thông tin khá phổ biến. Đặc biệt là hệ mã RSA.

Số học đồng dư Với mỗi cặp sổ a,b € Z chơ trước, b #0, tồn tại cặp số nguyên q, r thỏa (" : nà aos khi dé q 1a phan nguyên, r là phần đư. Nếu r = 0, thì phép chia la 0 <r« |hị phép chía hết, 141.1, khai niệm modulo Định nghĩa: cho a, b, n € Z, n > 0, a gọi là đồng du với b theo modulo n nếu phản dư của a chia m bằng phần dư của b chia n. Ký hiệu: a = b mod 1m nếu n chia hết cho b-a. Ménh dé a = b mod an được gọi là a đồng dư với b theo modulo n.

Ví dụ: 9 = 5 nod 2 Các tính chất của modulo 1. Néu a = bmod nvab =c mod nthia =cmodn iii. Néu a = bmod n,c = d mod nthia+c===b+dmodn Vaa. Phan tir nghich dao theo modulo n Định nghĩa: già sừ a € Z„.

Phan tử nghịch đảo của a mod n là a~Ì € 7„ sao 1—=a~la= 1 mod n. cho aa~ Định lý: nghịch đảo œ~1 của a theo modulo n tồn tại và duy nhất nếu và chỉ nếu a nguyên tố cùng nhau với n. Chứng mình: Chương 2: Thuật giải RSA Tìm hiểu và mô phông thuật giải RS4 trên matiab Trang 24 Nếu aø Ì= 1modm, thì aaÌ=1+km ©aa Ì—km=1=>a và m nguyên tố cùng nhau. lại, nếu a m nguyên t6 cùng nhau ta có aa"!+ km = 1 => aa"Ì= 1 —km, do đó aa"! = 1 mod m Giả sử nếu a có nghịch đảo khác là ø~Ìthì aa”! = aa~ = 1 mod m, do đó: a~1aa”! = a~taz~^ = a~1 z z~? mod m.

Số nguyên tố Số tự nhiên lớn hơn 1 chí chia hết cho 1 và chính nó được gọi là số nguyên tố. có duy nhất một số nguyễn tố chẩn lá: 2 Ñố nguyên tổ có vai rò và ý nghĩa to lớn trong số học và mật mã học. NỔ ngu ên tế củng nhau: cho a, b € A, a, b Íá hai số nguyên tố cùng nhau nếu chúng cà dạy nhất một ước chung là l. Ham Euler Định nghĩa: cho n € N, số lượng các số tự nhién bé hơn n và nguyên tố cùng ._ nhau với n được ký hiệu là @(n).

@ được gọi là hàm Euler. p(5) = 4= (1,2,3,4} Tổng quát, nếu p là số nguyên tố và r € M thì 1 g(p*)=p”*(~ 1Ð = p”(—7) Dinh Ij: nếu n là tích 2 số nguyên tố m=p. Chứng mình: tập tất cả các thặng dư mod n là {0, 1, 2, 3, 4, 5, ., pq-L}chi cd duy nhất những thặng dư không có nguyên tố cùng nhau với n là: p, 2p, 3p, 4p,. Cộng các giá trị này chính là g(n) = pq — ((p — 1) + (q — 1)) =pq— (p+q)—1 Chương 2: Thuật giải RSA Tìm hiểu và mô phỏng thuật giải RSA trên matlab Trang 25 =(p-1)(q-0 = øG).Ước số chung lớn nhất Hai số gọi là cặp số nguyên tố khi mà chúng khôn g có thừa số chung nàokhác 1, hay nói một cách khác, nếu ước số chung lớn nhất của a và n là bằng].

Chúng ta có thể viết như sau: gcd(a,n)=Í Số I5 và 2 là một vập số nguyên tố, nhưng J5 và 27 thì không phải cặp gắnguyên tẾ đo có ước số chung là | và 3, Ế dàng thấy 13 và 500 cũng là một cặp ad npuyen Wh.