Người viết: Nguyễn Anh Bảo - Đại học Bách Khoa Hà Nội
Reviewer:
Trong bài viết này, chúng ta sẽ cùng tìm hiểu một số thuật toán và phương pháp kiểm tra một số tự nhiên bất kì có là số nguyên tố hay không.
Một số tự nhiên được gọi là số nguyên tố khi và chỉ khi có đúng ước dương là và chính nó.
Ví dụ: là các số nguyên tố. không là số nguyên tố.
Trong bài viết này, chúng ta sẽ tập trung vào việc kiểm tra một số nguyên dương có phải số nguyên tố hay không. Để kiểm tra tính nguyên tố của nhiều số nguyên trên một đoạn , bạn đọc có thể tham khảo bài viết Sàng nguyên tố.
Cách đơn giản nhất để kiểm tra tính nguyên tố của số tự nhiên là trực tiếp sử dụng định nghĩa số nguyên tố:
Số tự nhiên là số nguyên tố khi và chỉ khi không chia hết cho các số tự nhiên .
Ta có thể cài đặt như sau:
bool primeCheck(int n)
{
if (n < 2)
return false;
for (int i = 2; i < n; ++i)
if (n % i == 0)
return false;
return true;
}
Độ phức tạp thuật toán: .
Để tối ưu thuật toán trên, nhận xét rằng nếu có một ước sao cho thì cũng là ước của và có . Suy ra nếu không chia hết cho các số tự nhiên lớn hơn và không vượt quá thì cũng không chia hết cho các số tự nhiên lớn hơn . Từ đó, thay vì xét tính chia hết của cho ta chỉ cần xét .
Cài đặt thuật toán:
bool primeCheck(int n)
{
if (n < 2)
return false;
for (int i = 2; i * i <= n; ++i)
if (n % i == 0)
return false;
return true;
}
Độ phức tạp thuật toán: .
Ta có thể mở rộng thuật toán trên thành thuật toán phân tích một số nguyên dương ra thừa số nguyên tố:
void primeFactorization(int n)
{
for (int i = 2; i * i <= n; ++i)
while (n % i == 0)
{
n /= i;
cout << i << ' ';
}
if (n > 1)
cout << n;
}
Để ý nếu số nguyên tố lẻ thì không chia hết cho một số chẵn bất kì. Do đó nếu , ta chỉ cần xét các số lẻ thuộc đoạn . Tương tự, nếu thì ta chỉ cần xét là các số không chia hết cho . Từ hai nhận xét trên, nếu thì ta chỉ cần xét các số sao cho chia dư hoặc .
bool primeCheck(int n)
{
if (n == 2 || n == 3)
return true;
if (n < 3 || n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
Chú ý: Có thể sử dụng nhiều số nguyên tố đầu tiên để tối ưu thuật toán hơn. Về lý thuyết, nếu là số số nguyên tố được dùng càng lớn thì vòng lặp chạy càng nhanh. Tuy nhiên, với , độ phức tạp vòng lặp for là . Và kể cả với thì độ phức tạp thuật của vòng lặp for vẫn là .
Do đó thuật toán này có thể không đủ nhanh để giải quyết giới hạn , hoặc nhưng phải kiểm tra số trở lên. Để giải quyết các bài toán có giới hạn lớn như thế, ta phải sử dụng đến các phương pháp xác suất.
Theo định lí Fermat nhỏ, nếu là một số nguyên tố thì với mọi số nguyên thỏa mãn , ta có:
Từ định lý Fermat ta có ý tưởng kiểm tra tính nguyên tố của số nguyên dương như sau:
Chú ý: Phần in đậm của phép thử nghĩa là tồn tại các giá trị của và sao cho là hợp số và . Ví dụ, nếu và thì . Trong trường hợp này, được gọi là số giả nguyên tố cơ sở , hoặc số nguyên tố xác suất cơ sở .
Về lý thuyết, nếu ta kiểm tra đẳng thức Fermat với mọi số , ta có thể kết luận chắc chắn tính nguyên tố của . Tuy nhiên, việc kiểm tra đẳng thức với mọi sẽ phức tạp hơn cả thuật toán ngây thơ. Do đó, phép thử Fermat sẽ thực hiện một số lần thử với các số được lấy ngẫu nhiên. Trong các bài toán lập trình thi đấu, phép thử vẫn có độ chính xác đủ tốt.
Ta có thể cài đặt kết quả của phép tính bằng lũy thừa nhị phân.
// Tính a^k (mod n)
int binaryPower(long long a, int k, int n)
{
a = a % n;
long long res = 1;
while (k)
{
if (k & 1)
res = (res * a) % n;
a = (a * a) % n;
k /= 2;
}
return res;
}
Cài đặt phép thử Fermat:
bool isProbablyPrime(int n)
{
if (n < 7)
return n == 2 || n == 3 || n == 5;
static const int repeatNum = 5;
for (int i = 0; i < repeatNum; ++i)
{
int a = rand() % (n - 3) + 2;
if (binaryPower(a, n - 1, n) != 1)
return false;
}
return true;
}
Độ phức tạp phép thử là với là số cơ số được thử.
Do thuật toán binaryPower có sử dụng phép tính (a * a) % n nên nếu sẽ có thể bị tràn số. Phiên bản được trình bày ở trên xử lí . Để áp dụng thuật toán lũy thừa nhị phân với , bạn phải dùng kiểu số nguyên nếu ngôn ngữ lập trình cho phép. Nếu ngôn ngữ lập trình chỉ có loại số nguyên , bạn có thể tham khảo thuật toán được chỉnh sửa như sau:
// Tính a * b mod n
long long binaryMul(long long a, long long b, long long n)
{
a = a % n;
long long res = 0;
while (b)
{
if (b & 1)
res = (res + a) % n;
a = (2 * a) % n;
b /= 2;
}
return res;
}
// Tính a^b mod n
long long binaryPow(long long a, long long k, long long n)
{
a = a % n;
long long res = 1;
while (k)
{
if (k & 1)
res = binaryMul(res, a, n);
a = binaryMul(a, a, n) % n;
k /= 2;
}
return res;
}
Khi đó độ phức tạp thuật toán là .
Chú ý: Do không có tính chính xác tuyệt đối nên phép thử Fermat không phải là một thuật toán.
Tuy tốc độ cao và dễ cài đặt, vẫn có những trường hợp xác suất phép thử Fermat thất bại là rất cao. Ví dụ xét số . Số này có tính chất với mọi số nguyên mà thì . Do đó, trừ khi trong các lần thử ngẫu nhiên ta chọn được chia hết cho hoặc thì phép thử sẽ cho kết quả sai.
Các số có tính chất trên được gọi là số Carmichael.
Xét là một số Carmichael có ước nguyên tố, là số lần chọn cơ số (repeatNum). Nếu thì số nhỏ nhất là . Xác suất phép thử kết luận đúng với do đó bị chặn bởi . cho bởi bảng sau:
Từ bảng trên có thể thấy để có độ chính xác thì ta phải thử ít nhất lần, và có thể nhiều hơn. Trong khi nếu ta chỉ thử lần duy nhất thì xác suất phép thử kết luận sai là .
Với , số Carmichael nhỏ nhất có ước nguyên tố là . Tương tự, xét xác suất phép thử cho kết quả đúng với là số Carmichael dạng này bị chặn bởi . được cho bởi bảng sau:
Tức là kể cả ta có thử đến lần thì xác suất phép thử kết luận đúng vẫn không thể quá .
Một điều khá thú vị là các số Carmichael phân bố rất ít trong tập các số tự nhiên. Theo OEIS-A055553:
Do đó, các bạn có thể yên tâm khi sử dụng phép thử Fermat nếu test được sinh ngẫu nhiên, vì xác suất gặp số Carmichael rất thấp. Nếu test cố tình chọn số Carmichael thì phép thử không còn đáng tin cậy. Rất may là có những phép thử hiệu quả và chính xác hơn phép thử Fermat. Trong phần tiếp theo chúng ta sẽ cùng tìm hiểu thuật toán Rabin-Miller.
Thuật toán Rabin-Miller là phiên bản mở rộng và mạnh hơn của phép thử Fermat. Thuật toán dựa vào nhận xét sau:
Với mọi số nguyên dương , ta tìm được duy nhất hai số tự nhiên sao cho và lẻ.
Ví dụ:
Do đó, xét số , ta có thể phân tích thành , với là số lẻ.
Theo định lý nhỏ Fermat, nếu là số nguyên tố thì với mọi sao cho ta có:
Vì là số nguyên tố nên tồn tại ít nhất một trong các nhân tử của vế trái chia hết cho . Do đó, thay vì kiểm tra kết luận của định lý Fermat nhỏ, ta sẽ kiểm tra điều kiện sau:
Nếu cả hai điều kiện không được thỏa mãn thì chắc chắn là hợp số.
Nhưng nếu cả hai điều kiện được thỏa mãn thì có phải số nguyên tố không?
Câu trả lời là không. Ví dụ: với thì và .
Do đó, để áp dụng ý tưởng trên, ta có thể triển khai theo hai cách sau:
Để tăng tính chính xác của thuật toán ta có thể lặp lại bước kiểm tra với nhiều cơ số , giống như phép thử Fermat. Hơn thế nữa, chứng minh được nếu là hợp số, chỉ có số cơ số trong đoạn thỏa mãn một trong hai điều kiện.
Nghĩa là với hợp số bất kì, xác suất để thuật toán chứng minh được là hợp số sau lần kiểm tra đầu tiên là , lần thứ hai là , lần thứ ba là , lần thứ là . Có thể thấy độ chính xác của thuật toán Rabin-Miller cao hơn nhiều so với phép thử Fermat, và tất nhiên là đủ tốt cho các bài toán lập trình thi đấu.
Cài đặt thuật toán:
// Tính a^k mod n
long long binaryPower(long long a, long long k, long long n)
{
a = a % n;
long long res = 1;
while (k)
{
if (k & 1)
res = (res * a) % n;
a = (a * a) % n;
k /= 2;
}
return res;
}
// Kiểm tra điều kiện thuật toán với a cố định
bool test(long long a, long long n, long long k, long long m)
{
long long mod = binaryPower(a, m, n);
if (mod == 1 || mod == n - 1)
return true;
for (int l = 1; l < k; ++l)
{
mod = (mod * mod) % n;
if (mod == n - 1)
return true;
}
return false;
}
bool RabinMiller(long long n)
{
// Kiểm tra với các giá trị nhỏ
if (n == 2 || n == 3 || n == 5 || n == 7)
return true;
if (n < 11)
return false;
// Tính m và k
long long k = 0, m = n - 1;
while (m % 2 == 0)
{
m /= 2;
k++;
}
// Lặp lại bước kiểm tra với a ngẫu nhiên
const static int repeatTime = 3;
for (int i = 0; i < repeatTime; ++i)
{
long long a = rand() % (n - 3) + 2;
if (!test(a, n, k, m))
return false;
}
return true;
}
Độ phức tạp là .
Phép thử xác suất có thể trở thành thuật toán bằng cách thay vì xét ngẫu nhiên, ta sẽ xét tất cả bị chặn bởi một hàm theo . Miller chứng minh được nếu Định đề Riemann tổng quát (GRH) là đúng thì ta chỉ cần kiểm tra . Sau đó, Bach chứng minh được chỉ cần xét .
Với đủ lớn thì vẫn có rất nhiều giá trị cần kiểm tra. Nhưng người ta cũng chứng minh được rằng:
Do đó, ta có phiên bản thuật toán (độ chính xác ) của phép thử như sau:
bool MillerRabin(long long n)
{
static vector<int> checkSet = {2,3,5,7,11,13,17,19,23,29,31,37};
for (auto a : checkSet)
if (n == a)
return true;
if (n < 41)
return false;
long long k = 0, m = n - 1;
while (m % 2 == 0)
{
m /= 2;
k++;
}
for (auto a : checkSet)
if (!test(a, n, k, m))
return false;
return true;
}