Реально ли проверить на простоту 72-значное число?

[Гость]

Реально ли проверить на простоту 72-значное число? Например, такое: 555555555555555555555555544444444444444444444444433333333333333333333333

[admin]

Да, это совершенно тривиально. Важно не путать две разные по сложности задачи: разложить число на множители трудно, а проверить его на простоту — легко. 72 знака для теста на простоту — это очень мало.

Ваше число (25 пятёрок, 24 четвёрки, 23 тройки) оказывается простым.

Как это проверяется:

1. Тест Миллера—Рабина / BPSW даёт ответ практически мгновенно — у меня получилось около 0,4 миллисекунды. Формально это вероятностный тест (BPSW проверен полным перебором лишь до 2^64), но при нескольких десятках случайных баз вероятность ошибки исчезающе мала.

2. Строгое доказательство простоты: APR-CL или ECPP (например, программа Primo). Для 72 знаков сертификат строится меньше чем за секунду. Современный ECPP справляется с числами в десятки тысяч знаков.

На практике это одна строка:

Python (sympy): isprime(n)
PARI/GP: isprime(n) — с флагом даёт строгое доказательство
Wolfram Alpha: PrimeQ[n]

Для сравнения: разложить 72-значное число на множители тоже реально (решето числового поля берёт примерно до 250 знаков), но это уже минуты-часы работы, а не микросекунды.