Кратко и по делу — три варианта для числа порядка $10^{12}$:
1) Пробное деление (с простыми делителями)
- Точность: детерминировано — даст ответ и (при желании) факторизацию.
- Сложность: нужно делить до $\sqrt{n}$. Для $n\approx 10^{12}$ имеем $\sqrt{n}=10^6$ и число простых до этой границы $\pi (10^6)\approx 78498$. То есть ~$7.8\cdot 10^4$ делений по простым — очень дешёво на современных CPU.
- Практические ограничения: нужно сгенерировать простые до $\sqrt{n}$ (решето) или держать список; память и время для этого малы (решето до $10^6$ — порядка мегабайтов и миллисекунд). Удобно, если нужен фактор числа.
2) Решето (Эратосфена / сегментированное) — применимо, если проверяются многие числа
- Точность: детерминировано в смысле получения списка простых для пробного деления.
- Сложность: создание решета до $\sqrt{n}$ — около $O(\sqrt{n}\log \log \sqrt{n})$; для $\sqrt{n}=10^6$ это тривиально.
- Практические ограничения: выгодно при массовой проверке чисел (сегментированное решето по диапазонам). Для одного числа лишний шаг по сравнению с прямым MR, но даёт факторизацию.
3) Тест Миллера–Рабина (MR)
- Точность: вероятностный, но для малых границ можно сделать детерминированным подбором баз. Для всех $n<3474749660383$ (≈$3.47\cdot 10^{12}$) достаточно тестировать базы $2,3,5,7,11,13$ — тогда MR даёт точный результат для $n\approx 10^{12}$.
- Сложность: для каждого базового основания требуется несколько модульных возведений в степень; практическая стоимость для $n\sim 10^{12}$ — доли миллисекунды. Ассимптотически: примерно $O(k\cdot {\log }^{3}n)$ битовых операций для $k$ баз (на практике быстро).
- Практические ограничения: нужно корректно реализовать безопасную модульную умножение (для 64-битных языков использовать 128-бит умножение или алгоритм умножения с редукцией). MR не даёт факторизацию, лишь прост/состав.
Резюме/рекомендация
- Для одиночного теста числа около $10^{12}$: самый быстрый и гарантированный способ — детерминированный MR с базами $\{2,3,5,7,11,13\}$.
- Если нужен фактор числа или вы проверяете много чисел: сгенерировать простые до $\sqrt{n}=10^6$ (решето) и делать пробное деление — также очень эффективно и детерминировано.
- Важно: следите за корректной modular multiplication (использовать 128‑бит или безопасные алгоритмы), иначе возможны ошибки при больших промежуточных произведениях.