Tài liệu Kỹ thuật lập trình - Chương 3: Kiểm tra và xây dựng số nguyên tố

Chia sẻ: | Ngày: | Loại File: DOC | Số trang:20

Thêm vào BST

Báo xấu

131
lượt xem 8
download

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

Dựa vào tính chất đặc biệt của số nguyên tố, mà khi xây dựng một số bài toán với việc áp dụng số nguyên tố, đặc biệt là ứng dụng số nguyên tố lớn, nó trở nên hữu ích cho mục đích bài toán. Trong chương này chúng ta đi tìm hiểu cách kiểm tra một số nguyên tố cho trước và làm thế nào để xây dựng được số nguyên tố lớn.

Chủ đề:

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

Lưu

Nội dung Text: Tài liệu Kỹ thuật lập trình - Chương 3: Kiểm tra và xây dựng số nguyên tố

Chương 3 KIỂM TRA VÀ XÂY DỰNG SỐ NGUYÊN TỐ Dựa vào tính chất đặc biệt của số nguyên tố, mà khi xây dựng một số bài toán v ới việc áp dụng số nguyên tố, đặc biệt là ứng dụng số nguyên tố lớn, nó trở nên hữu ích cho mục đích bài toán. Trong chương này chúng ta đi tìm hiểu cách kiểm tra một số nguyên tố cho trước và làm thế nào để xây dựng được số nguyên tố lớn. 3.1 Khái niệm về số nguyên tố Số tự nhiên p, lớn hơn 1 gọi là số nguyên tố nếu như nó chia hết cho 1 và chính nó. Định lý cơ bản của số học nói rằng, bất kỳ số tự nhiên n, lớn hơn 1 có thể phân tích thành tích các số nguyên tố. Tức là một số tự nhiên có thể biểu diễn dưới dạng sau α α n = p1 1 ... pk k , ở đây p1 < p2 < ... < pk - là các số nguyên tố khác nhau, α1 ,..., α k ∈ N . Bài toán kiểm tra số nguyên tố và xây dựng số nguyên tố lớn có ứng dụng rất quan trọng trong mã hóa. Trong phần này tác giả viết về các thuật toán khác nhau đ ể giải quyết những bài toán này 3.2 Kiểm tra số nguyên tố theo phương pháp thử Cho n ∈ N . Kiểm tra xem n có phải là số nguyên tố hay không Phương pháp thử chia Nếu như n là hợp số, thì n=ab, với 1 < a ≤ b , điều kiên là a ≤ n . Cho nên đối với [ ] d = 2,3,..., n chúng ta kiểm tra xem n có chia hết cho d hay không? Nếu như ước s ố của n không tìm thấy, thì n là số nguyên tố, ngược lại thì n là hợp số, và ta có thể phân tích n thành 2 thừa số. Độ phức tạp của phương pháp này là O( n ) . Sàng Eratosphen Nếu như chúng ta muốn thiết lập bảng tất cả các số nguyên tố giữa các số 2,3,…,N, thì đầu tiên cần gạch chân các số chia hết cho 2 ngọai trừ số 2. Sau đó ta lấy các số 3 và gạch chân các số tiếp theo và chia hết cho 3. Sau đó chúng ta chọn số tiếp theo và không gạch chân (có nghĩa là 5), và tiếp tục gạch chân các số chia hết cho 5, và tiếp tục như thế. Và cuối cùng chúng ta có được dãy các số nguyên tố. Phương pháp này thì t ốn nhiều bộ nhớ, nhưng để thành lập bảng nguyên tố thì đây là cách hiệu quả nhất.
3.3 Kiểm tra tính nguyên tố của số có dạng đặc biệt Chúng ta xem số n dạng n = 2 m + 1 , ở đây m ∈ N . Nếu m chia hết cho số nguyên tố p > 2 , tức là m = pm1 , m1 ≥ 1 , thì n = (2m1 ) p + 1 chia hết cho 2 m1 + 1 , có nghĩa là n là hợp số. Cho nên số nguyên tố có thể chỉ khi m = 2k . k Định nghĩa 3.1. Số Fk = 2 2 + 1, k = 0,1,2,..., gọi là số Fermat. Hiện tại chúng ta biết được rằng F0 , F1 , F2 , F3 , F4 là số nguyên tố, còn các số Fermat tiếp theo 5 ≤ k ≤ 32 là hợp số, còn các số tiếp theo thì chưa được kiểm tra. Để kiểm tra tính nguyên tố của số Fermat chúng ta xem định lý sau Định lý 3.1. Số n = Fk khi k>0 là số nguyên tố khi và chỉ khi: n −1 3 2 ≡ −1(mod n) . Chứng minh: Chúng ta chứng minh điều kiện đủ. Chúng ta có: n − 1 = 22 . Từ k n −1 n −1 3 2 ≡ −1(mod n) , nên 3 ≡ 1(mod n) , điều này có nghĩa là bậc của 3 (mod n) bằng * n − 1 = 2 2 . Nên nhóm nhân Z n có ít nhất là n-1 phần tử, và các phần tử khác không của k Zn khả nghịch, hay n là số nguyên tố. k k −1 Bây giờ ta chứng minh phần nghịch. Chú ý rằng 2 2 ≡ 42 ≡ 1(mod 3) . Bởi vậy n>3, n ≡ 2(mod 3), n ≡ 1(mod 4) . Theo định luật bình phương (định lý Gausse) ta có ( n −1)( 3 −1) n−1 3 n n 2 3   =  .( −1) 4 =   =   = −1 . Theo tiêu chuẩn Euler thì  ≡3 2 (mod n) . n 3  3 3 n Kiểm tra theo định lý này độ phức tạp là O(log n) , thế nhưng số Fermat tăng lên rất nhanh, nên cách kiểm tra này trở nên không hiệu quả. Bây giờ chúng ta xem số n dạng n = 2m − 1 . Nếu m là hợp số, m=ab, 1 < a ≤ b , thì n = 2 ab − 1 chia hết cho n = 2 a − 1 . Cho nên số n là nguyên tố chi khi m là số nguyên tố. Định nghĩa 3.2. Cho p là số nguyên tố, và M p= 2 − 1 cũng là số nguyên tố. Và số p M p gọi là số nguyên tố Mersenn. Để kiểm tra tính nguyên tố của số Mersenn ta dùng định lý sau Định lý 3.2. Cho q là số nguyên tố, q>2, n = 2q − 1 . Chúng ta xem dãy L0 , L1 , L2 ,..., xác định dãy này như sau L0 = 4 ; L j +1 ≡ L2j − 2(mod n) .
Số n là số nguyên tố khi và chỉ khi Lq − 2 ≡ 0(mod n) Định lý 3.3 Cho p là số nguyên tố, p ≡ 3(mod 4) , M p= 2 − 1 . Số Fermat Fp là số p nguyên tố khi và chi khỉ ( F p −1) / 2 Mp ≡ −1(mod Fp ) . p −1 Chứng minh: Theo định lý nhỏ Fermat ta có 2 2 ≡ 2(mod M p ) , từ đây + 1 ≡ 5(mod M p ) . Dẫn đến UCLN ( Fp , M p ) = 1 , và dẫn đến p −1 Fp = 2.22 F p −1 M   F   5  Mp  M 2 ≡ p ≡ p ≡ ≡ (mod Fp )  F  M  M   5     p   p   p  4k +3  Mp  2 Cho nên M p = 2 − 1 ≡ 23 − 1(mod 5) ≡ 2(mod 5),    =   = −1   5  5 Định nghĩa 3.3 (dãy số Liuka). Cho dãy số u0 , u1 , u2 ,... và v0 , v1 , v2 ,..., với u0 = 0, u1 = 1, v0 = 2, v1 = 4 , còn các thành phần tiếp theo của dãy được tính theo công thức truy hồi x j +1 = 4 x j − x j −1 , được gọi là dãy số Liuka. 3.4 Phương pháp N ± 1 kiểm tra tính nguyên tố và xây dựng số nguyên tố lớn Trong mục này chúng ta sẽ tìm hiểu một số phương pháp, mà với sự giúp đỡ của nó chúng ta có thể kiểm tra tính nguyên tố của số tự nhiên N, khi biết được hoàn toàn hoặc một phần của sự phân tích N ra thừa số. Và chúng ta cũng tìm hiểu một số phương pháp tạo ra số nguyên tố lớn được áp dụng trong mật mã. Đầu tiên chúng ta xem phương pháp N-1 kiểm tra số nguyên tố. k Định lý 3.4 Cho n ∈ N , n > 1 , n là số lẻ, n − 1 = ∏ pi - đã biết được sự phân chia α i i =1 thành thừa số nguyên tố của n-1. Nếu như đối với mỗi i = 1,..., k tồn tại số ai ∈ N , sao cho n −1 ain −1 ≡ 1(mod n) , a pi ≠ 1(mod n) , i thì n là số nguyên tố. Chứng minh: Cho mi là bậc của ai (mod n) trong Z n . Từ điều kiện chúng ta có mi | n − 1 , và mi n −1 α mi không là ước của , cho nên pi i | mi với i=1,…,k. Dẫn đến b ≡ a piαi (mod n) có bậc là pi i i
piα i trong Z n * , còn phần tử b = b1 ⋅ ... ⋅ bk (mod n) có bậc là p1 1 ⋅ ... ⋅ pk k = n − 1 trong Z n * . α α Điều này có nghĩa là Z n là một trường, và n là số nguyên tố. Từ định lý này chúng ta có thể kiểm tra được tính nguyên tố như sau. Phân tích n-1 ra thừa số, chọn a=2,3,…, kiểm tra điều kiện định lý. Nếu như tìm thấy a nào đó, với 1 < a < n , mà a n −1 ≠ 1(mod n) , thì n là hợp số. Nếu như tìm được a1 ,..., ak , mà thỏa mã điều kiện định lý thì n là số nguyên tố. Tương tự với việc kiểm tra số nguyên tố bằng phương pháp n-1, ta tìm hiểu phương pháp n+1 khi biết hoàn toàn các nhân tử nguyên tố của n+1 Định lý 3.5. Cho P, Q ∈ Z , D = P 2 − 4Q ≠ 0 . Xác định dãy số Liuka u0 , u1 ,... và định thức D bằng các biểu thức sau: u0 = 0, u1 = 1, u j + 2 = Pu j +1 − Qu j điều kiện là j ≥ 0 . Cho n là k một số tự nhiên lẻ, n>1, n + 1 = ∏ qi - tức là phân tích n+1 ra thừa số nguyên tố, và βi i =1 D   = −1 . Nếu như đối với từng i = 1,..., k , tìm được Pi , Qi ∈ Z , D = Pi 2 − 4Qi , sao cho có n quan hệ với dãy số Liuka u0i ) , u1(i ) ,... thỏa mãn điều kiện: ( n | uni+)1 và n không là ước của u((n)+1) / qi ( i , thì n là số nguyên tố. Nếu như tồn tại dãy số Liuka {u j } như thế và D, sao cho un +1 không chia hết cho n, thì n là hợp số. Định lý 3.6 Cho n ∈ N , n>1, n là số lẻ, n − 1 = F1 ⋅ R1 , với UCLN ( F1 , R1 ) = 1 . Giả sử k chúng ta biết được hoan toàn sự phân tích ra thừa số nguyên tố F1 = ∏ q j . Nếu như đối j α j =1 với mỗi j=1,…,k tìm được a j ∈ N , sao cho ( n −1) / q j a n −1 ≡ 1(mod n) , UCLN (a j j − 1, n) = 1 với điều kiện F1 ≥ n , thì số n là số nguyên tố. Chứng minh: Giả sử p là ước số nguyên tố của n. Chúng ta chứng minh rằng p > n , từ đây dẫn đến n là số nguyên tố. Từ điều kiện chúng ta có a n −1 ≡ 1(mod n) dẫn đến a n −1 ≡ 1(mod p ) , từ đây j j UCLN (a j , p) = 1 và bậc e j của phần tử a j (mod p ) trong Z p không là ước của n-1. Ngoài
ra theo định lý nhỏ Fermat thì e j | ( p − 1) . Từ điều kiện của định lý ta có k ≠ 1(mod p) , từ đây q j j | e j . Dẫn đến q j j | ( p − 1) , và F 1= ∏ q j | ( p − 1) . Nghĩa là ( n −1) / q j α α j α aj j =1 p − 1 ≥ F1 , p > F1 ≥ n . Chúng ta sẽ chứng minh với sự giúp đỡ của định lý này có thể xây dựng đ ược s ố nguyên tố lớn. Chúng ta xây dựng dãy số nguyên tố p1 < p2 < p3 < ..., cho đến khi xây dựng được số nguyên tố đủ lớn chúng ta cần. Số nguyên tố p1 chọn bất kỳ, ví dụ p1 = 3 . Giả sử chúng ta đã xây dựng được số nguyên tố pi −1 . Chọn số ngẫu nhiên r, 1 ≤ r ≤ pi −1 − 1 . Giả sử: r = 2 s t , t là số lẻ. Như thế số nguyên tố pi chúng ta chọn n = 2rpi −1 + 1 = 2 s +1 pi −1t + 1 . Đặt F1 = 2 s +1 pi −1 , R1 = t . Rõ ràng rằng UCLN ( F1 , R1 ) = 1 và s +1 s+2 s+2 2 chúng ta cũng có F1 > n , bởi vì n = 2 pi −1t + 1 < 2 pi −1t < 2 pi −1 ≤ F1 . Dẫn đến để 2 chứng tỏ n là số nguyên tố, chúng ta cần tìm các số a1 và a2 , sao cho n −1 n −1 a1n −1 ≡ a2 −1 ≡ 1(mod n) , UCLN (a 2 − 1, n) = UCLN (a pi −1 − 1, n) = 1 . n 1 2 Nếu như ta tìm được số a, sao cho a n −1 ≠ 1(mod n) , thì n là hợp số và chúng ta cần chọn số ngẫu nhiên r khác. Nếu như chúng ta chứng minh được n là nguyên tố thì đ ặt pi = n . Một phương pháp khác xây dựng số nguyên tố ứng dụng định lý trên có thể nêu ra dưới đây. Chúng ta lại xây dựng dãy số nguyên tố, và giả sử xây dựng pi −1 > 3 . Chúng ta chọn số chẵn ngẫu nhiên r, thỏa mãn 1 ≤ r ≤ pi −1 − 3 , và đặt n = pi −1r + 1 . Giả sử F1 = pi −1 , R1 = r , UCLN ( F1 , R1 ) = 1 .Chúng ta cần tìm một số tự nhiên a sao cho n −1 a n −1 ≡ 1(mod n),UCLN (a r − 1, n) = 1 (bởi vì = r ). Rõ ràng ta có bất đẳng thức pi −1 F1 = pi −1 > n , bởi vì n = pi −1r + 1 ≤ pi −1 ( pi −1 − 3) + 1 = pi2−1 − 3 pi −1 + 1 ≤ pi2−1 Chọn a và thực hiện tương tự như phương pháp xây dựng trên. Định lý tiếp theo sẽ cho chúng ta cách xây dựng số nguyên tố hiệu quả hơn, bởi vì không cần tính toán ước nguyên tố lớn.
Định lý 3.7 Cho n = 2rq + 1 , ở đây q là số nguyên tố lẻ, và r với r ≤ 2q + 1 . Nếu tồn tại số a ∈ N , sao cho a n −1 ≡ 1(mod n) , a 2 r ≠ 1(mod n) , thì n là số nguyên tố. Chứng minh. Giả sử n là hợp số, n = pN , với p là số nguyên tố, N > 1 . Bởi vì n không là ước của a 2 r − 1 , nên tồn tại số nguyên tố p sao cho ν p (n) > ν p (a − 1) và khi 2r s = ν p (a 2 r − 1) + 1 ≥ 1 chúng ta có p s | n và p s không là ước của a 2 r − 1 . Giả sử d là bậc của a (mod p s ) trong Z p . Số d được xác định và d|n-1=2rq, bởi vì S a n −1 ≡ 1(mod n) . Ngoài ra ta có d | φ ( p s ) = p s −1 ( p − 1) . Nhưng từ biểu thức a 2 r ≠ 1(mod p s ) dẫn đến d không là ước của 2r. Nghĩa là q|d. Bởi vì q | p s −1 ( p − 1) . Số q và p khác nhau, bởi vì p|n, q|n-1. Dẫn đến q|p-1. Từ đây p ≡ 1(mod q) , và do tính lẻ của p và q nên p ≡ 1(mod 2q) . Ngoài ra n ≡ 1(mod 2q) . Bởi vì n=pN, nên N ≡ 1(mod 2q ) . Bởi vì p > 1 và N > 1, nên p ≥ 1 + 2q, N ≥ 1 + 2q . Nghĩa là n = pN ≥ (1 + 2q) 2 . Thế nhưng n = 2rq + 1 ≤ 2q (2q + 1) + 1 < (1 + 2q ) 2 . Nhận được mâu thuẩn. Nên định lý được chứng minh. Định lý 3.8 Cho n = 2qr + 1 , ở đây q là số nguyên tố, r ≤ 4q + 2 . Giả sử tồn tại a ∈ N , sao cho a n −1 ≡ 1(mod n) , a 2 r ≠ 1(mod n) . Thế thì n hoặc là số nguyên tố, hoặc n = p 2 , với p = 2q + 1 - là số nguyên tố và a p −1 ≡ 1(mod p 2 ) . Chứng minh. Giả sử n là hợp số, n = pN , với p là số nguyên tố, N > 1 . Chúng ta chứng minh được rằng n ≡ p ≡ N ≡ 1(mod 2q ) . Nếu như một trong hai số p và N lớn hơn nhiều so với 1+ 2q , thì nó sẽ lớn hơn hoặc bằng 1 + 4q , và n = pN ≥ (1 + 2q)(1 + 4q ) = 8q 2 + 6q + 1 . Nhưng điều kiện n ≤ 2q (4q + 2) + 1 = 8q 2 + 4q + 1 . Dẫn đến p = N = 1 + 2q, n = p 2 . Chứng minh phần còn lại a p −1 ≡ 1(mod p 2 ) . Rõ ràng theo điều kiện và n=p2 nên chúng ta có a p 2 −1 ≡ 1(mod p 2 ) , theo 2 định lý Euler thì a p − p ≡ 1(mod p 2 ) , từ đây dẫn đến điều phải chứng minh.
Chú ý: Nếu biết được q thì kiểm tra đẳng thức n = (2q + 1) 2 rất dễ dàng. Có nghĩa là khi biết được a, chúng ta sẽ biết được n là nguyên tố hay hợp số. Từ đ ịnh lý kiểm tra tính nguyên tố này chúng có thể xây dựng số nguyên tố lớn rất hiệu quả, bởi vì càng lớn giới hạn trên của số ngẫu nhiên r thì càng đạt đ ược việc xây d ựng s ố nguyên t ố như ý. Các định lý 1.25 – 1.29 độ lớn phân chia số n-1 có bậc n1 / 2 . Định lý sau độ lớn phân chia số n-1 sẽ có bậc nhỏ hơn n1 / 3 . Định lý 3.9 Giả sử n là số lẻ, n > 1, n − 1 = F1 R1 , ở đây UCLN ( F1 , R1 ) = 1 , F1 là số chẳn, và ta biết được hoàn toàn sự phân chia F1 ra thừa số nguyên tố. Giả sử đối với bất kỳ ước nguyên tố q của F1 tìm thấy được a q ∈ N , sao cho a q −1 ≡ 1(mod n) , UCLN (aqn −1) / q − 1, n) = 1 . n ( Giả sử m ∈ N đối với từng l = 1,2,..., m − 1 , thì lF1 + 1 không là ước của n nếu n < ( mF1 + 1)(2 F12 + ( L − m) F1 + 1) , ở đây R1 = 2 F1 L1 + L , 1 ≤ L < 2 F1 , thì n là số nguyên tố khi và chỉ khi hoặc R1 = L , hoặc L2 − 8L1 không là số chính phương. 3.5 Kiểm tra số nguyên tố bằng thuật toán Konigin-Pomerans Nếu n ∈ N và biết được sự phân tích hoàn toàn hoặc một phần lớn ra thừa s ố nguyên tố của số n-1, thì có thể để kiểm tra xem n là hợp số hay là số nguyên tố với độ phức tạp theo đa thức. Đánh giá tốt nhất độ phức tạp nhận được từ thuật toán Konigin- Pomerans: k Định lý 3.10 Giả sử n ∈ N , n > 1 , n là số lẻ, n − 1 = ∏ q j . Lúc này việc kiểm tra tính j a j =1  ( log n ) 17 / 7  nguyên tố của n có thể có chi phí là O  log log n .    Định lý 3.11 Giả sử n ∈ N , n > 1 , n là số lẻ, n − 1 = F1 .R1 , ở đây UCLN ( F1 , R1 ) = 1 , và 1 biết được sự phân chia F1 ra thừa số nguyên tố. Nếu F ≥ n 4 n +ε , với ε là số dương 1 không đổi, thì việc kiểm tra tính nguyên tố của n có thể chi phí là O((log n) c (ε ) ) ( c(ε ) là số nguyên dương không đổi, phụ thuộc vào ε ).
Bổ đề 3.1. Giả sử a, m ∈ N , a m ≡ 1(mod n) , và giả sử đối với từng ước nguyên tố q của m thỏa mãn UCLN (a m / q − 1, n) = 1 . Khi đó nếu p là số nguyên tố và p | n , thì p ≡ 1(mod m) . Chứng minh. Rõ ràng rằng m là bậc của a (mod n) trong Z n . Giả sử p là số nguyên tố, và ước của n, và giả sử k là bậc của a (mod p). Như thế k=m. Rõ ràng, k|m bởi vì từ a m ≡ 1(mod n) , dẫn đến a m ≡ 1(mod p ) . Nếu như k
[ ] 6. Bước 6. Nếu như a ≤ log n , thì quay về tầng 2 với a là giá trị tiếp theo. Nếu 2 như a = [log 2 n] + 1 , thì n là hợp số. Chúng ta chứng minh tính đú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 O(log 4 n) . 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 O(log n) lệnh. Bước 2 của tầng tốn O(log 3 n) lệnh nhờ sự giúp đở của thuật toán hổ trợ sau Thuật toán tìm bậc của phần tử N Cho đầu vào thuật toán a, n ∈ N , n − 1 = ∏ p j - tức là biết được sự phân tích ra αj j =1 thừa số nguyên tố của số n-1. Đầu ra là bậc của a (mod n) trong Z n . Bước 1. M = n − 1, j := 0 . αj Bước 2. j := j + 1, M := M / p j , A := a M . Bước 3 (Chu trình). Đối với l = 0,1,...,α j , kiểm tra xem điều kiên sau có thỏa mãn không A ≡ 1(mod n) . Nếu như đúng thì nhảy sang bước 4. Ngược lại M := Mp j , A := A p j ; Và chuyển đến giá trị tiếp theo của l trong chu trình. Bước 4. Nếu như j
Trở lại thuật toán kiểm tra tính nguyên tố. Nếu như UCLN trong bước 3 của tầng 2 không bằng 1, thì n là hợp số. Rõ ràng rằng, theo định nghĩa E(a) không có một số nào từ số a E ( a ) / q − 1 chia hết cho n. Có nghĩa là gcd lớn hơn 1, một trong các số a E ( a ) / q − 1 có với n ước chung là d, 1 n log a >n 2 log log n = n , bởi vì a > log 2 n , dẫn đến log a > 2 log log n . Vậy chúng ta đã dẫn đến mâu thuẫn. 3.6 Kiểm tra tính nguyên tố bằng thuật toán Millier
Cho f : N → R * - hàm số trên tập số tự nhiên, với f(n)1. Bước 1. Kiểm tra điều kiện sau có thỏa mãn hay không n = m s , với s, m ∈ N , s ≥ 2 . Nếu như thỏa mãn, thì n là hợp số, và thuật toán dừng. Bước 2. Thuật hiên các bước nhỏ (i)-(iii) đối với tất cả a ≤ f (n) (i) Kiểm tra điều kiện a|n (ii) Kiểm tra điều kiện a n −1 ≠ (mod n) (iii) Kiểm tra xem có đúng hay không, với một số giá trị của k, 1 ≤ k ≤ v2 (n − 1) , n−1 1 < UCLN (a 2k − 1(mod n), n) < n Nếu như một trong ba điều kiện (i)-(iii) thỏa mãn thì n là hợp số, và thuật toán dừng. Bước 3. Nếu như chúng ta đi đến được bước này thì n là số nguyên tố. Chú ý. Hàm va (b) là số k lớn nhất thỏa mãn a k | b . 3.7 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 dùng nhất là các thuật toán ngẫu nhiên. Giả sử có một mệnh đề Q(p,a) nào đó đúng với mọi số nguyên tố p và một số tự nhiên a
(iii) 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ỏ n là hợp số thì ta kết luận n 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 Fermat (kiểm tra Fermat. Đây là phép thử heuristic; tuy nhiên ít người sử dung phép thử này. Được sử dụng nhiều hơn là Kiểm tra Miller-Rabin 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ố). Chúng ta đi tìm hiểu kỷ hai từng cách kiểm tra 3.7.1 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ư n là số nguyên tố thì bất kỳ số a ∈ Z thỏa mãn phương trình sau (1) a n ≡ a(mod n) Nếu như UCLN (a, n) = 1 , thì (2) a n −1 ≡ 1(mod n) . Cho nên để kiểm tra tính nguyên tố của n, chúng ta chọn một số bất kỳ a ∈ 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 như định lý 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 vì định lý 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ố a ∈ Z , thì ta vẫn có được đằng thức a n ≡ a (mod n) , số này còn được gọi là số Carmichael. Ví dụ, chúng ta xem số 561=3.11.17. Chúng ta chứng số này là số Carmichael. Đồng dư thức a 561 ≡ a(mod 561) sẽ tương đương với hệ a 561 ≡ a(mod 3) , a 561 ≡ a(mod11) , a 561 ≡ a(mod17) . Nếu 3|a, thì a 561 ≡ a ≡ 0(mod 3) . Nếu như 3 không là ước của a, thì a 2 ≡ 1(mod 3) , từ đây ta có a 560 ≡ 1(mod 3) , hay a 561 ≡ a(mod 3) . Tương tự kiểm tra đối với hai số 11 và 17. Như vậy 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: 1. Chọn ngẫu nhiên a từ tập {1,2,..., n − 1} và kiểm tra điều kiện UCLN(a,n)=1 2. Nếu như điều kiện trên không thỏa mãn thì n là hợp số 3. Kiểm tra đẳng thức (2)
4. Nếu như đẳng thức (2) không thỏa mãn thì trả lời n là hợp số 5. 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 khac nhau. Giải thuật Fermat kiểm tra tính nguyên tố của số Đầu vào: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm tra . Đầu ra: hợp số nếu n là hợp số, nếu không nguyên tố xác suất repeat k times: lấy a ngẫu nhiên trong [1, n − 1] if an − 1 mod n ≠ 1 then return hợp số return nguyên tố xác suất Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán là O(k × log3n), ở đó k là số lần kiểm tra với mỗi số a ngãu nhiên, và n là giá trị ta muốn kiểm tra. Và từ việc kiểm tra này dẫn ta đến phần sau. Định nghĩa 3.4 Cho n>1 là số tự nhiên lẻ, n − 1 = 2 2.d , ở đây d là số lẻ. Số n gọi là số giả nguyên tố chặc chẽ trong cơ sỡ a, a ∈ N , nếu như UCLN (a, n) = 1 hoặc a d ≡ 1(mod n) , hoặc a d .2 ≡ −1(mod n) , với 0 ≤ r < s . r Từ định nghĩa chúng ta có điều sau. Nếu n là số nguyên tố, thì a n −1 ≡ 1(mod n) , tức là s s −1 s −1 a2 d ≡ 1(mod n) . Từ đây ta có a 2 d ≡ ±1(mod n) . Nếu như a 2 d ≡ −1(mod n) , thì chúng ta s −1 dừng, nếu như a 2 d ≡ 1(mod n) , thì chúng ta lại khai căn cho đến khi tìm được a d hay căn đó đồng dư với -1. Để kiểm tra tính nguyên tố của các số lẻ n, 7 < n < 25.109 , ta dùng quá trình như sau: Bước 1: Kiểm tra tính chặc chẽ giả nguyên tố của n trong cơ sỡ 2,3,5,7. Nếu n không là chặc chẽ giả nguyên tố một trong các cơ sỡ đó thì n là hợp số. Bước 2: Nếu n=3215031751, thì n là hợp số, ngược lại n là số nguyên tố. Như vậy chúng ta thấy việc kiểm tra trên cơ sỡ tính chặc chẽ giả nguyên tố là hiệu quả đối với việc tìm số hợp số, thế nhưng cách này cũng chỉ đúng trong một điều kiện cần thiết. Trong một số kết quả chứng tỏ rằng, điều kiện cần và đ ủ đ ể kiểm tra s ố nguyên tố là n < (67107840) 2 . 3.7.2 Kiểm tra bằng Miller-Rabin
Kiểm tra Miller-Rabin là một thuật toán xác suất để kiểm tra tính nguyên tố .Nó được đề xuất đầu tiên bởi Gary L. Miller như một thuật toán tất định, dựa trên giả thiết Riemann tổng quát; Michael O. Rabin đã sửa chữa nó thành một thuật toán xác suất. Khi sử dụng kiểm tra Miller-Rabin chúng ta căn cứ vào một mệnh đ ề Q(p,a)đúng với các số nguyên tố p và mọi số tự nhiên a ∈ A ⊂ N và kiểm tra xem chúng có đúng với số n muốn kiểm tra và một số a ∈ A được chọn ngẫu nhiên hay không? Nếu mệnh đề Q(n,a) không đúng, tất yếu n không phải là số nguyên tố, còn nếu Q(n,a) đúng, số n có thể là số nguyên tố với một xác suất nào đó. Khi tăng số lần thử, xác suất đ ể n là s ố nguyên tố tăng lên. Bổ đề 3.2 Cho trường hữu hạn Z p , trong đó p là số nguyên tố. Chắc chắn rằng 1 và -1 luôn là các căn bậc hai của 1 theo mođun p. Chúng là hai căn bậc hai duy nhất của 1. Thật vậy, giả sử rằng x là một căn bậc hai của 1 theo mođun p. Khi đó: x 2 ≡ 1(mod p) x 2 − 1 ≡ 0(mod p ) ( x − 1)( x + 1) ≡ 0(mod p ) Từ đó, x − 1 hoặc x + 1 là chia hết cho p. Bây giờ giả sử p là một số nguyên tố lẻ, khi đó p - 1 là số chẵn và ta có thể viết p − 1 dưới dạng 2 s ⋅ m , trong đó s là một số tự nhiên lớn hơn hay bằng 1 và m là số lẻ - Điều này nghĩa là ta rút hết các thừa số 2 khỏi p − 1. Lấy số a bất kỳ trong tập {1,2,..,p- 1}. Xét dãy số xk = a 2 ⋅m với k=0,1,2,...,s. Khi đó xk = (xk − 1)2, với k=1,2,...,s và xs = a p −1 . k Từ định lý Fermat nhỏ: a p −1 ≡ 1(mod p ) Hay xs ≡ 1(mod p ) Hay xs2−1 ≡ 1(mod p ) Do đó hoặc xs −1 ≡ 1(mod p ) hoặc xs −1 ≡ −1(mod p ) . Nếu xs −1 ≡ −1(mod p ) ta dừng lại, còn nếu ngược lại ta tiếp tục với xs − 2. Sau một số hữu hạn bước ta có: hoặc ta có một chỉ số k, 0 ≤ k ≤ s − 1 sao cho xk ≡ −1(mod p) , hoặc tới k=0 ta vẫn có xk ≡ 1(mod p) .
Ta có mệnh đề Q(p,a) như sau: Nếu p là số nguyên tố lẻ và p - 1 = 2 s ⋅ m thì với mọi k a: 0
Điều này là mâu thuẫn. Xác suất trả lời sai: Định lý 3.12: nếu n là hợp số dương lẻ thì trong các số a ∈ {2,..,n-1} tồn tại không n −1 quá cơ sở a để n là số giả nguyên tố mạnh Fermat. 4 Gọi A là biến cố "Số n là hợp số". B là biến cố "Kiểm tra Miller-Rabin trả lời n là số nguyên tố". Khi đó xác suất sai của kiểm tra này là xác suất để số n là hợp s ố trong khi thuật toán cho câu trả lời TRUE, nghĩa là xác suất điều kiện P(A|B). Theo định lý trên nếu n là hợp số thì khả năng kiểm tra này trả lời TRUE xảy ra với 1 1 xác suất không vượt quá , nghĩa là P(B|A) ≤ . Tuy nhiên để tính xác suất sai của 4 4 kiểm tra Miller-Rbin cần tính xác suất diều kiện P(A|B). Dựa trên định lý về ước lượng số các số nguyên tố ta đưa ra ước lượng 2 ln n − 2 P ( A) ≈ 1 − ≈ ln n ln n Theo định lý Bayes trong lý thuyết xác suất ta có công thức đ ể tính xác suất sai c ủa kiểm tra Miller-Rabin là: P(B | A ) ⋅ P ( A) P ( B | A) ⋅ P ( A) P( A | B) = = P( B ) P ( B | A) ⋅ P ( A) + P( B | A) ⋅ P ( A) 1 Trong công thức này P(A) đã biết ở trên, P(B|A) ≤ , còn P( B | A) = 1 vì khi n là số 4 2 nguyên tố thì chắc chắn mệnh đề Q(n,a) là đúng và P( A) = 1 − P( A) = . Từ đây ta có ln n P ( B | A) ⋅ (ln n − 2) P( A | B) = P ( B | A) ⋅ (ln n − 2) + 2 Kiểm tra Miller-Rabin lặp: Theo công thức tính xác suất sai trên đây, với n lớn (cỡ 130 chữ số thập phân), n ếu thực hiện phép thử Miller-Rabin chỉ một lần, xác suất sai là khá lớn, tới trên 90%. Để giảm xác suất sai, ta lặp lại phép thử k lần với k số ngẫu nhiên a khác nhau, nếu n vượt 1 qua 50 lần thử thì P(B|A) ≤ , khi thay vào công thức với 50 lần thử nếu cả 50 l ần, 4k phép thử đều "dương tính" thì xác suất sai giảm xưống chỉ còn là một số rất nhỏ không vượt quá 9 ⋅10 −29 .
3.7.3 Kiểm tra bằng Solovay-Strasen Xem tiêu chuẩn Euler là mệnh đề Q(p,a). Khi đó Q(p,a) đúng với mọi số nguyên tố p và mọi số tự nhiên a, 1 ≤ a < p . Thay số nguyên tố p bằng số lẻ n ta định nghĩa: Hợp số n được gọi là số giả nguyên tố Euler cơ sở a(1 ≤ a < n ) nếu: a  ≡a ( n−1) / 2 (mod n) . n n Định lý 3.13 Nếu n là hợp số lẻ thì tồn tại không quá số tự nhiên dương a nhỏ 2 hơn n, nguyên tố cùng nhau với n sao cho n là số giả nguyên tố Euler cơ sở a. Chứng minh: n −1 b Chúng ta đi chứng minh tồn tại số b ∈ N , mà UCLN (b, n) = 1 và b 2 ≠  (mod n) . n α α Giả sử n = p1 ⋅ ⋅ ⋅ pk - tức là phân tích n ra thừa số nguyên tố. 1 k Nếu n chia hết cho số bình phương số nguyên tố, thì tìm được b ∈ N , UCLN (b, n) = 1 , n −1 sao cho b n−1 ≠ 1(mod n) , từ đây b 2 ≠ ±1(mod n) . Rõ ràng rằng, tồn tại α i ≥ 2 . Theo định α lý về phần dư trung hoa, có thể tìm được b ∈ N , b(mod pi ) - là căn nguyên thủy trong i Z p αi , còn khi j ≠ i, b ≡ 1(mod p α j ) . Nếu như b n−1 ≡ 1(mod n) , thì b n−1 ≡ 1(mod piα i ) , từ đây j i n − 1 ( piα i ) = piα i −1 ( pi − 1) , điều này là không thể bởi vì n-1 không chia hết cho pi . φ Bây giờ giả sử rằng n = p1 ... p k . Chúng ta tìm số b ∈ N , sao cho b(mod p1 ) -là căn nguyên thủy trong Z p , và b ≡ 1(mod p j ) khi j>1. Khi đó UCLN (b, n) = 1 và 1 b  b   b   b    =   ⋅ ⋅ ⋅   =   = −1  n   p1   pk   p1        n −1 n −1 Đồng dư thức b 2 ≡ −1(mod n) tương đương với b 2 ≡ −1(mod p j ) , với j=1,…,k. Bởi n −1 vì k ≥ 2 thì 1 ≡ b 2 ≡ −1(mod p 2 ) , là không thể. Như vậy số b tồn tại. Chúng ta xem 2 tập hợp :  n −1 a  W1 = a | 1 ≤ a ≤ n − 1,UCLN ( a, n) = 1, a 2 ≡  (mod n) ,  n   n−1 a  W2 = a | 1 ≤ a ≤ n − 1,UCLN (a, n) = 1, a 2 ≠  (mod n) ,  n 
 a1a 2   a1  a2  Nếu như a1 ∈W1 , a2 ∈W2 , thì a1a 2 ∈W2 , bởi vì   =    . Cho nên đối với số  n   n  n  a ∈ W1 , thặng dư không âm nhỏ nhất của ba (mod n) thuộc W2 . Dẫn đến , | W2 |≥| W1 | , từ đây rút ra điều khẳng định của định lý. Giải thuật kiểm tra Solovay-Strasen Đầu vào: n: là số tự nhiên lẻ Đầu ra: FALSE nếu n là hợp số, nếu không TRUE 1. Chọn a ngẫu nhiên trong khoảng[1,n-1] a 2. Tính ký hiệu Jacobi J=   n 3. Tính x =a(n − 1) / 2(mod n) 4. Nếu J ≠ x thì trả về FALSE nếu khác trả về TRUE. Gọi A là biến cố "Số nguyên lẻ n là hợp số"; B là biến cố: "Thuật toán Solova- 1 Strassen trả lời TRUE". Xác suất điều kiện P(B|A) ≤ . 2 Tương tự phép thử Miller-Rabin tính được xác suất sai của phép thử Solova-Strasen là P(B | A ) ⋅ P ( A) P ( B | A) ⋅ P ( A) P( A | B) = = . P( B) P ( B | A) ⋅ P ( A) + P( B | A) ⋅ P ( A) P ( B | A) ⋅ (ln n − 2) P( A / B) ≈ . P ( B | A) ⋅ (ln n − 2) + 2 3.8 Kiểm tra tính nguyên tố của số bằng thuật toán đa thức Định lý 3.14 Cho p là số lẻ, a ∈ Z , UCLN (a, p) = 1 . Số p là số nguyên tố khi và chỉ khi ( x − a ) p ≡ x p − a(mod p ) (3.3) (đồng dư thức 3.3 nghĩa là hệ số của đa thức so sánh với modulo p) Chứng minh: Rõ ràng ta có  p p −1 ( x − a ) − ( x − a ) = ∑  x i (− a ) p −i + a − a p (3.4) p p   i =1  i 
Nếu như p là số nguyên tố, thì biểu thức (1.3) dẫn đến từ (1.4), bởi vì khi 1 ≤ i ≤ p − 1  p số   chia hết cho p. i    Giả sử biểu thức (3.3) thỏa mãn, và giả sử p là hợp số. Chúng ta sẽ tìm được số nguyên tố q và số tự nhiên k sao cho q k || p , điều kiện q < p . Rõ ràng rằng q k không  p p ( p − 1)...( p − q + 1) chia hết cho   = q  , và cho nên hệ số x q trong (3.4) không chia hết   q! cho p, như thế mâu thuẫn với sự thỏa mãn của biểu thức (3.3). Định lý đã đ ược chứng minh. Chúng ta ký hiệu P(m) là ước số nguyên tố lớn nhất của số tự nhiên m. Bổ đề 3.3 Cho p và r là 2 số nguyên tố khác nhau. Khi đó 1) Đối với từng t ∈ N , nhóm G(p t ,*) là nhóm cyclic 2) Đối với từng đa thức f ( x ) ∈ Z [ x ] đẳng thức sau đây đúng f ( x) p ≡ f ( x p )(mod p ) . 3) Nếu như h( x) ∈ Z [ x ], h( x) | x − 1, m1 , m2 ∈ Z ≥0 , m ≡ mr (mod r ) , thì r x m ≡ x mr (mod h( x)) . xr −1 4)Nếu như Ord r ( p ) bậc của p (mod r), thì trong Z p [ x ] đa thức được phân chia x −1 ra các đa thức bất khả quy, mà mỗi trong chúng nó có mũ là Ord r ( p ) . Bổ đề 3.4 Tồn tại hằng số dương c0 và số tự nhiên n0 sao cho đối với các số x ≥ n0 bất đẳng thức sau đúng { } # p | p ≤ x, P( p − 1) > x 2 / 3 ≥ c0 log x . Bổ đề 3.5 Với mọi số m ≥ 2 , chúng ta có bất đẳng thức sau m 8m , ≤ π ( m) ≤ 6 log 2 m log 2 m ở đây π (m) là một số nguyên tố p ≤ m , mà P( p − 1) > m 2 / 3 . Thuật toán kiểm tra tính nguyên tố của số tự nhiên lẻ n>1 Bước 1. Nếu như n có dạng a b , ở đây a, b ∈ N , b ≥ 2 , thì thông báo, n là hợp số và thuật toán kết thúc. Bước 2. r:=2
Bước 3. Đối với giá trị hiện tại của r thực hiện bước 4-8 Bước 4. Nếu như r1, thì n là hợp số, thuật toán kết thúc. Bước 5. Nếu r là số nguyên tố, thì hoàn thành các bước 6-7, ngược lại thì chuyển đến bước 8 Bước 6. Tìm số q – là ước số nguyên tố lớn nhất của r-1 r −1 Bước 7. Nếu q ≥ 4 r log 2 n và n q ≠ 1(mod r ) , chuyển đến bước 9 với giá trị r đã cho Bước 8. r:=r+1. Nếu như r ≥ n , thì thông báo n là số nguyên tố, và thuật toán kết thúc. Ngược lại thì lặp lại bước 3. Bước 9. [ ] 1) Nếu như n − 1 ≤ 2 r log 2 n , thì đối với tất cả các số a từ khoảng r < a ≤ n − 1 thì kiểm tra điều kiện UCLN (a, n) = 1 . [ ] 2) Nếu như n − 1 > 2 r log 2 n , thì đối với tất cả a từ đoạn 1 ≤ a ≤ 2 r log 2 n [ ] kiểm tra biểu thức ( x − a ) n ≡ x n − a(mod x r − 1) trong Z n [ x] . Nếu như đối với một số giá trị a trong trường hợp 1 hoàn thành bất đẳng thức UCLN(a,n)>1, hoặc trong trường hợp 2 đẳng thức theo modulo x r − 1 không đúng thì n là hợp số và thuật toán dừng. Bước 10. Nếu như chúng ta đi đên bước này thì n là số nguyên tố. Kết thúc thuật toán .