Miller-Rabin và Pollard rho
Bài Số nguyên tố kiểm tra n bằng cách thử chia cho các số đến . Với n đến 1012 là khoảng 106 phép chia. Nhưng đề hay cho n đến 1018, khi đó là 109 phép chia. Bài này trình bày hai thuật toán làm việc với số lớn như vậy:
- Miller-Rabin kiểm tra n có nguyên tố không trong khoảng vài trăm phép nhân.
- Pollard rho tìm một ước của hợp số n trong khoảng n1/4 bước (với n = 1018 là khoảng 3 × 104).
Định lý Fermat nhỏ và chỗ hở của nó
Phần tiêu đề “Định lý Fermat nhỏ và chỗ hở của nó”Theo định lý Fermat nhỏ, nếu p nguyên tố và a không chia hết cho p thì ap - 1 chia p dư 1. Nên nếu tìm được a mà an - 1 chia n không dư 1 thì n chắc chắn là hợp số. Ví dụ n = 91: 290 chia 91 dư 64, vậy 91 là hợp số (91 = 7 × 13), dù chưa tìm ra ước nào.
Chiều ngược lại thì sai: có hợp số vẫn cho an - 1 dư 1. Tệ nhất là các số Carmichael như 561 = 3 × 11 × 17: với mọi a nguyên tố cùng nhau với 561, a560 chia 561 dư 1. Kiểm tra Fermat không bao giờ phát hiện được nó.
Kiểm tra Miller-Rabin
Phần tiêu đề “Kiểm tra Miller-Rabin”Miller-Rabin dùng thêm một tính chất: với p nguyên tố, x2 chia p dư 1 chỉ khi x chia p dư 1 hoặc dư p - 1. Lý do: x2 - 1 = (x - 1)(x + 1) chia hết cho p nguyên tố thì p là ước của x - 1 hoặc của x + 1.
Viết n - 1 = d × 2s với d lẻ. Xét dãy ad, a2d, a4d, …, a2sd (theo modulo n), mỗi số là bình phương của số trước, số cuối là an - 1. Nếu n nguyên tố thì số cuối dư 1, và đi ngược từ cuối, lần đầu tiên dãy “trở thành 1” phải đi ra từ n - 1. Vậy với n nguyên tố, luôn có một trong hai:
- ad chia n dư 1, hoặc
- có một số trong dãy chia n dư n - 1 (trước số cuối).
Nếu cả hai đều không xảy ra thì n chắc chắn là hợp số, và a được gọi là nhân chứng.
Thử với n = 561, a = 2: n - 1 = 560 = 35 × 24. Dãy là 235 ≡ 263, rồi bình phương liên tiếp được 166, 67, 1. Dãy chạm 1 mà không đi qua 560, nên 2 là nhân chứng: 561 là hợp số. Kiểm tra Fermat thì bỏ sót vì 2560 ≡ 1.
Người ta đã kiểm chứng: với mọi n nhỏ hơn 3,3 × 1024, chỉ cần thử 12 cơ số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37; hợp số nào cũng có ít nhất một nhân chứng trong số đó. Vậy với n đến 1018, Miller-Rabin với 12 cơ số này luôn đúng, không phải “đúng với xác suất cao”.
Nhân không tràn số: n tới 1018 thì tích hai số dư có thể tới 1036, vượt long long. Trong C++,
nhân bằng kiểu 128 bit __int128 rồi mới lấy dư. Python tự xử lý số lớn.
Thuật toán Pollard rho
Phần tiêu đề “Thuật toán Pollard rho”Biết n là hợp số rồi, làm sao tìm một ước? Gọi p là ước nguyên tố nhỏ nhất của n (p ≤ ). Xét dãy
xk + 1 = (xk2 + c) mod n
Nhìn dãy này theo modulo p (ta không biết p, chỉ tưởng tượng): chỉ có p giá trị dư, nên dãy sớm muộn lặp lại và đi vòng tròn. Giống bài toán “trong lớp có bao nhiêu người thì có hai người trùng ngày sinh”, hai giá trị trùng nhau theo modulo p thường xuất hiện sau khoảng số hạng, tức là khoảng n1/4. Đường đi của dãy vào vòng lặp có hình chữ ρ (rho) của Hy Lạp, nên thuật toán mang tên này.
Khi xi và xj trùng nhau theo modulo p thì p là ước của xi - xj, nên ƯCLN(|xi - xj|, n) lớn hơn 1, cho ra một ước của n. Để tìm cặp trùng mà không lưu cả dãy, dùng hai con trỏ: “rùa” đi mỗi lần một bước, “thỏ” đi mỗi lần hai bước; khi cả hai đã vào vòng, thỏ sẽ đuổi kịp rùa.
Ví dụ n = 8051, x0 = 2, c = 1:
| Bước | Rùa x | Thỏ y | ƯCLN(|x - y|, 8051) |
|---|---|---|---|
| 1 | 5 | 26 | 1 |
| 2 | 26 | 7474 | 1 |
| 3 | 677 | 871 | 97 |
Được ước 97, và 8051 = 83 × 97.
Nếu ƯCLN bằng chính n (rùa và thỏ trùng nhau theo modulo n) thì thử lại với c khác. Để phân tích hết n: n nguyên tố (kiểm tra bằng Miller-Rabin) thì xong; ngược lại tìm một ước d bằng Pollard rho rồi phân tích tiếp d và n ÷ d.
import randomfrom math import gcd
CO_SO = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
def la_nguyen_to(n): """Miller-Rabin với 12 cơ số: luôn đúng với n nhỏ hơn 3,3 × 10^24.""" if n < 2: return False for p in CO_SO: if n % p == 0: return n == p d, s = n - 1, 0 while d % 2 == 0: d //= 2 s += 1 for a in CO_SO: x = pow(a, d, n) if x == 1 or x == n - 1: continue for _ in range(s - 1): x = x * x % n if x == n - 1: break else: return False # a là nhân chứng: n là hợp số return True
def pollard_rho(n): """Một ước thật sự (khác 1 và n) của hợp số n.""" if n % 2 == 0: return 2 while True: c = random.randrange(1, n) rua = tho = random.randrange(2, n) uoc = 1 while uoc == 1: rua = (rua * rua + c) % n tho = (tho * tho + c) % n tho = (tho * tho + c) % n uoc = gcd(abs(rua - tho), n) if uoc != n: # uoc == n thì thử lại với c khác return uoc
def phan_tich(n): """Các thừa số nguyên tố của n (có lặp), sắp tăng dần.""" if n == 1: return [] if la_nguyen_to(n): return [n] d = pollard_rho(n) return sorted(phan_tich(d) + phan_tich(n // d))
print(phan_tich(999999999999999989)) # số nguyên tố: [999999999999999989]print(phan_tich(1000000016000000063)) # [1000000007, 1000000009]#include <iostream>#include <vector>#include <random>#include <algorithm>using namespace std;typedef unsigned long long u64;
u64 nhanMod(u64 a, u64 b, u64 m) { return (unsigned __int128)a * b % m; } // không tràn số
u64 luyThuaMod(u64 a, u64 e, u64 m) { u64 ketQua = 1; a %= m; for (; e > 0; e >>= 1, a = nhanMod(a, a, m)) if (e & 1) ketQua = nhanMod(ketQua, a, m); return ketQua;}
const u64 CO_SO[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
bool laNguyenTo(u64 n) { if (n < 2) return false; for (u64 p : CO_SO) if (n % p == 0) return n == p; u64 d = n - 1; int s = 0; while (d % 2 == 0) { d /= 2; s++; } for (u64 a : CO_SO) { u64 x = luyThuaMod(a, d, n); if (x == 1 || x == n - 1) continue; bool gapNTru1 = false; for (int r = 1; r < s && !gapNTru1; r++) { x = nhanMod(x, x, n); if (x == n - 1) gapNTru1 = true; } if (!gapNTru1) return false; // a là nhân chứng: n là hợp số } return true;}
mt19937_64 ngauNhien(12345);
u64 ucln(u64 a, u64 b) { while (b) { u64 t = a % b; a = b; b = t; } return a; }
u64 pollardRho(u64 n) { // một ước thật sự của hợp số n if (n % 2 == 0) return 2; while (true) { u64 c = ngauNhien() % (n - 1) + 1, rua = ngauNhien() % (n - 2) + 2, tho = rua, uoc = 1; while (uoc == 1) { rua = (nhanMod(rua, rua, n) + c) % n; tho = (nhanMod(tho, tho, n) + c) % n; tho = (nhanMod(tho, tho, n) + c) % n; uoc = ucln(rua > tho ? rua - tho : tho - rua, n); } if (uoc != n) return uoc; // uoc == n thì thử lại với c khác }}
void phanTich(u64 n, vector<u64> &thuaSo) { if (n == 1) return; if (laNguyenTo(n)) { thuaSo.push_back(n); return; } u64 d = pollardRho(n); phanTich(d, thuaSo); phanTich(n / d, thuaSo);}
int main() { vector<u64> thuaSo; phanTich(1000000016000000063ULL, thuaSo); sort(thuaSo.begin(), thuaSo.end()); for (u64 p : thuaSo) cout << p << ' '; // 1000000007 1000000009 cout << '\n'; return 0;}Số bước: Miller-Rabin thử 12 cơ số, mỗi cơ số khoảng 2 log2n phép nhân, tổng khoảng 1500 phép nhân với n = 1018, so với 109 phép chia của cách thử từng số. Pollard rho tìm ước p nhỏ nhất trong khoảng vòng lặp, và n có không quá 60 thừa số nguyên tố (vì 260 lớn hơn 1018), nên phân tích hết n chỉ cần khoảng vài lần 104 vòng lặp.
Có thừa số nguyên tố rồi, các đại lượng ở bài Hàm nhân tính như số ước, tổng ước, φ(n), μ(n) đều tính được cho n đến 1018.
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 22 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Kiểm tra số nguyên tố lớn
Phần tiêu đề “Nhóm 1. Kiểm tra số nguyên tố lớn”Bài 1. Kiểm tra số nguyên tố đến 1018
Phần tiêu đề “Bài 1. Kiểm tra số nguyên tố đến 1018”Nhập số nguyên n (1 ≤ n ≤ 1018). In ra YES nếu n là số nguyên tố, ngược lại in NO.
Ví dụ: nhập 999999999999999989 thì in ra YES.
Kiểm tra: nhập 999999866000004473.
Bài 2. Đếm số nguyên tố trong dãy
Phần tiêu đề “Bài 2. Đếm số nguyên tố trong dãy”Dòng đầu có m (1 ≤ m ≤ 104), dòng thứ hai có m số nguyên dương, mỗi số không quá 1018. In ra số lượng số nguyên tố trong dãy.
Ví dụ:
| Nhập | In ra |
|---|---|
62 15 97 561 1000000007 999999866000004473 | 3 |
Kiểm tra: nhập
81 4 999999999999999989 1105 131071 524287 8191 10000000019Bài 3. Số nguyên tố tiếp theo
Phần tiêu đề “Bài 3. Số nguyên tố tiếp theo”Nhập n (1 ≤ n ≤ 1018). In ra số nguyên tố nhỏ nhất lớn hơn hoặc bằng n.
Ví dụ: nhập 90 thì in ra 97.
Kiểm tra: nhập 1000000000000.
Bài 4. Số nguyên tố liền trước
Phần tiêu đề “Bài 4. Số nguyên tố liền trước”Nhập n (2 ≤ n ≤ 1018). In ra số nguyên tố lớn nhất nhỏ hơn hoặc bằng n.
Ví dụ: nhập 100 thì in ra 97.
Kiểm tra: nhập 1000000000000.
Bài 5. Số nguyên tố trong đoạn lớn
Phần tiêu đề “Bài 5. Số nguyên tố trong đoạn lớn”Nhập L, R (1 ≤ L ≤ R ≤ 1018, R - L ≤ 104). In ra số lượng số nguyên tố trong đoạn [L, R].
Ví dụ: nhập 1 100 thì in ra 25.
Kiểm tra: nhập 1000000 1010000.
Bài 6. Cặp số nguyên tố sinh đôi
Phần tiêu đề “Bài 6. Cặp số nguyên tố sinh đôi”Hai số nguyên tố p, p + 2 gọi là cặp sinh đôi. Nhập n (1 ≤ n ≤ 1015). In ra cặp sinh đôi đầu tiên có p ≥ n.
Ví dụ: nhập 20 thì in ra 29 31.
Kiểm tra: nhập 1000000000.
Nhóm 2. Phân tích thừa số với Pollard rho
Phần tiêu đề “Nhóm 2. Phân tích thừa số với Pollard rho”Bài 7. Phân tích thừa số nguyên tố
Phần tiêu đề “Bài 7. Phân tích thừa số nguyên tố”Nhập n (2 ≤ n ≤ 1018). In ra các thừa số nguyên tố của n theo thứ tự không giảm (thừa số lặp lại bao nhiêu lần thì in bấy nhiêu lần).
Ví dụ: nhập 8051 thì in ra 83 97.
Kiểm tra: nhập 600851475143.
Bài 8. Ước nguyên tố lớn nhất
Phần tiêu đề “Bài 8. Ước nguyên tố lớn nhất”Nhập n (2 ≤ n ≤ 1018). In ra ước nguyên tố lớn nhất của n.
Ví dụ: nhập 13195 thì in ra 29.
Kiểm tra: nhập 600851475143.
Bài 9. Số ước của n lớn
Phần tiêu đề “Bài 9. Số ước của n lớn”Nhập n (1 ≤ n ≤ 1018). In ra số ước nguyên dương của n.
Ví dụ: nhập 360 thì in ra 24.
Kiểm tra: nhập 963761198400.
Bài 10. Tổng các ước theo modulo
Phần tiêu đề “Bài 10. Tổng các ước theo modulo”Nhập n (1 ≤ n ≤ 1018). In ra tổng các ước nguyên dương của n chia lấy dư 109 + 7.
Ví dụ: nhập 12 thì in ra 28.
Kiểm tra: nhập 600851475143.
Bài 11. Hàm Euler với n lớn
Phần tiêu đề “Bài 11. Hàm Euler với n lớn”Nhập n (1 ≤ n ≤ 1018). In ra φ(n): số các số từ 1 đến n nguyên tố cùng nhau với n.
Ví dụ: nhập 36 thì in ra 12.
Kiểm tra: nhập 600851475143.
Bài 12. Tích của hai số nguyên tố
Phần tiêu đề “Bài 12. Tích của hai số nguyên tố”Nhập n (1 ≤ n ≤ 1018). In ra YES nếu n bằng tích của đúng hai số nguyên tố (có thể bằng nhau), ngược lại in NO.
Ví dụ: nhập 49 thì in ra YES.
Kiểm tra: nhập 999999999999.
Nhóm 3. Hàm số học với n lớn
Phần tiêu đề “Nhóm 3. Hàm số học với n lớn”Bài 13. Hàm Möbius với n lớn
Phần tiêu đề “Bài 13. Hàm Möbius với n lớn”Nhập n (1 ≤ n ≤ 1018). In ra μ(n): bằng 0 nếu n chia hết cho bình phương của một số nguyên tố, ngược lại bằng 1 nếu n có số chẵn ước nguyên tố, -1 nếu có số lẻ ước nguyên tố (μ(1) = 1).
Ví dụ: nhập 30 thì in ra -1.
Kiểm tra: nhập 600851475143.
Bài 14. Tích các ước nguyên tố khác nhau
Phần tiêu đề “Bài 14. Tích các ước nguyên tố khác nhau”Nhập n (1 ≤ n ≤ 1018). In ra tích các ước nguyên tố khác nhau của n (với n = 1 in ra 1).
Ví dụ: nhập 360 thì in ra 30.
Kiểm tra: nhập 963761198400.
Bài 15. Đếm ước nguyên tố
Phần tiêu đề “Bài 15. Đếm ước nguyên tố”Nhập n (1 ≤ n ≤ 1018). In ra hai số: số ước nguyên tố khác nhau của n, và tổng các số mũ trong phân tích thừa số nguyên tố của n.
Ví dụ: nhập 360 thì in ra 3 6.
Kiểm tra: nhập 963761198400.
Bài 16. Lũy thừa của một số nguyên tố
Phần tiêu đề “Bài 16. Lũy thừa của một số nguyên tố”Nhập n (2 ≤ n ≤ 1018). Nếu n = pk với p nguyên tố và k ≥ 1, in ra p và k; ngược lại in NO.
Ví dụ: nhập 243 thì in ra 3 5.
Kiểm tra: nhập 10000000000.
Bài 17. Nhân thêm để thành số chính phương
Phần tiêu đề “Bài 17. Nhân thêm để thành số chính phương”Nhập n (1 ≤ n ≤ 1018). In ra số nguyên dương k nhỏ nhất để n × k là số chính phương.
Ví dụ: nhập 18 thì in ra 2.
Kiểm tra: nhập 963761198400.
Nhóm 4. Vận dụng
Phần tiêu đề “Nhóm 4. Vận dụng”Bài 18. Số Carmichael
Phần tiêu đề “Bài 18. Số Carmichael”Hợp số n là số Carmichael nếu với mọi a nguyên tố cùng nhau với n, an - 1 chia n dư 1. Theo tiêu chuẩn Korselt, hợp số n là số Carmichael khi và chỉ khi n không chia hết cho bình phương số nguyên tố nào và với mọi ước nguyên tố p của n, n - 1 chia hết cho p - 1. Nhập n (1 ≤ n ≤ 1018), in YES nếu n là số Carmichael, ngược lại in NO.
Ví dụ: nhập 561 thì in ra YES.
Kiểm tra: nhập 41041.
Bài 19. Số giả nguyên tố cơ sở 2
Phần tiêu đề “Bài 19. Số giả nguyên tố cơ sở 2”Hợp số n gọi là giả nguyên tố cơ sở 2 nếu 2n - 1 chia n dư 1 (lọt qua kiểm tra Fermat với a = 2). Nhập n (1 ≤ n ≤ 1018), in YES nếu n là giả nguyên tố cơ sở 2, ngược lại in NO.
Ví dụ: nhập 341 thì in ra YES.
Kiểm tra: nhập 4369.
Bài 20. Tách thành tổng hai số nguyên tố
Phần tiêu đề “Bài 20. Tách thành tổng hai số nguyên tố”Nhập số chẵn n (4 ≤ n ≤ 1018). In ra hai số nguyên tố p ≤ q với p + q = n, chọn p nhỏ nhất có thể (giả thuyết Goldbach, đã được kiểm chứng trong phạm vi này, bảo đảm luôn có cách).
Ví dụ: nhập 100 thì in ra 3 97.
Kiểm tra: nhập 1000000000000.
Bài 21. Số ước chung của hai số lớn
Phần tiêu đề “Bài 21. Số ước chung của hai số lớn”Nhập a, b (1 ≤ a, b ≤ 1018). In ra số nguyên dương là ước của cả a và b.
Ví dụ: nhập 360 84 thì in ra 6.
Kiểm tra: nhập 963761198400 897612484786617600.
Bài 22. Tách thành hai thừa số nguyên tố cùng nhau
Phần tiêu đề “Bài 22. Tách thành hai thừa số nguyên tố cùng nhau”Nhập n (1 ≤ n ≤ 1018). Đếm số cặp có thứ tự (x, y) gồm hai số nguyên dương với x × y = n và ƯCLN(x, y) = 1.
Ví dụ: nhập 12 thì in ra 4.
Kiểm tra: nhập 9699690.