SỐ GIẢ NGUYÊN TỐ
Giả sử b là một số nguyên dương. Nếu n là hợp số nguyên dương và b^n ≡ 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: b^(n-1) ≡ 1 (mod n).
Nói chung trong bất kì một khoảng nào thì số giả nguyên tố ít hơn rất nhiều so với số nguyên tố. Như vậy các số thoả mãn định lí Fermat bé 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.
KIỂM TRA MILLER VÀ SỐ GIẢ NGUYÊN TỐ MẠNH ( Thuật toán Rabin - Miller)
Giả sử n là số nguyên dương lẻ, n-1 = 2^s * t, 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 b^t ≡ 1 (mod n) hoặc b^(t * 2^j) ≡ -1 (mod n) với j nào đó (0 ≤ j ≤ s-1).
Số nguyên n được gọi là 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ác số giả nguyên tố.
Từ đó ta có thể dùng kiểm tra Miller để kiểm tra tính nguyên tố của những số không lớn lắm. 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ự vậy, số 1373653, là số giả nguyên tố mạnh lẻ bé nhất cơ sở 2 và 3. Đối với cơ sở 2, 3 và 5 thì số giả nguyên tố mạnh lẻ bé nhất là 25326001. Trong trường hợp cơ sở 2, 3, 5, 7 thì số đó là 3215031751.
Cách làm trên chỉ có thể dùng để kiểm tra những số nguyên tố không lớn lắm, còn đối với các số lớn thì chúng ta sẽ dùng thuật toán xác suất dựa theo định lí sau.
Nếu n là một hợp số dương lẻ thì tồn tại không quá (n-1)/4 cơ sở b (0<b<n), sao cho n trải qua được kiểm tra Miller đối với các cơ sở đó.
Từ định lí này suy ra rằng, nếu số b được chọn ngẫu nhiên trong khoảng (0 < b < n) thì n kiểm 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 được kiểm tra Miller đối với k cơ sở đó là 1 - 1/(4^k). Khi k đủ lớn (ví dụ k = 20) thì xác suất đó là quá nhỏ, do đó nếu n có thể trải qua kiểm tra Miller với 20 cơ sở ngẫu nhiên thì có thể tin “hầu chắc chắn” n là số nguyên tố.
Từ đó ta có thuật toán sau. ( thuật toán Rabin - Miller)
Cho N >2 lẻ thuật toán sau đây xác định rằng N là hợp số, hoặc đưa ra thông báo N là số nguyên tố với xác suất lớn hơn 1 – 1/(4^20) (=0.99999999999909050529822707176208).
Step1: (Xuất phát) Đặt q = N-1, t = 0, và nếu q chẵn thì q := q/2, t:= t+1 (lặp cho đến khi q lẻ, do đó ta có N = 2^t q, với q lẻ). Sau đó đặt c = 20.
Step2: (Chọn a mới). Chọn ngẫu nhiên số a trong khoảng 1<a<N. Đặt e:= 0, b := a^q mod N. Nếu b = 1 chuyển sang Step4.
Step3: (bình phương) Nếu b ≠ ±1 (mod N) và e < t-2 thì ta đặt b:= b^2 mod N, e := e+1. Nếu b ≠ N - 1, in ra thông báo “N là hợp số” và kết thúc thuật toán.
Step4: Đặt c:= c-1. Nếu c> 0 thì, chuyển sang Step2. Nếu c = 0 thì đưa ra thông báo “N là số nguyên tố”.
Người ta đã chứng minh được rằng thuật toán Rabin_Miller hết O(k * (log n)^3) phép tính bit.
Cũng có một số thuật toán kiểm tra tính nguyên tố của một số theo xác suất khác nữa, trong đó có thuất toán Euler. với độ phức tạp thời gian cũng như trên nhưng tính chính xác thì kém hơn 1 – 1/(2^k) tất nhiên là không đáng kể. Nhưng để hiểu được thuật toán này thì cần phải có một kiến thức toán về thặng dư khá vững nên tôi xin phép không đề cập đến ở đây.
Cai này cài đặt rất dễ, kiểm tra số nguyên tố cỡ vài nghìn chữ số chỉ mất vài giây.