Question about sequence length/count/security of $x\mapsto x^\alpha \mod (N=Q\cdot R)$, with $Q=2q_1q_2+1$ and $R=2r_1r_2+1$ and $\alpha = 2q_2r_2$

Given a number $$N$$ with $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ with different primes $$P,Q,q_1,q_2,r_1,r_2$$.

If we now choose an exponent $$\alpha$$ containing prime factors of $$Q,R$$ with $$\alpha=2 \cdot q_2 \cdot r_2$$ we can generate a sequence $$S$$ with elements $$s_{i+1} = s_i^\alpha \mod N$$ starting at a value $$s_0$$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ with}\textbf{ }x\in [1,N-1]$$ we can generate a sequence with (in most cases) a constant length $$|S|_{\max}$$.

Goal: I'm looking for a way to minimize $$|S|_{\max}$$ while still maintain security and being able to generate random values $$\in S$$ without leaking security related parameters. Maintaining security relies on keeping the size of $$|S|$$ and with this the factorization of $$N$$ hidden from a potential adversary to avoid big steps. Furthermore the adversary should not be able to determine the index gap $$i-j$$ in between two randomly generated sequence elements $$s_i,s_j \in S$$

Solving trial: the following part may contain in-complete/wrong equations. They also may require assumptions made above.

The number of unique values $$x^\alpha \mod N$$ is $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

Size of sequences:

To determine the most common and largest sequence length $$S_{\max}$$ we first need to determine the sequence length among the prime factors $$q_1,r_1$$ with $$g_q \equiv \alpha \mod q_1$$ $$L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ for } k\in [1,q_1-1]\}|$$ $$g_r \equiv \alpha \mod r_1$$ $$L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ for } k\in [1,r_1-1]\}|$$

Let $$C$$ be the product from the set of common prime factors among the factorization of $$L_{q_1}$$ and $$L_{p_1}$$ (so no prime powers in $$C$$)
Knowing this we can determine $$|S|_{\max}$$ (in most cases) with $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (one knowing problem: it does not work out if $$L_{q_1}$$ is a full divider of $$L_{r_1}$$ or vice versa)

Number of sequences:

Depending on chosen $$s_0$$ it can be part of $$1$$ out of $$N_S$$ different sequences with length $$|S_{\max}|$$ or in some rare cases also part of a sequence with length $$q_1-1$$,$$r_1-1$$ or $$1$$.
The total number of sequences $$N_S$$ would be (in most cases) $$N_S = \frac{\frac{q_1-1}{L_{q_1}}\cdot \frac{r_1-1}{L_{r_1}}}{\gcd(L_{q_1},L_{r_1})}$$ (as above this won't work if $$L_{q_1}$$ is a full divider of $$L_{r_1}$$ or vice versa)
The number of different sequences is always at least $$N_S > 2$$. The goal is to keep this also as small as possible.

We also need to take care about the exponent $$\alpha$$ being large enough to avoid factorization.

Questions:

Knowing this we can find a hard-to-factorize $$N$$ with $$\alpha$$ and a small $$|S|_{\max}$$. But how small can $$|S|_{\max}$$ be to maintain security?

We call it secure enough if an adversary who generated two random sequence elements $$s_i, s_j$$ needs in mean $$2^{100}$$ steps of computation to calculate the index gap in between $$i$$ and $$j$$ (assuming $$s_i,s_j$$ part of the same sequence).

Q1: Would a $$\approx 102$$-bit $$|S|_{\max}$$ sufficient? If not, how much large does it need to be?
Q2: Has the factorization of $$|S|_{max}$$ an impact on security? E.g. better pick $$|S|_{max} = d\cdot p$$ with small $$d$$ and big prime $$p$$?
Q3: If we pick $$|S|_{max} = A\cdot B \cdot C$$ with $$A,B,C$$ as prime and as similar as possible and furthermore replace $$\alpha$$ with $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ Randomly generated elements would have $$3$$-indices like $$s_{abc}$$. How many steps needed to calculate the index gap to $$s_{def}$$?
E.g. index gap $$a-d$$ would be calculated with $$\alpha_A$$.
Q3: Would it be faster than $$O(AB+C)$$ (surface intersection with line)?

Bonus-Q: Are there some more complete/correct/easier formula for $$|S|_{max}$$ and $$N_S$$?

Example: We pick a $$2048$$-bit $$N = P \cdot Q$$ with prime factors $$q_2 \gg q_1$$ and $$r_2 \gg r_1$$. With this $$\alpha = q_2\cdot r_2$$ could be $$\approx 1800$$-bit and the related $$|S|_{\max}$$ could be $$100/200/300$$-bit

Toy example:

N primes primes primes $$\alpha$$ $$N_\alpha$$ $$|S|_{\max}$$ $$N_S$$ $$L_{q_1}$$ $$L_{r_1}$$
6302749 1787,3527 19,41 < 47,43 4042 840 360 2 18 40
65368909 7103,9203 53,43 < 67,107 14338 2376 546 4 13 42
22216573 3527,6299 41,47 < 43,67 5762 2016 920 2 40 23
12156997 1979,6143 23,37 < 43,83 7138 912 99 8 11 9
61533289 7103,8663 53,61 < 67,71 9514 3348 780* 4 52 60

*example for error, equations predicted $$1560$$ instead

Some related question & answers: about $$N_\alpha$$ ,$$\space$$ about those sequences

• Since the difficulty of factoring N is important: Did you see that N always ends up being of the form 12k+1? And that (2p1p2+1) is only prime when p1p2 = 6m+5 for p1, p2 > 3?  N = (12u+11)(12v+11) = 12k+1 according to your definitions.  This also points out that a back door is present to an adversary. Others can show if this small crack can lead to a full exploit. Hope this helps. Mar 30, 2022 at 18:59
• @MostlyResults nope didn't notice that so far (beside factor 3 has some special role). Thanks for the hint. This makes finding candidates easier. But would this be a backdoor? He still need to factorize $k$ which is only slightly smaller than $N$. Is it safer if I take care about $k$ being a prime as well? Mar 30, 2022 at 19:35