Luận văn Thạc sĩ Toán học: Số giả nguyên tố và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:38

Thêm vào BST

Báo xấu

34
lượt xem 6
download

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

Luận văn "Số giả nguyên tố và ứng dụng" được nghiên cứu nhằm mục đích tìm hiểu sơ lược về cơ sở Toán học của Lý thuyết mật mã và tìm hiểu một số loại số giả nguyên tố được nhiều người quan tâm. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Số giả nguyên tố và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ MINH HUỆ SỐ GIẢ NGUYÊN TỐ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THỊ MINH HUỆ SỐ GIẢ NGUYÊN TỐ VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 60 46 01 13 NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH. HÀ HUY KHOÁI THÁI NGUYÊN - 2017
3 Mục lục Danh sách kí hiệu 5 MỞ ĐẦU 6 Chương 1. Số giả nguyên tố trong lý thuyết mật mã khóa công khai 8 1.1 Cơ sở toán học của lý thuyết mật mã khoá công khai . . . . . 8 1.1.1 Hệ mã khoá RSA . . . . . . . . . . . . . . . . . . . 9 1.1.2 Vấn đề lấy căn bậc hai modulo n . . . . . . . . . . . 10 1.1.3 Độ khó của việc tìm số không chính phương modulo p 11 1.2 Vấn đề sinh số nguyên tố lớn . . . . . . . . . . . . . . . . . 11 Chương 2. Một số loại số giả nguyên tố 14 2.1 Số giả nguyên tố . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Số Carmichael . . . . . . . . . . . . . . . . . . . . 16 2.2 Kiểm tra Miller và số giả nguyên tố mạnh . . . . . . . . . . 22 2.3 Số giả nguyên tố Euler . . . . . . . . . . . . . . . . . . . . 25 2.4 Số giả nguyên tố Catalan . . . . . . . . . . . . . . . . . . . 33 KẾT LUẬN VÀ KIẾN NGHỊ 37 TÀI LIỆU THAM KHẢO 38
4 Lời cảm ơn Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái Nguyên và hoàn thành với sự hướng dẫn của GS.TSKH. Hà Huy Khoái (Trường Đại học Thăng Long, Hà Nội). Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới người hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả xin trân trọng cảm ơn Ban Giám hiệu Trường Đại học Khoa học - Đại học Thái Nguyên, Ban Chủ nhiệm Khoa Toán–Tin, cùng các giảng viên đã tham gia giảng dạy, đã tạo mọi điều kiện tốt nhất để tác giả học tập và nghiên cứu. Tác giả muốn gửi những lời cảm ơn tốt đẹp nhất tới tập thể lớp Cao học Toán khóa 9B (2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong suốt quá trình học tập. Nhân dịp này, tác giả cũng xin chân thành cảm ơn Sở Giáo dục và Đào tạo Hải Phòng, Ban Giám hiệu và các đồng nghiệp ở Trường THPT Quang Trung, Huyện Thủy Nguyên, Thành phố Hải Phòng đã tạo điều kiện cho tác giả hoàn thành tốt nhiệm vụ học tập và công tác của mình. Cuối cùng, tác giả muốn dành những lời cảm ơn đặc biệt nhất đến bố mẹ và đại gia đình đã luôn động viên và chia sẻ những khó khăn để tác giả hoàn thành tốt luận văn này.
5 Danh sách kí hiệu   b   ký hiệu Jacobi n π(n) số các số nguyên tố nhỏ hơn hoặc bằng n mod p modulo p a|b b là bội của a a ≡ b (mod p) a đồng dư với b theo modulo p gcd(a, b) ước chung lớn nhất của hai số nguyên a và b m ∑ ai ký hiệu tổng a1 + a2 + · · · + am i=1 m ∏ bi ký hiệu tích b1 b2 · · · bm i=1
6 Mở đầu Có thể nói, Lý thuyết số là một ngành khoa học sớm nhất của nhân loại. Trước những năm 70 của thế kỷ XX, Lý thuyết số được coi là một ngành thuần túy lý thuyết, và thậm chí người ta còn ca ngợi vẻ đẹp của nó vì nó xa rời thực tiễn! Tuy nhiên, như Issac Newton từng nói : “Không có gì gần với thực tiễn hơn là một lý thuyết đẹp”, Lý thuyết số lại trở thành một ngành gần thực tiễn nhất, ứng dụng nhất, vì những ảnh hưởng lớn lao và bất ngờ của nó đến nhiều ngành, chẳng hạn như Lý thuyết mật mã. Trong lĩnh vực Lý thuyết mật mã, mật mã hóa khóa công khai là một dạng mật mã cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật). Các kiến thức toán học được sử dụng ở đây là các mối quan hệ, các tính chất của số nguyên tố (prime), số giả nguyên tố (pseudoprime) và nhiều khía cạnh khác của Lý thuyết số. Trong Lý thuyết số, số giả nguyên tố là một hợp số nguyên dương thỏa mãn nhiều quan hệ như các số nguyên tố. Nếu ta tìm được một quan hệ nào đó (ví dụ như đồng dư thức trong định lý Fermat bé) sao cho số các hợp số thoả mãn quan hệ đó là "rất ít" so với các số nguyên tố, thì những số giả nguyên tố xét theo quan hệ đó có thể sử dụng để tìm ra những số nguyên tố xác suất, tức là những số mà về mặt lý thuyết, có thể là hợp số với một xác suất rất nhỏ.
7 Luận văn này có một mục đích, một mặt là tìm hiểu sơ lược về cơ sở Toán học của Lý thuyết mật mã, mặt khác, là tìm hiểu một số loại số giả nguyên tố được nhiều người quan tâm. Ngoài các phần Mở đầu, Kết luận, Tài liệu tham khảo, nội dung của luận văn được trình bày trong hai chương: • Chương 1. Số giả nguyên tố trong lý thuyết mật mã khóa công khai. Trong chương này chúng tôi trình bày các kiến thức cơ sở về các số giả nguyên tố trong lý thuyết mật mã khóa công khai bao gồm cơ sở toán học của lý thuyết mật mã và độ phức tạp của việc sinh số nguyên tố lớn. • Chương 2. Một số loại số giả nguyên tố. Chương này dành để trình bày về một số loại số giả nguyên tố quan trọng bao gồm số giả nguyên tố Fermat, số giả nguyên tố mạnh, số giả nguyên tố Euler, số giả nguyên tố Catalan. Tác giả hy vọng rằng, bản luận văn này có thể làm tài liệu tham khảo hữu ích cho những ai quan tâm đến Lý thuyết số và các vấn đề ứng dụng thực tiễn, ví dụ như mật mã, và nó cũng có thể được làm tài liệu bồi dưỡng học sinh khá giỏi, tài liệu tham khảo về Lý thuyết số. Thái Nguyên, ngày 20 tháng 5 năm 2017 Tác giả Nguyễn Thị Minh Huệ
8 Chương 1 Số giả nguyên tố trong lý thuyết mật mã khóa công khai 1.1 Cơ sở toán học của lý thuyết mật mã khoá công khai Trong mục này, chúng ta sẽ thảo luận về việc áp dụng phân tích nhân tử và kiểm tra tính nguyên tố trong mật mã. Trong mật mã chúng ta tìm cách truyền một tin nhắn bí mật m, chẳng hạn từ Alice cho Bob theo cách mà Oscar là người chặn tín hiệu không thể đọc được tin. Ý tưởng là phải đưa ra một khoá mã hoá Φ, là một hàm toán học biến m thành r := Φ(m) để gửi. Số r là những ký tự mà dường như vô nghĩa để cho Oscar không thể thông dịch và Bob có thể giải mã bằng cách tính Ψ(r), trong đó Ψ = Φ−1 . Cho tới gần đây (trước 1977), hiểu biết về khoá mã hoá Φ có thể cho phép Oscar xác định khoá giải mã Ψ, và do đó việc giữ bí mật khoá mã hoá Φ là một việc vô cùng quan trọng và thường là một nhiệm vụ khó khăn. Nếu Oscar được cho một khoá mã hoá thì anh ta dễ dàng xác định khoá giải mã bằng cách đảo ngược những gì đã làm để mã hoá. Tuy nhiên, năm 1976, Diffie và Hellman , bằng cách đưa ra hệ mã mũ, dường như đã tạo ra khoá công khai Φ, theo đó Oscar có thể nhìn thấy nhưng không thể xác
9 định Ψ = Φ−1 . Nếu việc này khả thi, Alice có thể quên đi khó khăn của việc giữ khoá bí mật. Trong hệ thống mã hoá khoá công khai ngày nay, các khó khăn trong việc xác định Ψ từ Φ có xu hướng dựa trên một bài toán khó chưa giải được, thường là các bài toán mà ngay cả những người giỏi nhất như Gauss và các nhà toán học sau này đều không giải được, ví dụ như bài toán phân tích nhân tử. Bây giờ chúng ta nghiên cứu các hệ thống mật mã khoá công khai nổi tiếng nhất. 1.1.1 Hệ mã khoá RSA Năm 1977, Ron Rivest, Adi Shamir và Len Adleman đề xuất một hệ thống mật mã khoá công khai, là trung tâm của nhiều hệ thống bảo mật máy tính ngày nay. Ý tưởng là Bob lấy hai số nguyên tố lớn p < q, tính tích của chúng n = pq, và xác định hai số nguyên d và e thoả mãn de ≡ 1( (mod (p − 1)(q − 1)) (việc này dễ dàng). Khoá công khai, mà Alice sử dụng, sẽ bao gồm số n và khoá mã hoá e, trong khi đó Bob giữ khoá giải mã d bí mật (tức là giữ p và q). Ta giả sử tin nhắn m là một số nguyên thuộc [1, n − 1]. Để mã hoá m, Alice tính r := Φ(m) ≡ me (mod n), với Φ(m) ∈ [1, n − 1], có thể dễ dàng tính được. Để giải mã Bob tính Ψ(r) := rd (mod n), với Ψ(r) ∈ [1, n − 1]. Sử dụng Định lý Euler (cho tích của p và q) ta có thể dễ dàng kiểm tra mde ≡ m (mod n), và do đó Ψ = Φ−1 . Oscar biết n, và nếu ông có thể phân tích nhân tử n, thì ông cũng có thể dễ dàng xác định Ψ, do đó độ bảo mật của hệ thống RSA phụ thuộc vào độ khó của việc phân tích nhân tử. Như đã nói ở trên, việc này vượt xa những gì khả thi ngày nay nếu chúng ta lấy p và q là các số nguyên tố có chứa
10 nhiều hơn 200 chữ số. Ta sẽ thấy rằng, việc tìm số nguyên tố (xác suất) lớn như vậy rất dễ dàng bằng cách sử dụng các số giả nguyên tố, vấn đề sẽ thảo luận trong luận văn. 1.1.2 Vấn đề lấy căn bậc hai modulo n Từ Định lý Euler ta biết rằng, nếu ta có thể tìm được căn bậc hai b của 1 mod n mà khác ±1, thì điều này chứng tỏ rằng n là hợp số. Thực vậy, từ b suy ra phép phân tích nhân tử của số lẻ n với: gcd(b − 1, n) gcd(b + 1, n) = gcd(b2 − 1, n) = n (1.1) (do b2 ≡ 1 (mod n)) trong đó gcd(b − 1, n) và gcd(b + 1, n) nhỏ hơn n (vì b 6≡ 1 hay −1 (mod n)), kéo theo 1 < gcd(b − 1, n), gcd(b + 1, n) < n và do đó (1.1) là phép phân tích nhân tử không tầm thường của n. Một cách tổng quát hơn ta giả sử rằng cho trước hợp số lẻ n với ít nhất hai nhân tử nguyên tố phân biệt, Oscar có một hàm fn sao cho nếu a là một bình phương (mod n), thì fn (a)2 ≡ a (mod n). Sử dụng fn , Oscar có thể dễ dàng phân tích nhân tử n (với thời gian đa thức ngẫu nhiên), vì nếu ông lấy các số nguyên b trong khoảng [1, n − 1] một cách ngẫu nhiên thì gcd( fn (b2 ) − b, n) là một nhân tử không tầm thường của n với điều kiện b 6≡ fn (b2 ) hay − fn (b2 ) (mod n); vì có ít nhất bốn căn bậc hai của b2 (mod n), xác suất đây là một phép phân tích nhân tử của n là lớn hơn hoặc bằng 1/2. Sử dụng ý tưởng này, Rabin xây dựng một hệ thống mật mã khoá công khai mà về bản chất việc phá khoá khó như tìm phân tích nhân tử của n.
11 1.1.3 Độ khó của việc tìm số không chính phương modulo p Cho một số nguyên tố lẻ p ta dễ tìm được bình phương modulo p: lấy 1 hoặc 4 hoặc 9, hoặc thậm chí bất kỳ a2 (mod p). Có đúng (p − 1)/2 giá trị trong số các giá trị modulo p khác không là bình phương modulo p, và do đó có đúng (p − 1)/2 giá trị không là bình phương modulo p. Ta có thể đoán rằng dễ dàng tìm được chúng, nhưng chúng ta không biết một cách chắc chắn làm thế nào để nhanh chóng tìm một giá trị như vậy cho mỗi số nguyên tố p (mặc dù chúng ta thực sự biết một cách nhanh chóng để kiểm tra một số không chính phương hay không nếu chúng ta có nó). Ý tưởng rõ ràng nhất là thử lần lượt a = 2, 3, 4, · · · cho tới khi tìm thấy một số không chính phương. Người ta tin rằng có một số không chính phương nhỏ hơn hoặc bằng 2(log p)2 , nhưng ta không thể chứng minh được điều này (mặc dù ta có thể suy ra từ Giả thuyết Riemann suy rộng). 1.2 Vấn đề sinh số nguyên tố lớn Trong mục này, ta sẽ thảo luận về độ phức tạp của việc sinh số nguyên tố lớn. Ta sẽ dùng tài liệu Hà Huy Khoái [3] làm tài liệu tham khảo chính. Ta sẽ nghiên cứu việc sinh số nguyên tố thỏa mãn: 1. Số sinh ra có độ dài 3072 bit, 2. Số được sinh ra là ngẫu nhiên, và 3. Thời gian sinh mỗi số phải nhanh, thời gian trung bình bé hơn 5 giây/1 số đối với các máy tính thông thường.
12 Nhắc lại, một số nguyên dương p > 1 được gọi là một số nguyên tố nếu p không chia hết cho số nguyên dương nào ngoài 1 và p. Ngược lại, số p được gọi là hợp số. Ta ký hiệu π(n) là số các số nguyên tố nhỏ hơn hoặc bằng n, và gọi nó là hàm phân phối của các số nguyên tố. Ví dụ 1.2.1. π(10) = 4 vì có bốn số nguyên tố nhỏ hơn 10 là 2, 3, 5, 7. Ta có định lý sau đây về ước lượng xấp xỉ hàm số học π(·): Định lí 1.2.2. Ta có π(n) lim = 1. n→∞ n/ ln n Nói cách khác, giá trị π(n) xấp xỉ bằng n/ ln n khi n vô cùng lớn. Ví dụ 1.2.3. Với n = 109 , ta có π(n) = 50847534 và n/ ln n = 48254942. Sai số ở đây là 6%. Vậy ta lấy ngẫu nhiên một số nguyên dương k bit, xác suất để số này là số nguyên tố bằng 1/ ln 2k . Vậy về trung bình, ta cần ln 2k lần thử để lấy được một số nguyên tố k bit. Ví dụ 1.2.4. Nếu k = 3072 thì trung bình lấy ngẫu nhiên ln 23072 ≈ 2130 số, ta sẽ có được một số nguyên tố k bit. Từ phân tích ở trên, về trung bình thuật toán ngẫu nhiên dưới đây sẽ dừng sau 2130 bước lặp. Thuật toán sinh số nguyên tố.
13 Bước 1. Chọn ngẫu nhiên một số nhị phân p độ dài 3072 bit. Bước 2. Đặt cả hai bit cao nhất và bit thấp nhất của p là 1. Bước 3. Kiểm tra xem p có là số nguyên tố hay không. Bước 4. Nếu có thì in ra số nguyên tố p. Còn không thì quay lại Bước 1. Trong Bước 2 của thuật toán. • ta thêm bit thấp nhất của p là 1 để đảm bảo rằng p là số lẻ; • và ta thêm bit cao nhất của p là 1 để đảm bảo rằng số p sinh ra thỏa mãn 23072−1 < p ≤ 23072 − 1, điều này cần thiết vì để đảm bảo an toàn cho thuật toán RSA thì các số nguyên tố sinh ra phải đủ lớn.
14 Chương 2 Một số loại số giả nguyên tố 2.1 Số giả nguyên tố 2.1.1 Khái niệm Bây giờ ta sẽ trình bày khái niệm về các số giả nguyên tố. Theo định lý Fermat, nếu n là số nguyên tố và b là số nguyên tuỳ ý, thì bn ≡ b (mod n). Do đó nếu tồn tại số b sao cho bn 6≡ b (mod n) thì n phải là hợp số. Trong nhiều ứng dụng, chúng ta lại cần đến các thuật toán để chỉ ra một số n là số nguyên tố. Trong trường hợp này, ta không thể dùng Định lý Fermat nhỏ, vì định lý ngược của nó không đúng. Tuy nhiên, nếu một số nguyên thoả mãn các giả thiết của Định lý Fermat nhỏ thì “có nhiều khả năng” nó là một số nguyên tố ! Ta có định nghĩa sau đây. Định nghĩa 2.1.1. Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương và bn ≡ b (mod n) thì n được gọi là số giả nguyên tố cơ sở b. Trong trường hợp (n, b) = 1, ta thường dùng định nghĩa tương đương, là bn−1 ≡ 1 (mod n). Trường hợp này, n được gọi là một số giả nguyên tố Fermat.
15 Ví dụ 2.1.2. Số nguyên 561 = 3 · 11 · 17 là số giả nguyên tố cơ sở 2. Thật vậy, áp dụng Định lý Fermat nhỏ, ta có 2560 = (22 )280 ≡ 1 (mod 3), 2560 = (210 )56 ≡ 1 (mod 11), 2560 = (216 )35 ≡ 1 (mod 17). Từ đó suy ra 2560 ≡ 1 (mod 561). Nói chung các số giả nguyên tố ít hơn nhiều so với các số nguyên tố. Chẳng hạn, có tất cả 455052512 số nguyên tố bé hơn 1010 nhưng chỉ có 14884 số giả nguyên tố cơ sở trong khoảng đó. Sự kiện này giải thích cách nói ở trên: Các số thoả mãn Định lý Fermat nhỏ có nhiều khả năng là số nguyên tố. Tuy nhiên đối với mọi cơ sở tuỳ ý, số các số giả nguyên tố là vô hạn. Chẳng hạn, ta chứng minh điều đó đối với cơ sở 2. Định lí 2.1.3. Có vô số số giả nguyên tố cơ sở 2. Chứng minh. Giả sử n là một số giả nguyên tố cơ sở 2, ta sẽ chứng tỏ rằng m = 2n − 1 cũng là số giả nguyên tố cơ sở 2. Theo giả thiết, n là hợp số, chẳng hạn n = dt với 1 < d, t < n, và 2n−1 ≡ 1 (mod n). Dễ thấy rằng m là hợp số, vì (2d − 1) | (2n − 1). Do n là giả nguyên tố, 2n ≡ 2 (mod n) n −2 tức là tồn tại k sao cho 2n − 2 = kn. Ta có 2m−1 = 22 = 2kn , và do đó, m = (2n − 1) | (2nk − 1) = 2m−1 − 1, tức là 2m−1 ≡ 1 (mod m). Vậy số m là giả nguyên tố cơ sở 2. Như vậy, để kiểm tra một số có phải là số nguyên tố hay không, trước tiên ta xem nó có là giả nguyên tố cơ sở 2 hay không, sau đó có thể tiếp tục kiểm tra đối với các cơ sở khác. Tuy nhiên, tồn tại các số giả nguyên tố với mọi cơ sở, đó là các số Carmichael. Ta sẽ xem xét nó ngay ở mục sau đây.
16 2.1.2 Số Carmichael Định nghĩa 2.1.4. Hợp số nguyên n thoả mãn bn−1 ≡ 1 (mod n) với mọi số nguyên dương b sao cho (n, b) = 1 được gọi là số Carmichael. Ví dụ 2.1.5. Số nguyên 561 = 3 · 11 · 17 là một số Carmichael. Thật vậy, nếu như (b, 561) = 1 thì suy ra (b, 3) = (b, 11) = (b, 17) = 1. Theo Định lý Fermat nhỏ, ta có b2 ≡ 1 (mod 3), b10 ≡ 1 (mod 11), b16 ≡ 1 (mod 17). Do đó, viết 560 = 2 · 280 = 10 · 56 = 16 · 35 ta được 280 b = b2 560 ≡ 1 (mod 3), 56 b = b10 560 ≡ 1 (mod 11), 35 b = b16 560 ≡ 1 (mod 17). Từ đó suy ra b560 ≡ 1 (mod 561). Giả thuyết sau đây đã được chứng minh trong W. R. Alford, A. Granville & C. Pomerance [4] : tồn tại vô hạn số Carmichael. Chính xác hơn, như trong [4, Abstract], các tác giả nói rằng sẽ chứng minh có khoảng x2/7 số Carmichael nhỏ hơn x, với x đủ lớn. Ta điểm qua một số cột mốc chính trong lịch sử phát triển của các nghiên cứu về số giả nguyên tố Fermat và số Carmicheal. Vào ngày 18/10/1640, Fermat viết trong một bức thư gửi đến Frenicle, rằng p chia hết a p − a với mọi số nguyên a, với p là một số nguyên tố. Câu hỏi tự nhiên nảy sinh là : Liệu các số nguyên tố có là tất cả những số nguyên lớn hơn 1 thỏa mãn tiêu chuẩn này?
17 Tuy nhiên, năm 1910, Carmichael đã chỉ ra 561 (bằng 3 × 11 × 17) chia hết a561 − a với mọi số nguyên a. Năm 1899, Korselt đã lưu ý rằng có thể dễ dàng kiểm tra những số nguyên như vậy bằng cách sử dụng Tiêu chuẩn Korselt. n chia hết an − a với mọi số nguyên a nếu và chỉ nếu n là số không có ước chính phương khác 1 (squarefree) và p − 1 chia hết n − 1 với mọi số nguyên tố p chia hết n. Trong loạt bài báo nghiên cứu những năm 1910, Carmichael bắt đầu một nghiên cứu chuyên sâu về các hợp số với tính chất này, về sau được gọi là các số Carmichael (Carmichael numbers). Năm 1912, Carmichael trình bày thuật toán để xây dựng số như vậy, và phát biểu, có lẽ “danh sách này (các số Carmichael) có thể được mở rộng vô hạn” Giả thuyết của Carmicheal chỉ được chứng minh vào năm 1995, trong công trình của W. R. Alhfors, A. Granville và C. Pomerance. Năm 1939, Chernick đã lưu ý rằng nếu p = 6m + 1, q = 12m + 1 và r = 18m + 1 là các số nguyên tố thì pqr là một số Carmichael. Tính toán chưa công bố của Richard Pinch chỉ ra 8,241 số Carmichael nhỏ hơn 1012 , 19,279 nhỏ hơn 1013 , 44,706 nhỏ hơn 1014 và 105,212 số nhỏ hơn 1015 . Nếu gọi C(x) là số các số Carmicheal nhỏ hơn x thì nhiều tác giả đã cung cấp chặn trên cho C(x) C (x) ≤ x1−{1+o(1)} log log log x/ log log x với x → ∞. Năm 1994, trong [4], ba tác giả W.R. Alford, A. Granville, C. Pomer- ance đã chứng minh rằng C(x) > xα mọi số x lớn và với hằng số α nào đó.
18 Giá trị chính xác của α phụ thuộc vào hai hằng số khác xuất hiện trong Lý thuyết số giải tích. Bây giờ chúng ta mô tả những hằng số này. Giả sử π(x) là số các số nguyên tố p ≤ x, và giả sử π(x, y) là số các số trong số đó mà p − 1 không có các nhân tử nguyên tố vượt quá y. Giả sử E là ký hiệu tất cả các số E trong miền 0 < E < 1 mà tồn tại x1 (E), γ1 (E) > 0 sao cho π(x, x1−E ) ≥ γ1 (E)π(x) (2.1) với mọi x ≥ x1 (E). Năm 1935, Paul Erd¨os chỉ ra sự tồn tại một số nguyên dương nhỏ trong E . Các giá trị lớn hơn sau đó được tìm thấy bởi Wooldridge, Goldfeld, Pomerance, Fouvry và Grupp, Balog và Friedlander. Kết quả tốt √ nhất được biết đến (xem [4]) là bất kỳ số dương nào nhỏ hơn 1 − (2 e)−1 đều thuộc E . Erd¨os có giả thuyết nói rằng mỗi số dươngnhỏ hơn 1 đều thuộc E , nghĩa là E là khoảng mở (0, 1). Ta nhận xét rằng nếu E ∈ E , thì (0, E] ∈ E . Thêm nữa, có thể chứng minh rằng (sử dụng Bất đẳng thức Brun-Titchmarsh) rằng nếu E ∈ E thì E 0 ∈ E với E 0 > E nào đó. Do vậy, E là một khoảng mở. Định nghĩa π(x; d, a) là số các số nguyên tố nhỏ hơn hay bằng x thuộc cấp số cộng a modulo d. Định lý số nguyên tố đối với cấp số cộng phát biểu rằng π(x) π(x; d, a) ∼ với x → ∞, (2.2) ϕ(d) với điều kiện (a, d) = 1, trong đó ϕ là hàm Euler. Một bài toán quan trọng trong Lý thuyết số giải tích là tìm hiểu sự phụ thuộc có thể giữa d và a trong quan hệ tiệm cận này. Ví dụ, có thể d cũng dần tới vô hạn x dần đến vô hạn, và nếu vậy, tốc độ nhanh như thế nào? Người ta phỏng đoán rằng
19 (2.2) xảy ra đều với mọi số nguyên tố cùng nhau a, d với 1 ≤ d ≤ x1−ε , với mỗi ε > 0 cố định. Nếu chấp nhận Giả thuyết Riemann đối với L-hàm Dirichlet thì giả thuyết trên đây có thể được chứng minh cho miền hạn chế hơn 1 ≤ d ≤ x1/2−ε . Tuy nhiên, kết quả mạnh nhất được biết là Định lý Siegel-Walfisz mà trong đó khẳng định rằng (2.2) xảy ra đều với mọi cặp số nguyên tố cùng nhau a, d với 1 ≤ d ≤ (log x)k , với mỗi k cố định. Nếu ta sẵn sàng bỏ qua các bội của modul “đặc biệt” có thể, thì ta có thể cải thiện đáng kể miền trong Định lý Siegel-Walfisz. Thật vậy, nếu ψ(x) dần đến vô cùng chậm tuỳ ý thì (1.2) đúng với mọi cặp a, d nguyên tố cùng nhau với 1 ≤ d ≤ xψ(x) , trừ ra có thể là với những d mà là bội số của một số nguyên d1 (x) nào đó vượt quá một luỹ thừa của log x. Hơn nữa, nếu người ta nới lỏng quan hệ cận tiệm cận trong (2.2), thì có thể lấy 1 ≤ d ≤ xB với B > 0 nhỏ nào đó. Nếu cho phép nhiều moduli đặc biệt hơn, chúng ta có thể nhận được giá trị lớn hơn của B. Đặc biệt, nếu ký hiệu B là tập hợp các số B trong miền 0 < B < 1 mà với nó tồn tại một số x2 (B) và một số nguyên dương DB , sao cho nếu x ≥ x2 (B), (a, d) = 1 và 1 ≤ d ≤ min xB , y/x1−B thì π(y) π(y; d, a) ≥ (2.3) 2ϕ(d) mỗi khi d không chia hết cho bất kỳ phần tử nào của DB (x), là một tập hợp có không quá DB số nguyên, mỗi số vượt quá log x. Trong [4], các tác giả cũng chứng minh rằng (0, 5/12) ∈ B và chứng minh một định lý khá mạnh đối với các số trong khoảng này. Định lý về số Carmichael phụ thuộc nhiều vào tập E và B. Định lí 2.1.6. Với mỗi E ∈ E và B ∈ B tồn tại một số x0 = x0 (E, B) sao
20 cho C(x) ≥ xEB với mọi x ≥ x0 . √ Do 0, 1 − (2 e)−1 ⊂ E và (0, 5/12) ⊂ B, ta kết luận rằng C(x) ≥ xβ −ε với mỗi ε > 0 và mọi x lớn phụ thuộc việc chọn ε, trong đó √ 5 β = (1 − (2 e)−1 ) = 0.290306 . . . 12 Lập luận của bài báo dựa vào lập luận độc đáo của Erd¨os với những sửa đổi nhất định. Ý tưởng là xây dựng một số nguyên L mà với nó tồn tại rất nhiều số nguyên tố p sao cho p − 1 chia hết L. Giả sử rằng tích của một số trong những số nguyên tố đó C = p1 . . . pk là đồng dư với 1 mod L. Khi đó C là một số Carmichael, do mỗi p j − 1 chia hết L, mà L chia hết C − 1, và ta có thể áp dụng tiêu chuẩn Korselt như trên. Thật ra, càng có nhiều tích như vậy chúng ta có thể tìm thấy càng nhiều số Carmichael. Ta cần có tập các số nguyên tố p như vậy lớn đến mức nào để đảm bảo sự tồn tại của những tích như trên? Chúng ta có thể xem các số nguyên tố p như các phần tử của nhóm (Z/LZ)∗ của các thặng dư thu gọn theo mod L. Kết quả sau đây, theo Emde Boas và Kruyswijk (và mở rộng một định lý độc lập theo Kruyswijk và Olson) trả lời một phần câu hỏi trên. Định lí 2.1.7. Nếu G là một nhóm abel hữu hạn mà bậc cực đại của một phần tử là m, thì trong dãy có ít nhất m(1 + log(|G|/m)) (không nhất thiết phân biệt) phần tử của G, tồn tại một dãy con khác rỗng có tích là đơn vị. Để có thể áp dụng Định lí 2.1.7 tìm các số Carmichael bằng phương pháp vừa đề xuất, ta sẽ cần một số nguyên L, với ít nhất ϕ(L) λ (L) 1 + log ≥ λ (L) λ (L) số nguyên tố p mà p − 1 chia hết L. Ở đây hàm lambda Carmichael λ (L) là bậc lớn nhất của một phần tử trong (Z/LZ)∗ . Tuy nhiên, số các số nguyên