A cyclic sequence can be produced with
$$s_{i+1} = s_i^a \mod N$$
with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ different primes.
and $a$ a primitive root of $p$ and $q$.
Let $s_0 = x_0$ be a quadratic residue $\mod N$ and the cyclic sequence $S = \{x_0^{a^i} \mod N\}$
(we ignore special case bases like $0,1$ here)
Question:
How can (pseudo)-random members $x_r$ of the same sequence (don't need to be equal to $S$) be produced without leaking security related variables (like $P,Q,p,q$) or their indices $i$ in
$$x_r = s_i = x_0^{a^i} \mod N $$
or given multiple random values $x_1,x_2$ their index spacing $j$ in
$$x_1=x_2^{a^j}\mod N$$
Some more information:
As exponent $a$ is a primitive root of $p,q$ the length $L_S$ of the sequence $S$ is (in most cases)
$$L_S = \mathrm{lcm}(p-1,q-1)$$
The number of such sequences $N_S$ is
$$N_S = \mathrm{gcd}(p-1,q-1)$$
Special cases: For a starting point of $0$ or $1$ the cycle length is only 1.
If we have the $p$-th power ($\mod N$) the cycle would only have a length of $1$ in $\mathbb Z/p\mathbb Z$.
Combined with the cycle length for $q$ we get a length of $\mathrm{lcm}(1,q-1) = q-1$
Same $q$-th power $\mathrm{lcm}(p-1,1) = p-1$
There are two of each, depending if it is a multiple of $P^2 \mod N$ for $p$-th power or multiple of $Q^2$ for $q$-th-power.
For starting values $(P^2)^q,(Q^2)^p \mod N$ we get only a cycle length of $1$ each as in $\mathbb Z/p\mathbb Z$ with $P^2 \equiv 1 \mod p$ and power $q$ remaining the same value.
With this we know the total number of quadratic residue $N_{x^2}$ among $\mathbb Z/N\mathbb Z$:
$$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$
-------------
Solving trial
To solve this problem we could either transfer a random variable from a random sequence to the target sequence or somehow limit our random numbers to the members of the target sequence.
To transfer from one sequence $s_1$ to any member of another sequence $s_2$ we are looking for some exponent $b$ with
$$x_{s_1}^b \equiv x_{s_2}^{a^i} \mod N$$
We already know about $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. Besides primitive root $a$ that's also the case for all other primitive roots from $p,q$.
But as far as I know that's hard to test for a random $b$.
However we do know that $P,Q$ can't be a power of a primitive root. So $b$ can be a power of those
$$ b \equiv P^k \mod \phi(N)$$
We just need to take care this $k$ is $\not= 1$ (this would leak $P$) and all $N_S$ sequences can by cycled through.
We can do this by setting $k$ to
$$ k = 1 + N_S \cdot n $$
with $n \in \mathbb{N_+}$ (and $b \not\in \{0,P\}$) (edit: this seem to not always cycle through all of them)
But we still don't know if our current $x_r$ is inside the target sequences. Also this might take some long time if $N_S$ is big (which is probably the case in use case).
Any ideas to fix that?
Another way would generating a value based at $x_0$ and hide the index with an exponent $c$ like
$$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$
and generate a random value $x_r$ at this sequence
$$x_r = x_0^{c^r} \mod N$$
with a random $r$ of choice. However increasing $r$ by one would shift the index always to the same amount. If the index difference is known for two random $x_{r_1}, x_{r_2}$ it would be known for every other random value produced this way. Also this would be an expensive computation without sharing $\phi(N)$
Any ideas to fix that?
-------
Example numbers:
$N=6313, P=59, Q=107, p=29, q=53$
with $N_S = 4$ cycles of length $L_S = 364$
and a total of $N_{x^2} = 1620 $ squares
Primitive root from $p$ and $q$ would be $a=3$
Sequence changer power $b$ could be
$$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$
However this $b$ does only cycle in between two sequence and not all of them.
There are also many $b$ which can cycle through all sequences ($2912$ ?) but didn't figure out how to compute them yet. Smallest such a $b$ would be $5$.
Or here some alternatives:
$$b \in [5 , 10 , 11 , 15 , 17, 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51,.. ]$$
If we limit $b$ to exponents which applied $N_S = 4$ times result in the same variable only $32$ are left over:
$$b \in [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3104, 3497, 3550, 3740, 3945, 4135, 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$
-------
(this question is based at the answer to a similar question )