Gennadiy Usov, совсем неинтересно. Очевидно, что если число - псевдопростое по Ферма по некоторому основанию, а Миллер-Рабин по этому же основанию говорит, что число составное - то это автоматически дает нам факторизацию. Только трудоемкость подбора какого такого основания превышает перебор делителей.

Или тут имелся ввиду p-1 - метод Полларда ?

Разных алгоритмов напридумывать можно. Будут ли они эффективными - вот вопрос.
Например, такой вариант: допустим, мы предполагаем что известное нам составное N - произведение ровно двух простых неизвестных сомножителей p и q (пытаемся факторизовать rsa-модуль).
Тогда pq = N = ((p+q)/2) ² - ((p-q)/2) ² и это дает нам ограничения на возможные остатки (p+q)/2 по простым модулям: ((p+q)/2) ² - N должно быть квадратичным вычетом.

С другой стороны, для произвольного a должно выполняться a ^(p-1)(q-1)/2 ≡ 1 mod N
Преобразуем это равенство: a ^(pq+1)/2 ≡ a ^(p+q)/2 mod N
Левую часть мы знаем. И нам нужно найти дискретный логарифм в правой части.
Тут можно использовать вариацию на тему метода больших и малых шагов . Большой шаг будет произведением некоторого набора маленьких простых чисел, а на возможные значения малых шагов у нас уже есть ограничение: ((p+q)/2) ² - N должно быть квадратичным вычетом по модулю каждого из этих маленьких простых.

Такой алгоритм должен неплохо работать до значений N порядка 2 ¹²⁸ .

Или вариация на тему квадратичных форм Шенкса - цепочка редукций фактически дает нам набор равенств:
b ₁ ² - a ₀ a ₁ = N
b ₂ ² - a ₁ a ₂ = N
b ₃ ² - a ₂ a ₃ = N
.....
b _n ² - a _n-1 a _n = N
При этом a ₀ = 1, а из первого цикла мы выходим, когда a _n оказывается квадратом.
И зачем нам нужен второй цикл, если в этот момент (b ₁ *b ₂ *...*b _n ) ² ≡ a ₀ *(a ₁ *a ₂ *...*a _n-1 ) ² *a _n mod N
Если a ₀ и a _n квадраты, имеем классическое равенство для факторизации x ² ≡ y ² mod N
Ну и соответственно начинать можно не только с a ₀ = 1, но и например с любого квадрата простого числа, найдя b ₁ как квадратный корень из N по модулю квадрата этого простого (тут есть алгоритм Тонелли — Шенкса ).

Так тут две эквивалентные формулы
a ^{(pq+1)/2 - (p+q)/2} ≡ 1 mod N
вот тут ваша единица

теория

Ну а 3^3 = 6 (mod 7)
Надо "для всех целых, взаимно простых с модулем".