Дан цикл $x \mapsto x^a$ с начальной точкой $x_1$. Можно ли преобразовать другую начальную точку $x_2$, чтобы получить такой же цикл?

При анализе подобных случаев полезно рассматривать поведение по модулю $P$ и по модулю $Q$ по отдельности, а потом посмотреть, как они сочетаются. Добавлю в предположении, что $P\neQ$; вы прямо этого не сказали; Я считаю разумным, что вы предположили это.

Когда мы смотрим на структуру цикла по модулю $P$, мы сначала видим, что $s_0 \bmod P$ является квадратичным вычетом по модулю $P$ (это математический способ сказать «это квадрат»); поскольку $а$ является первообразным корнем $р$, то видим, что циклов три:

• Цикл длины 1 (значение 0)

• Другой цикл длины 1 (значение 1)

• Цикл длины $p-1$; это потому что $a^i \bmod p-1$ являются различными значениями в диапазоне $[0, р-2]$, и $s_0$ порядок $p-1$ (в этой группе квадратичные вычеты, отличные от 1, всегда имеют этот порядок), и поэтому $s_0^{a^i}$ находятся $p-1$ отличные значения.

Мы получаем аналогичные результаты для рассмотрения поведения по модулю $Q$.

Учитывая эти основы, как они сочетаются?

Ну, цикл по модулю $PQ$ повторяется только тогда, когда оба цикла по модулю $P$ повторяется и цикл по модулю $Q$ повторяется; если $P$-цикл длина $\альфа$ и $Q$-цикл длина $\бета$, этот комбинированный цикл имеет длину $\текст{lcm}(\альфа,\бета)$.

Это означает, что любая комбинация двух больших циклов будет иметь длину $\text{lcm}(p-1,q-1)$ (это результат, который вы уже нашли). И здесь $\gcd(p-1,q-1)$ способы, которыми эти два больших цикла могут сочетаться.

Теперь рассмотрим комбинацию, включающую малый цикл; у нас есть две комбинации с длиной цикла $p-1$, две комбинации с длиной цикла $q-1$, и четыре комбинации с длиной цикла 1 (включая $s_0 = 0$ и $s_0 = 1$).

Следовательно, общее количество циклов равно $\gcd(p-1, q-1) + 8$.

И, чтобы ответить на ваш вопрос:

Есть ли способ преобразовать $x_2$ поэтому он будет производить ту же циклическую последовательность, что и $x_1$ делает?

Ну, для любого целого числа $\бета$, у нас есть $s_{i+1}^\beta = (s_i^\beta)^a$. То есть, если мы возьмем каждый элемент цикла и возведем его в степень $\бета$, у нас все еще есть цикл.

Итак, если у нас есть значение $\бета$ для которого $x_2^\бета = x_1$, то это дает нам возможность преобразовать один цикл в другой.

Оказывается, всегда есть такое $\бета$ если оба цикла большие (т. е. имеют длину $\text{lcm}(p-1, q-1)$). Для вырожденных циклов (всех остальных) не будет - впрочем, я не считаю этот случай таким уж интересным...

Конечно, найти такую $\бета$ данный $x_1, x_2$ нетривиальная задача, если $П, К$ большие...