Mục lục: Số nguyên tố và các bài toán liên quan

Tìm hiểu về số nguyên tố và ứng dụng của chúng trong chứng minh không tiết lộ thông tin. Khám phá các phương pháp bảo mật thông tin tiên tiến.

• Tác giả: Tạ Thị Hằng
• Người hướng dẫn: Thị Hồng Minh, Phó Chủ Nhiệm Khoa Sau Đại Học Quốc Gia Hà Nội
• Trường học: Đại học Công nghệ Thông tin & Truyền thông Đại học Thái Nguyên
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Số Nguyên Tố và Ứng Dụng Chứng Minh Không Tiết Lộ Thông Tin
• Loại tài liệu: Luận văn
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Tóm tắt

I. Số Nguyên Tố Tổng Quan và Ứng Dụng Mật Mã 55 ký tự

Số nguyên tố, những viên gạch cơ bản của lý thuyết số, đóng vai trò then chốt trong mật mã học hiện đại. Một số tự nhiên lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó. Bài viết này cung cấp một cái nhìn tổng quan về số nguyên tố, các thuật toán kiểm tra tính nguyên tố cơ bản, và tầm quan trọng của chúng trong các giao thức bảo mật dữ liệu. Đặc biệt, chúng ta sẽ đi sâu vào ứng dụng then chốt của số nguyên tố trong chứng minh không tiết lộ thông tin (zero-knowledge proof). Nghiên cứu này dựa trên các kiến thức đã được thu thập từ nhiều nguồn hợp pháp và trích dẫn tham khảo, cung cấp một nền tảng vững chắc cho việc hiểu và ứng dụng số nguyên tố trong an toàn thông tin.

1.1. Định nghĩa và tính chất cơ bản của số nguyên tố

Số tự nhiên lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ chia hết cho 1 và chính nó. Điều này có nghĩa là nó không thể được biểu diễn dưới dạng tích của hai số tự nhiên nhỏ hơn nó. Tính chất này làm cho số nguyên tố trở thành một yếu tố cơ bản trong việc xây dựng các hệ thống mật mã học an toàn. Một tính chất quan trọng khác là định lý cơ bản của số học, nói rằng mọi số tự nhiên lớn hơn 1 đều có thể được phân tích duy nhất thành tích của các số nguyên tố (bỏ qua thứ tự).

1.2. Các bài toán quan trọng liên quan đến số nguyên tố

Có nhiều bài toán mở và chưa được giải quyết liên quan đến số nguyên tố. Một trong số đó là giả thuyết Riemann, một trong những bài toán quan trọng nhất trong toán học. Các bài toán khác bao gồm bài toán về phân tích thừa số nguyên tố, bài toán về khoảng cách giữa các số nguyên tố liên tiếp, và bài toán về việc tìm ra số nguyên tố lớn. Giải quyết những bài toán này có thể mang lại những đột phá lớn trong mật mã học và các lĩnh vực khác.

II. Thách Thức Phân Tích Thừa Số Bảo Mật Mật Mã RSA 58 ký tự

Một trong những ứng dụng quan trọng nhất của số nguyên tố là trong hệ mật mã RSA. Độ an toàn của RSA dựa trên độ khó của việc phân tích thừa số nguyên tố của một số lớn, là tích của hai số nguyên tố lớn. Hiện tại, không có thuật toán nào được biết đến có thể phân tích thừa số nguyên tố một cách hiệu quả cho các số đủ lớn. Tuy nhiên, sự phát triển của các thuật toán lượng tử có thể đe dọa tính an toàn của RSA. Do đó, việc nghiên cứu các hệ mật mã hậu lượng tử đang trở nên ngày càng quan trọng.

2.1. Độ khó của bài toán phân tích thừa số nguyên tố

Bài toán phân tích thừa số nguyên tố là bài toán tìm các số nguyên tố mà tích của chúng bằng một số cho trước. Bài toán này được coi là khó về mặt tính toán, đặc biệt khi số cần phân tích là tích của hai số nguyên tố lớn. Không có thuật toán cổ điển nào được biết đến có thể giải quyết bài toán này một cách hiệu quả. Điều này làm cho bài toán phân tích thừa số nguyên tố trở thành nền tảng của nhiều hệ mật mã, bao gồm cả RSA.

2.2. Ảnh hưởng của lượng tử đến bảo mật mật mã RSA

Sự phát triển của máy tính lượng tử đang đe dọa tính an toàn của các hệ mật mã dựa trên độ khó của bài toán phân tích thừa số nguyên tố, chẳng hạn như RSA. Thuật toán Shor, một thuật toán lượng tử, có thể giải quyết bài toán phân tích thừa số nguyên tố một cách hiệu quả. Nếu máy tính lượng tử đủ lớn được xây dựng, nó có thể phá vỡ các hệ mật mã RSA hiện tại. Do đó, việc phát triển các hệ mật mã hậu lượng tử đang trở nên ngày càng quan trọng.

2.3. Các Thuật Toán Phân Tích Thừa Số Nguyên Tố Tiêu Biểu

Một vài thuật toán phân tích thừa số nguyên tố được biết đến như: thuật toán phân tích thử, thuật toán rho của Pollard, thuật toán bình phương Fermat, và thuật toán sàng số nguyên (Quadratic Sieve). Tuy nhiên, các thuật toán này có độ phức tạp tính toán rất lớn, và không thể ứng dụng hiệu quả cho các số có kích thước đủ lớn. Thuật toán hiệu quả nhất để phân tích thừa số nguyên tố hiện nay là thuật toán sàng trường số tổng quát (General Number Field Sieve), nhưng nó vẫn có độ phức tạp siêu đa thức.

III. Chứng Minh Không Tiết Lộ Ứng Dụng Bảo Mật 53 ký tự

Chứng minh không tiết lộ thông tin (zero-knowledge proof) là một giao thức mật mã cho phép một bên chứng minh cho một bên khác rằng một tuyên bố nào đó là đúng, mà không tiết lộ bất kỳ thông tin nào khác ngoài sự thật đó. Số nguyên tố đóng vai trò quan trọng trong việc xây dựng các giao thức chứng minh không tiết lộ thông tin an toàn và hiệu quả. Ứng dụng của chứng minh không tiết lộ thông tin rất đa dạng, từ bỏ phiếu điện tử đến thương mại điện tử.

3.1. Khái niệm và tính chất của chứng minh không tiết lộ

Chứng minh không tiết lộ thông tin (zero-knowledge proof) là một loại giao thức mật mã cho phép một bên (người chứng minh) chứng minh cho một bên khác (người xác minh) rằng một tuyên bố nào đó là đúng, mà không tiết lộ bất kỳ thông tin nào khác ngoài sự thật đó. Giao thức này phải đảm bảo ba tính chất: tính đầy đủ, tính đúng đắn và tính không tiết lộ thông tin. Điều này có nghĩa là nếu tuyên bố là đúng, người chứng minh có thể thuyết phục người xác minh; nếu tuyên bố là sai, người chứng minh không thể thuyết phục người xác minh; và người xác minh không học được bất kỳ thông tin nào khác từ giao thức, ngoài việc tuyên bố là đúng.

3.2. Ứng dụng của số nguyên tố trong xây dựng giao thức ZKP

Số nguyên tố được sử dụng rộng rãi trong việc xây dựng các giao thức chứng minh không tiết lộ thông tin an toàn và hiệu quả. Ví dụ, trong giao thức Schnorr, số nguyên tố được sử dụng để tạo ra các trường hữu hạn, trong đó các phép tính số học được thực hiện. Độ an toàn của giao thức Schnorr dựa trên độ khó của bài toán logarit rời rạc trong trường hữu hạn này. Các giao thức chứng minh không tiết lộ thông tin khác cũng sử dụng số nguyên tố để đảm bảo tính an toàn và bảo mật.

3.3. Ví dụ Ứng dụng ZKP trong hệ thống bỏ phiếu điện tử

Chứng minh không tiết lộ thông tin được ứng dụng trong bỏ phiếu điện tử để đảm bảo tính riêng tư của cử tri và tính toàn vẹn của cuộc bầu cử. Cử tri có thể chứng minh rằng lá phiếu của họ hợp lệ (ví dụ, họ đủ tuổi để bỏ phiếu) mà không tiết lộ thông tin cá nhân. Các giao thức ZKP đảm bảo rằng không ai có thể biết ai đã bỏ phiếu cho ai, đồng thời đảm bảo rằng tổng số phiếu được tính toán chính xác.

IV. Thuật Toán Kiểm Tra Nguyên Tố Miller Rabin và AKS 59 ký tự

Việc kiểm tra tính nguyên tố của một số lớn là một bài toán quan trọng trong mật mã học. Có nhiều thuật toán kiểm tra tính nguyên tố khác nhau, từ các thuật toán đơn giản như kiểm tra chia đến các thuật toán phức tạp như Miller-Rabin và AKS primality test. Miller-Rabin là một thuật toán xác suất, trong khi AKS primality test là một thuật toán tất định. Việc lựa chọn thuật toán phù hợp phụ thuộc vào yêu cầu về độ chính xác và hiệu suất.

4.1. Thuật toán kiểm tra tính nguyên tố Miller Rabin

Thuật toán Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố của một số. Thuật toán này dựa trên định lý Fermat và một số tính chất khác của số nguyên tố. Thuật toán Miller-Rabin không thể chứng minh một số là nguyên tố, nhưng nó có thể chứng minh một số là hợp số với xác suất cao. Xác suất lỗi của thuật toán Miller-Rabin có thể được giảm xuống bằng cách thực hiện nhiều lần kiểm tra với các giá trị khác nhau.

4.2. Thuật toán kiểm tra tính nguyên tố AKS Primality Test

Thuật toán AKS primality test là thuật toán tất định đầu tiên để kiểm tra tính nguyên tố của một số trong thời gian đa thức. Thuật toán này được phát triển bởi Agrawal, Kayal và Saxena vào năm 2002. Thuật toán AKS primality test có độ phức tạp cao hơn so với thuật toán Miller-Rabin, nhưng nó đảm bảo tính chính xác tuyệt đối. Tuy nhiên, thuật toán Miller-Rabin vẫn được sử dụng rộng rãi hơn trong thực tế do tính hiệu quả của nó.

4.3. So sánh hiệu năng và độ chính xác của các thuật toán

Thuật toán Miller-Rabin nhanh hơn nhiều so với thuật toán AKS primality test trong thực tế, nhưng nó không đảm bảo tính chính xác tuyệt đối. Thuật toán AKS primality test đảm bảo tính chính xác, nhưng nó chậm hơn nhiều. Lựa chọn thuật toán phụ thuộc vào ứng dụng cụ thể. Nếu cần độ chính xác cao, AKS primality test là lựa chọn tốt hơn. Nếu tốc độ quan trọng hơn, Miller-Rabin là lựa chọn phù hợp.

V. Ứng Dụng Thực Tiễn An Toàn Thông Tin và Bảo Mật 57 ký tự

Ứng dụng của số nguyên tố không chỉ giới hạn trong mật mã học. Chúng còn được sử dụng trong nhiều lĩnh vực khác, bao gồm an toàn thông tin, bảo mật dữ liệu, và chữ ký số. Việc hiểu rõ về số nguyên tố và các ứng dụng của chúng là rất quan trọng để xây dựng các hệ thống bảo mật an toàn và hiệu quả.

5.1. Số nguyên tố trong chữ ký số và xác thực thông tin

Chữ ký số sử dụng số nguyên tố để đảm bảo tính xác thực và tính toàn vẹn của thông tin. Người gửi sử dụng khóa bí mật (liên quan đến số nguyên tố) để tạo ra chữ ký số cho thông điệp. Người nhận sử dụng khóa công khai tương ứng để xác minh chữ ký số, đảm bảo rằng thông điệp không bị sửa đổi và được gửi bởi người gửi hợp lệ.

5.2. Bảo mật dữ liệu và mã hóa thông tin sử dụng số nguyên tố

Số nguyên tố là nền tảng của nhiều thuật toán mã hóa, giúp bảo vệ dữ liệu khỏi truy cập trái phép. Các thuật toán như RSA, Diffie-Hellman, và ElGamal sử dụng số nguyên tố để tạo ra các hệ mật mã mạnh mẽ. Tính bảo mật của các hệ mật mã này dựa trên độ khó của các bài toán số học liên quan đến số nguyên tố.

VI. Tương Lai Nghiên Cứu Số Nguyên Tố và Mật Mã Hậu Lượng Tử 58 ký tự

Nghiên cứu về số nguyên tố vẫn tiếp tục là một lĩnh vực sôi động, với nhiều hướng đi mới và tiềm năng. Một trong những hướng đi quan trọng nhất là nghiên cứu về mật mã hậu lượng tử, nhằm phát triển các hệ mật mã an toàn trước sự tấn công của máy tính lượng tử. Số nguyên tố có thể đóng vai trò quan trọng trong việc xây dựng các hệ mật mã hậu lượng tử này.

6.1. Các hướng nghiên cứu mới về số nguyên tố

Các nhà toán học và nhà mật mã học đang tiếp tục nghiên cứu các tính chất và ứng dụng mới của số nguyên tố. Một số hướng nghiên cứu bao gồm việc tìm kiếm các thuật toán kiểm tra tính nguyên tố nhanh hơn, phát triển các hệ mật mã dựa trên các bài toán số học khó hơn, và khám phá các ứng dụng mới của số nguyên tố trong các lĩnh vực khác.

6.2. Vai trò của số nguyên tố trong mật mã hậu lượng tử

Mật mã hậu lượng tử là một lĩnh vực nghiên cứu mới nổi, nhằm phát triển các hệ mật mã an toàn trước sự tấn công của máy tính lượng tử. Số nguyên tố có thể đóng vai trò quan trọng trong việc xây dựng các hệ mật mã hậu lượng tử này. Các nhà nghiên cứu đang khám phá các cách sử dụng số nguyên tố trong các hệ mật mã dựa trên lưới, mã sửa sai, và các cấu trúc toán học khác.

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

chương 1 đã tổng quan về số nguyên tố và phân tích thừa số nguyên tổ. Đây là kiến thức cơ sở chuân bị cho những nghiên cứu tiếp theo của "bản luận văn này. Phân đầu nói về định nghĩa và các tính chất của số nguyên tổ. Tiếp theo là những vấn đề về sinh số nguyên tổ và phân tích số nguyên tố.

đồ ra thừa số. Nội đung chính chương giúp hiểu được số nguyên tổ và mô hình hóa lập kế hoạch giải quyết các bài toán về số nguyên tố. Đây là cơ sở quan trọng để tiền. hành xây đựng các thuật toán kiểm tra số nguyên tố và sinh số nguyên tổ lớn.

đâm bảo hiệu quả, sẽ trình bay ở các chương tiếp theo. Chương 2: Số nguyên tố lớn và ứng dung trong chứng minh không tiết lộ thông tin. Thuật toán kiểm tra số nguyên tố Bài toán 'Cho một số nguyên n, kiểm tra xem đó có phải là số nguyên tổ hay không? Giải thuật Ì ~ Nếu n là 1, thì n không là số nguyên tố - Xết cả số nguyên ï nhỏ hơn (n - 1), kiểm tra xem ør cô chia hết x không, niếu tất cả không thì ø là số nguyên tổ. "Thuật toán có thê viết đạng giả mã như sau: Giải thuật 1: Kiểm tra nguyên tổ Tnput: n (lớn hơn 2) Output: 1 néu n là số nguyên tổ, 0 nếu ngược lại Begin for (i=2:; ica: i++) if (n%i=0) return 0: retum 1; End.

Chang ta có thể nhận thấy rằng giải thuật 1 kiểm tra số nguyên tổ có số lần. lặp tuỷ thuộc vào giá trị của ø, nếu ø quá lớn, giải thuật sẽ tính toán với thời gian lớn. Có thé làm giảm bớt thời gian tính toán trong thuật toán 1 bằng cách thêm và điều chỉnh một số lệnh như sau: - Thém lệnh kiểm tra trường hợp m là số chẵn (z%2==0) kết thúc thuật toán trả về giá trị ~_ Điều chỉnh vòng lặp for với ¿ chạy từ 2 tdi Vm ma vin nhận được kết quả đúng. Vi nếu một số n không là nguyên tổ có ước a thi sé có ước z4, một trong hai giá trị ø hoặc níz sẽ cô nhỏ hơn .z, vậy chúng ta chỉ cần thực hiện vòng lặp đến vn đề tìm ra ước của ø nếu có.

Giải thuật 2 có thê được viết lại như sau: Giải thuật 2: tra số nguyên tổ Tnput: n (lớn hơn 2) Output: 1 néu n là số nguyên tổ, 0 nếu ngược lại icsqrt(n); i++) 0) return 0: End. Độ phức tạp của giải thuật 2 trong trường hợp xấu nhất là O(. Tuy có giảm được thời gian tính toán so với giải thuật 1, nhưng với giá trị m rat lớn thì đây cũng chưa phải là giải thuật có thé đáp ứng được yêu cầu về mặt thời gian tính toán. Chúng ta sẽ xem xét một số kĩ thuật phân tích và thiết kế thuật toán kiểm tra số nguyên tổ lớn một cách hiệu quả trong những phần tiếp theo của chương này Kiểm tra số nguyên tố bằng thuật toán Konigi -Pomerans Èu mex' và một số được phân tích ra thừa số nguyên tổ n-1, thì để kiểm.

tran là hợp số hay là số nguyên tổ ta đánh giá độ phức tạp theo đa thức. Tnputn ‘Output: Sé ri cần kiêm tra là hợp số hay số nguyên tổ. Thuật toán Konigin-Pomerans Đặt F(1):=1. |eg`n|+1 Sau đô đối với từng số a=2.

leg` z|+1 chúng ta thực hiện cho đến khi chúng ta không chứng minh được n là hợp số hay nguyên tổ. Nếu a là hợp số, thì F(@=F(a—1va nhây lên bước 6. Nếu a là số. nguyên tố, và 7< lềnodz), thi F(@)=F(a-D và nhảy đến bước 6.

Ngược lại chúng ta kiểm tra điều kiện sau, xem có thỏa mãn không: 4”? =I(moän) Nếu như khôi , thi n là hợp số. Khi phân tích n-1 ra thửa số ng ;ên tổ, ta tìm bậc của a (mod n), nghĩa Ja số tự nhiên nhỏ nhất E(a), thỏa mãn a° ‘modn) 3. Kiểm tra điều kiện sau c6 théa man hay khéng: UCLN( [](@"** 1), g 1a 86 nguyên tố. 'Nếu như điều kiện trên không hoàn thành thì n là hợp số.E(a)), BCNN-bội số chung nhỏ nhất./», thì n là số nguyên tổ.

6A như z<[leg°ni, thì quay về tầng 2 với a là gid trị tiếp theo. N nhu a=log? n|+1, thi n 1a hợp số. 'Đánh giá độ phức tạp cũa thuật toán Konigin- Pomerans Nếu giả sử meA„s>1, n là số lễ, a~1= [J4 .Lúc này việc kiểm tra tính nguyên tổ của n có thể có chi phí là 4 eben | Thật vậy với neA,m>1, n là số lễ, n-1=F,R, 6 day UCLNŒ,,&)=1, và biết được sự phân chia 7, ra thừa số nguyên tố. Nếu Z;>»'“”, với elà số đương không đổi, thì nguyên tố của n có thể chỉ phí là Ø(0egz)“°)( c(e) là số nguyên đương không đổi, phụ thuộc vào e.

“Chúng ta chứng minh tinh đúng đắn của thuật toán và nhận đánh giá về độ phúc tạp của thuật toán. Bảng liệt kê số nguyên tố thực hiện trên tầng 1 nhờ sự giúp đỡ của sàng Eratosfen với độ phức tạp Ø(eg“z). Giá trị hiện tại của F(a) là ước số của n-1, cho nên bước 1 của tầng mất (kg) lệnh Bước 2 của tầng tốn Ø(og' z) lệnh nhờ sự giúp đỡ của thuật toán hỗ trợ. sau Input: aneN.n- được sự phân tích ra thửa số nguyên tổ của số z-1 ‘Output :l bac cia a (mod ) trong Z, ‘Thuat toán tìm bậc của phần tử j+LM=Mips.z,, kiểm tra xem điều kiên sau có.

thôa mãn không A=lmodn) "Nếu như đúng thì nhây sang bước 4. Ngược lại M=Mp,, 4 ‘Va chuyén dén gia trị tiếp theo của I trong chu trình. 4 Nếu như j<N, thì quay về bước 2, ngược lại thì đưa ra M. Tinh đúng đắn của thuật toán tìm bậc của phần tử thì quá rõ ràng.

Đề nhận được đánh giávề độ phức tạp của thuật toán này ta chú ý rằng. Cho nên bên trong và bên ngoài chu trình thực hiện Ø{egz) bước, và trong từng bước thực hién O(ogn)lénh. Téng độ phức tạp là Ø(eg`z) lệnh.Kiém tra tính nguyên tố bằng thuật toán Miller Cho /:X->#- hàm số trên tập số tự nhiên, với fín)<n. Tương tự 'Konhiagin-Pomerans chúng ta xem thuật toán Miller Input :Số tự nhiên lẽn, n>1 ‘Output : Flase néun là.

guyén, True nếu n là hop Thuật toán Miller 1 Kiểm tra điều kiện sau cô thỏa mãn hay khôngz=zr, với smeN,r>2.N như thôa mãn, thi n 1a hợp số, và thuật toán đừng. Thực hiện các bước nhỗ ()-(ii) đối với tất cã a< /0ò () Kiểm tra điều kiện địt (ii) - Kiểm tra điều kiện a”' #(modz) (iii) Kiểm tra xem có đúng hay không, với một số giá trị của k, 1X#<y;0—D, 1<UCDNG ~lạmsin)s)<n iêu như một trong ba điều kiện ()-(ii) thöa mãn thủ z là hợp số, và thuật toán đừng 3. Nếu như chúng ta đi đến được bước này thì ø là số nguyên tổ. Kiểm tra tính nguyên tế của số bằng phép kiêm tra xác suất.

Các phép kiểm tra tính nguyên tố hay đùng nhất là các thuật toán ngất nhiên. Giả sử có một mệnh đề Q(ø,a) nào đó đúng với mọi số tguyên tổ p và một số tự nhiên a <=. "Nếu n là một số tự nhiên lẽ và mệnh đề Q(x.) đúng với một a<= ø được lấy ngẫu nhiên, khi đồ a có khả năng là một guyén tổ. Ta đưa ra một thuật toán, kết luận rằng z là số nguyêntố.

Nó là một thuật toán ngẫu. 1 nhiên hay thuật toán xác suất. Trong các thuật toán loại này, đùng để kiểm tra. ngẫu nhiên không bao giờ kết luận một số nguyên tổ là hợp số nhưng có thể kết luận một hợp số là số nguyên tổ.

Xác suất sai của phép kiểm tra cô thể giảm. x i nha viée chon mét day déc lap cdc s6 a néu voi méi sé a xac suZ thuật toán kết luận một hợp là số nguyên tổ là nhỏ hơn một nửa thì sau k lần. thử độc lập, xác suất sai là nhỗ hơn 2ˆ* độ tin cậy của thuật toán sẽ tăng lên theo k trúc cơ bản của một phép kiếm tra ngẫu nhiên là Input: 7 'Output: Số ø cần kiểm tra là hợp số hay là số nguyên. Thuật toán kiểm tra xác suất 1: Chọn một số ngẫu nhiên ø 2: Kiểm tra một hệ thức nào đó giữa số a và số n đã cho.

Nếu hệ thức sai thì chắc chắn n là một hợp số (số z là "bằng chứng" chứng. tö n là hợp số) và đừng thuật toán. 3: Lặp lại bước 1 cho đến khi đạt được số lần đã định hoặc gặp bước 2. Sau một loạt lần kiém tra, nếu không tìm được bằng chứng chứng tổ z là hợp số thì ta kết luận z là số nguyên tổ.

Các phép kiểm tra tính nguyên tổ ngầu nhiên là: Phép kiểm tra tính nguyên tố của Fennat (kiểm tra Fermat). Day là phép thử heuristic, tuy nhiên ít người sử dụng phép thử này. Được sử dụng nhiều hơn là Kiểm tra Miller-RRabin và Kiểm tra Solovay-Strassen.Với mỗi hợp số n, ít nhất 3⁄4 (với kiém tra Miller-Rabin) hoặc 1⁄2 (Với kiểm tra Solovay-Strassen) các số a là bằng chứng chứng tô n là hợp số). Kiểm tra trên cơ sở định luật nhö của Fermat Phương pháp này dựa trên định luật nhỏ của Fermat: Nếu như » là số nguyên tổ thì bất kỳ số z< Z thõa mãn phương trình sau Nếu như UCLN(@.n)=1, thi Cho nén 4@ kiém tra tinh nguyén té cia n, ching ta chon mét s6 bat ky ae Z và kiểm tra xem có thỏa mãn định lý của Fermat hay không? Nếu như định lý Fermat không thỏa với một giá trị a nào đó thì n là hợp số.

Nếu thỏa mãn, thì chúng ta cũng không thê kết luận rằng n là số nguyên tổ, bởi nó chỉ đúng trong. điều kiện cần. Vì vẫn tôn tại n là hợp số, thì đối với bắt kỳ số aeZ, thi ta vẫncó được đẳng thức a" = a(modn), số này còn được gọi là số giã nguyên tổ. ‘Vi du, ching ta xem số 561=3.

Chúng ta chứng số này là số giã nguy tổ. Nếu 3la, thì a như3 không là ước cia a, thi a’ = i(mod3), ti day ta 06 a =1(mod3), hay a = a{mod3). Tuong tu kiém tra déi v6i hai s6 11 va 17 Nhu vay việc kiểm số nguyên tổ theo Fermat là có khuyết điểm. 'Ta có thể nêu ra các bước kiểm tra tính nguyên tố như sau: Input : Chọn ngẫu nhiên a tập {12.:—1} ‘Output: Sé r¡ cần kiêm tra là hợp số hay là số nguyên.

Thuật toán kiểm tra của Fermat 1: Kiểm tra điều kiện UCLNG/ "Nếu như điều kiện trên không thöa mãn thì n là hợp số. Kiểm tra đẳng thức (2) "Nếu như đẳng thức (2) không thöa mãn thì trả lời n là hợp số. "Nếu như đẳng thức đúng thì trả lời là chưa biết, nhưng có thể kiểm tra lại một số lần với các a khác nhau.