Kiểm tra nguyên tố Miller-Rabin (nhân chứng cố định)

Với số lớn, thử chia quá chậm. Miller-Rabin là phép kiểm tra nhanh dựa trên định lý Fermat mở rộng.

Viết n - 1 = 2^r * d với d lẻ. Với nhân chứng a, n có thể là nguyên tố nếu a^d ≡ 1 (mod n) hoặc tồn tại 0 <= i < r sao cho a^(2^i * d) ≡ -1 (mod n).

Dùng bộ nhân chứng cố định {2,3,5,7,11,13,17,19,23,29,31,37} thì kết quả xác định đúng cho mọi n < 3.3 * 10^24.

Ví dụ

Input:
561
Output:
NO

561 = 3 x 11 x 17 là số Carmichael, không phải nguyên tố.