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
