Bỏ qua để đến nội dung

Miller-Rabin và Pollard rho

Mức độ: Chuyên sâu

Bài Số nguyên tố kiểm tra n bằng cách thử chia cho các số đến n\sqrt{n}. Với n đến 1012 là khoảng 106 phép chia. Nhưng đề hay cho n đến 1018, khi đó n\sqrt{n} 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).

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ó.

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.

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 ≤ n\sqrt{n}). 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 p\sqrt{p} 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ướcRùa xThỏ yƯCLN(|x - y|, 8051)
15261
22674741
367787197

Đượ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 random
from 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]

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 p\sqrt{p} 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.

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ậ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.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

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ậpIn ra
6
2 15 97 561 1000000007 999999866000004473
3

Kiểm tra: nhập

8
1 4 999999999999999989 1105 131071 524287 8191 10000000019
Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1000000000039

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

999999999989

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

753

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1000000007 1000000009

Hướng dẫn giải chi tiết: liên hệ tác giả.

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”

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.

Xem đáp số

71 839 1471 6857

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

6857

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

6720

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

544144210

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

591194251200

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

223092870

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

9 18

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

7436429

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

11 999999999989

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

6720

Hướng dẫn giải chi tiết: liên hệ tác giả.

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.

Xem đáp số

256

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy