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