Родилась интересная идея в рамках "поделки на коленке", которой спешу поделиться.

Есть много алгоритмов факторизации (например, описанные на e-maxx), но, кажется, что всем им можно понаходить нехорошие контрпримеры в данном диапазоне (по крайней мере, они известные стандартные, и можно ждать подобного, хотя в детали не вдавался - может быть, просветят).

Пусть дано N ≤ 10¹⁸. Для начала, проверим маленькие делители до 10⁷ (решето Эратосфена и деления должны уложиться в таком диапазоне). Также проверим, что число не точный квадрат.

Теперь, число либо простое, либо имеет два простых делителя не больше 10¹¹. Попробуем найти функцию Эйлера от числа . Очевидно, что она лежит в диапазоне

Зададимся некоторым a. Предпросчитаем aⁿ для n ≤ 10⁷. Если у числа окажется маленький порядок, то просто запомним этот порядок. Иначе с шагом 10⁷ пройдем диапазон значений pq - 10¹¹ - 10⁷ ≤ n ≤ pq - 1 + 10⁷ и обнаружим решения aⁿ = 1, в которых одно из n будет являться искомым значением функции . Удостовериться, что данное значение является искомым можно просто решив квадратное уравнение и проверив один из получившихся делителей.

Будем проверять a начиная с двух и так далее. Единственной особенной ситуацией может быть то, что много чисел в начале будут иметь маленький порядок. Будем попутно считать НОК всех получившихся порядков, и, как только этот НОК будет больше 10⁷ проведем процедуру проверки на с шагом НОК.

Не реализовывал, хотя выглядит верным. Discuss.

Upd 1. Сортировать 10⁷ чисел после предпросчета может быть долго. Быть может, надо понизить эту константу до 10⁶ (10⁵ проверок нас вполне устроит). Кроме того, можно использовать тот факт, что делится на 4 и наш шаг делится на 4 и сохранить только 10⁷ / 4 шагов предпросчета.

Upd 2. Итого к реализации: gcd, быстрое возведение в степень, решето Эратосфена, решение квадратного уравнения, точное извлечение корня из числа до 10^18. Не так много и совсем стандартно.