Luận văn Số giả nguyên tố và ứng dụng

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 pi(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. pi(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 pi(·): Định lí 1.2.2. Ta có lim n→∞ pi(n) n/ lnn = 1. Nói cách khác, giá trị pi(n) xấp xỉ bằng n/ lnn khi n vô cùng lớn. Ví dụ 1.2.3. Với n= 109, ta có pi(n) = 50847534 và n/ lnn= 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/ ln2k. Vậy về trung bình, ta cần ln2k 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 ln23072 ≈ 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) tức là tồn tại k sao cho 2n− 2 = kn. Ta có 2m−1 = 22n−2 = 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 b560 = ( b2 )280 ≡ 1 (mod 3), b560 = ( b10 )56 ≡ 1 (mod 11), b560 = ( b16 )35 ≡ 1 (mod 17). Từ đó suy ra b560 ≡ 1 (mod 561). Giả thuyết sau đây đã được chứngminh trongW. 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 ap− 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 choC(x) C (x)≤ x1−{1+o(1)} log loglogx/ log logx với x→ ∞. Năm 1994, trong [4], ba tác giả W.R. Alford, A. Granville, C. Pomer- ance đã chứng minh rằngC(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ử pi(x) là số các số nguyên tố p≤ x, và giả sử pi(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 0 sao cho pi(x,x1−E)≥ γ1(E)pi(x) (2.1) với mọi x ≥ x1(E). Năm 1935, Paul Erdo¨s 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ởiWooldridge, 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 . Erdo¨s 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 ′ ∈ E với E ′ > E nào đó. Do vậy, E là một khoảng mở. Định nghĩa pi(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 pi(x;d,a)∼ pi(x) ϕ(d) với x→ ∞, (2.2) 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 ≤ (logx)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 logx. 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ì pi(y;d,a)≥ pi(y) 2ϕ(d) (2.3) 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á logx. 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 choC(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 đó β = (1− (2√e)−1) 5 12 = 0.290306 . . . Lập luận của bài báo dựa vào lập luận độc đáo của Erdo¨s 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) ( 1+ log ϕ(L) λ (L) ) ≥ λ (L) số nguyên tố pmà 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 21 tố như vậy p không thể vượt quá τ(L), số các ước của L (do mỗi p như vậy là 1 cộng với một ước của L), và λ (L) lớn hơn nhiều τ(L). Để tránh vấn đề này chúng ta sẽ chọn L sao cho τ(L) là nhỏ, trong khi, đồng thời có nhiều số nguyên tố p mà p−1 chia hết L. Để làm điều này, ta chọn L là tích của các số nguyên tố q mà mọi nhân tử nguyên tố của q−1 không vượt quá y. Prachar cũng chứng minh rằng có nhiều vô hạn số nguyên m với hơn 2c logm/ log logm ước có dạng p− 1, p nguyên tố. Ở đây c > 0 là một hằng số nào đó phụ thuộc vào một số B ∈B. Không thể làm thực sự tốt hơn, do τ(m) ≤ 2(1+o(1)) logm/ log logm với mọi m khi m→ ∞. Phương pháp của Prachar là lấy một số L mà là tích của tất cả các số nguyên tố lớn đến một điểm nào đó và chứng minh rằng có một số nguyên k với k < Lc ′ và với m= kL có nhiều ước có dạng p−1. Với mục đích này, ta cần λ (kL) là nhỏ so với kL. Nhưng việc đưa vào nhân tử k bí ẩn đó có thể làm hỏng mọi việc, bởi vì không có nguyên nhân nào cho thấy λ (kL) không thể lớn tuỳ ý, ngay cả khi ta xuất phát từ một L mà với nó λ (L) là rất nhỏ so với L. Trong bài báo [4] các tác giả đã sửa đổi phương pháp của Prachar, để khi cho L, ta có thể tìm một số nguyên k nguyên tố cùng nhau với L sao cho có nhiều số nguyên tố p≡ 1 mod k mà p−1 chia hết kL. Trong [4, Section 6] các tác giả cũng trình bày chứng minh cho Định lý sau: Định lí 2.1.8. Với mỗi B ∈B, (0,B)⊂ E . Định lí 2.1.9. Cho ε > 0. Giả sử tồn tại một số xε sao cho pi(x;d,1)≥ pi(x) 2ϕ(d) với mọi số nguyên dương d ≤ x1−ε , x ≥ xε . Khi đó tồn tại một số x′ε sao 22 cho C(x) ≥ x1−2ε với mọi x ≥ x′ε . Đặc biệt, nếu một số xε như vậy tồn tại với mỗi ε > 0, thìC(x) = x1−o(1) khi x→ ∞. Chứng minh của Định lí 2.1.6 là hiệu quả theo ý nghĩa nếu các giá trị bằng số được cho với γ1(E), x1(E), và x2(B), thì giá trị bằng số đối x0(E,B) có thể tính được. Tuy nhiên, giá trị lớn của E mà ngày nay chúng ta biết là thuộc E đã được chứng minh thuộc E thông qua định lý không hiệu quả Bombieri-Vinogradov. Rất có thể, Định lý Friedlander nói rằng mọi số nguyên dương E < 1− (2√e)−1 là thuộc E , có thể được chứng minh từ một dạng yếu hơn, nhưng hiệu quả của định lý này, nhưng chúng ta không đưa vấn đề này ở đây. Điều thú vị cần lưu ý là chứng minh độc đáo của Erdo¨s rằng E chứa số dương E nào đó chỉ sử dụng phương pháp của Brun và do đó hiệu quả. Ta có định lý sau. Định lí 2.1.10. Với mỗi α trong miền 0 < α < 25/144, tồn tại một số có thể tính toán hiệu quả x(α) sao choC(x)≥ xα với mọi x≥ x(α). 2.2 Kiểm tra Miller và số giả nguyên tố mạnh Định nghĩa 2.2.1. Giả sử n là số nguyên dương lẻ, n− 1 = 2st, trong đó s là số nguyên không âm, t là số nguyên dương lẻ. Ta nói n trải qua được kiểm tra Miller cơ sở b, nếu hoặc bt ≡ 1 (mod n), hoặc b2 jt ≡−1 (mod n), với j nào đó, 0≤ j ≤ s−1. Ta chứng tỏ rằng, nếu n là số nguyên tố thì n trải qua được kiểm tra Miller cơ sở b với mọi số b sao cho n | b. Thật vậy, giả sử n−1= 2st. Đặt xk = b(n−1)/2 k = b2 (s−k)t , với k = 0,1, · · ·s. 23 Vì n là số nguyên tố nên x0 ≡ 1 (mod n). Do đó x21 ≡ 1 (mod n), tức là x1 ≡ 1 (mod n) hoặc x1 ≡ −1 (mod n). Tiếp tục quá trình như vậy ta sẽ đi đến kết luận rằng, hoặc xk ≡ 1 (mod n) với k = 0,1 · · ·s, hoặc xk ≡ −1 (mod n) với một số nguyên k nào đó. Như vậy n trải qua được kiểm tra Miller cơ sở b. Dễ thấy rằng, nếu n trải qua được kiểm tra Miller cơ sở b thì n sẽ là số giả nguyên tố cơ sở b. Ta có định nghĩa sau. Định nghĩa 2.2.2. Số nguyên n được gọi là số giả nguyên tố mạnh cơ sở b nếu nó là hợp số và trải qua được kiểm tra Miller cơ sở b. Như vậy các số giả nguyên tố mạnh lại còn ít hơn các số giả nguyên tố. Tuy nhiên, ta có định lý sau. Định lí 2.2.3. Tồn tại vô số số giả nguyên tố mạnh cơ sở 2. Chứng minh. Thật vậy, giả sử n là một số giả nguyên tố cơ sở 2. Khi đó, với số nguyên lẻ k nào đó, ta có 2n−1−1= nk. Đặt N = 2n−1, khi đó nó có ước là 2d−1, với d là ước số nào đó của n. Mặt khác, N−1= 2n−2= 2(2n−1−1) = 2nk, 2N−12 = 2nk = (2n)k ≡ 1 (mod N). Vậy với mỗi số giả nguyên tố n, ta xây dựng được số giả nguyên tố mạnh N với các số n khác nhau cho ta các số N khác nhau. Như vậy định lý được chứng minh, bởi vì có vô số giả nguyên tố cơ sở 2. Ta có thể dùng kiểm tra Miller để kiểm tra nguyên tố những số không lớn lắm. Ta biết rằng, số giả nguyên tố mạnh lẻ cơ sở 2 bé nhất là 2047. Như vậy, nếu n lẻ và n< 2047, thì n là nguyên tố nếu nó trải qua kiểm tra Miller. Tương tự như vậy, số 1373653, là số giả nguyên tố mạnh lẻ bé nhất 24 cơ sở 2 và 3, được dùng để kiểm tra nguyên tố những số bé hơn nó. Đối với cơ sở 2, 3 và 5, số giả nguyên tố mạnh lẻ bé nhất là 25326001, trong trường hợp cơ sở 2, 3, 5, 7, số tương ứng là 3215031751. Trong những số nhỏ hơn 25 · 109, chỉ có một số giả nguyên tố lẻ với cơ sở 2, 3, 5, 7, đó là 3215031751. Như vậy, nếu n< 25 ·109 là số lẻ trải qua kiểm tra Miller cơ sở 2, 3, 5, 7 thì n là số nguyên tố nếu nó khác với 3215031751. Cách làm trên đây chỉ áp dụng được khi cần kiểm tra nguyên tố những số không lớn. Đối với những số lớn, ta có thể dùng thuật toán xác suất dựa trên định lý sau đây: Định lí 2.2.4. Nếu n là một hợp số dương lẻ thì tồn tại không quá n−14 cơ sở b, 1≤ b≤ n−1 sao cho n trải qua được kiểm tra Miller đối với các cơ sở đó. Từ Định lý 2.2.4 suy ra rằng, nếu số b được chọn ngẫu nhiên trong khoảng 1≤ b≤ n−1 thì n trải qua kiểm tra Miller cơ sở b với xác suất bé hơn 1/4. Như vậy, nếu ta chọn k số ngẫu nhiên thì xác suất để n trải qua kiểm tra Miller đối với k cơ sở đó sẽ bé hơn 14k . Khi k đủ lớn, ví dụ k = 20, xác suất đó quá nhỏ, nên với n trải qua với 20 cơ sở ngẫu nhiên thì có thể tin “hầu chắc chắn” rằng n là số nguyên tố. Từ đó ta có thuật toán xác suất sau đây. Thuật toán (Rabin-Miller 1980). Cho N ≥ 3 lẻ, thuật toán sau đây xác định rằng N là một hợp số, hoặc in ra thông báo N là số nguyên tố với xác suất lớn hơn 1− 1420 . RM1 (Xuất phát). Đặt q←N−1, t← 0, và nếu q chẵn đặt q← q/2, t← t+1 (bây giờ ta có N−1= 2tq, với q lẻ). Sau đó đặt c← 20 25 RM2 (Chọn a mới). Chọn ngẫu nhiên số a trong khoảng 1 < a < N. Đặt e← 0, b← aq (mod N). Nếu b=1, chuyển sang RM4. RM3 (Bình phương). Nếu b 6≡±1 (mod n) và e< t−2, ta đặt b← b2 (modN), e← e+ 1. Nếu b 6= N− 1, in ra thông báo “n là hợp số” và kết thúc thuật toán. RM4 Đặt c← c− 1. Nếu c > 0, chuyển sang RM2. Nếu c = 0, in ra thông báo “N là số nguyên tố”. 2.3 Số giả nguyên tố Euler Giả sử p là số nguyên tố lẻ và b là số nguyên dương không chia hết cho p. Khi đó theo tiêu chuẩn Euler ta có b p−1 2 ≡ b p  (mod p). Như vậy, để kiểm tra một số n có phải là nguyên tố hay không, ta có thể lấy một số b nguyên tố cùng nhau với n, và kiểm tra xem đồng dư sau đây có đúng hay không. b n−1 2 ≡ b n  (mod n), trong đó vế bên phải là ký hiệu Jacobi. Nếu đồng dư thức đó không đúng thì n phải là hợp số. Nếu đồng dư thức trên đây nghiệm đúng, vẫn chưa kết luận được n có phải là nguyên tố hay không, nhưng “có nhiều khả năng” n là số nguyên tố. Định nghĩa 2.3.1. Số nguyên dương n được gọi là số giả nguyên tố Euler 26 cơ sở b nếu nó là một hợp số và đồng dư thức sau đây nghiệm đúng b n−1 2 ≡ b n  (mod n). Ta có mối liên hệ gữa số giả nguyên tố Euler cơ sở b và số giả nguyên tố cơ sở b sau đây: Định lí 2.3.2. Mọi số giả nguyên tố Euler cơ sở b đều là số giả nguyên tố cơ sở b. Chứng minh. Chỉ cần bình phương hai vế của đồng dư thức thoả mãn bởi các số giả nguyên tố Euler. Điều ngược lại không đúng. Chẳng hạn, có thể thấy rằng số 341 là số giả nguyên tố cơ sở 2 , nhưng không là số giả nguyên tố Euler cơ sở 2. Định lí 2.3.3. Mọi số giả nguyên tố mạnh cơ sở b đều là số giả nguyên tố Euler cơ sở b. Chứng minh. Cho n là số giả nguyên tố mạnh cơ sở b. Khi đó, nếu n−1= 2st, trong đó t lẻ, thì, hoặc bt ≡ 1 (mod n), hoặc b2rt ≡−1 (mod n), với r nào đó 0≤ r≤ s−1. Giả sử m ∏ j=1 pa jj là phân tích của n thành thừa số nguyên tố. Ta xét riêng hai trường hợp. Trường hợp thứ nhất bt ≡ 1 (mod n). Giả sử p là một ước nguyên tố của n. Khi đó ordpb | t, và do đó ordpb là số lẻ. Mặt khác, ordpb là ước của φ(p) = p−1, nên nó phải là ước của p−12 . Vậy ta có b p−1 2 ≡ 1 (mod p). 27 Theo tiêu chuẩn Euler b p = 1, và do đó b n = 1. Mặt khác ta có b n−1 2 = (bt)2 s−1 ≡ 1 (mod p). Vậy n là số giả nguyên tố Euler cơ sở b. Trường hợp thứ hai b2 rt ≡ −1 (mod n). Nếu p là một ước nguyên tố của n thì b2 rt ≡−1 (mod p). Bình phương cả hai vế của đồng dư thức này ta được b2 r+1t ≡ 1 (mod p). Từ đó suy ra ordpb | 2r+1t, nhưng ordpb không là ước của 2rt. Như vậy, ordpb= 2r+1c, trong đó c là một số nguyên lẻ. Mặt khác, vì ordpb | (p−1), 2r+1 | ordpb, nên 2r+1 | (p−1). Như vậy, ta có p= 2r+1d+1, trong đó d là số nguyên. Vì b ordp b 2 ≡−1 (mod p). nên ta cób p ≡ b p−12 = b ordp b2 p−1ordp b = (−1) p−1ordp b = (−1) p−12r+1 c (mod p). Vì c lẻ nên từ đó suy ra b p  = (−1)d. Bây giờ giả sử n có phân tích thành thừa số nguyên tố dạng m ∏ j=1 pa jj . Theo chứng minh phần trên, các ước nguyên tố pi có dạng pi = 2r+1di+1, và ta cób n = m∏ i=1  b pi a i = (−1) m ∑ i=1 aidi. 28 Mặt khác, dễ thấy rằng n≡ 1+2r+1 m ∑ i=1 aidi (mod 22r+2). Do đó t2s−1 = n−1 2 ≡ 2r m ∑ i=1 aidi (mod 2r+1), tức là t2s−1−r ≡ m ∑ i=1 aidi (mod 2), và b n−1 2 = ( b2 rt )2s−1−r = (−1) m ∑ i=1 aidi (mod n). Như vậy, b n−1 2 ≡ b n  (mod n). và n là số giả nguyên tố Euler cơ sở b. Định lý được chứng minh xong. Chú ý rằng, điều ngược lại không phải luôn luôn đúng, tức là tồn tại những số giả nguyên tố Euler cơ sở b không là giả nguyên tố mạnh cơ sở đó. Một ví dụ là với n= 1105, b= 2. Tuy nhiên, với những điều kiện bổ sung, một số giả nguyên tố Euler sẽ là giả nguyên tố mạnh cùng cơ sở. Ta có định lý sau: Định lí 2.3.4. Số n giả nguyên tố Euler cơ sở b là số giả nguyên tố mạnh cơ sở b nếu n≡ 3 (mod 4), hoặc b n =−1. Chứng minh. Trường hợp thứ nhất n ≡ 3 (mod 4). Khi đó n− 1 = 2t và t lẻ. Vì n là số giả nguyên tố Euler cơ sở b nên bt = b n−1 2 ≡ b n  (mod n). 29 Như vậy, n là số giả nguyên tố mạnh cơ sở b. Trong trường hợp thứ hai, ta viết n− 1 = 2st, trong đó t lẻ, s là số nguyên đương. Vì n là số giả nguyên tố mạnh cơ sở b nên b2 s−1t = b n−1 2 = b n  (mod n). Theo giả thiết ta có b2 s−1t ≡−1 (mod n). Vì b n =±1 cho nên hoặc bt ≡ 1 (mod n), hoặc bt ≡−1 (mod n). Như vậy n là số giả nguyên tố mạnh cơ sở b. Dùng số giả nguyên tố Euler, ta có thể xây dựng thuật toán xác suất để kiểm tra một số là nguyên tố hay không. Thuật toán này được tìm ra đầu tiên năm 1977 trong công trình R.M. Solovay, V. Strassen [8]: Ta bắt đầu bằng bổ đề sau. Bổ đề 2.3.5. Giả sử n là một số nguyên dương lẻ không chính phương. Khi đó tồn tại ít nhất một số b với 1< b< n, (b,n) = 1, sao cho b n =−1. Chứng minh. Nếu n là nguyên tố, số b tồn tại theo [1, Địn