Вопрос о длине/количестве/безопасности последовательности $x\mapsto x^\alpha \mod (N=Q\cdot R)$, с $Q=2q_1q_2+1$ и $R=2r_1r_2+1$ и $\alpha = 2q_2r_2$

Дан номер $N$ с $$N=Q\cdot R$$ $$Q=2\cdot q_1 \cdot q_2+1$$ $$R=2\cdot r_1\cdot r_2+1$$ с разными простыми числами $P,Q,q_1,q_2,r_1,r_2$.

Если мы теперь выберем показатель степени $\альфа$ содержащие простые множители $К,Р$ с $$\alpha=2 \cdot q_2 \cdot r_2$$ мы можем сгенерировать последовательность $S$ с элементами $$s_{i+1} = s_i^\alpha \mod N$$ начиная со значения $s_0$ $$s_0 = x^\alpha \mod N\textbf{ }\text{ с}\textbf{ }x\in [1,N-1]$$ мы можем сгенерировать последовательность с (в большинстве случаев) постоянной длиной $|S|_{\max}$.

Цель: Я ищу способ минимизировать $|S|_{\max}$ сохраняя при этом безопасность и возможность генерировать случайные значения $\в S$ без утечки параметров, связанных с безопасностью.Поддержание безопасности зависит от сохранения размера $|S|$ и с этим факторизация $N$ скрыты от потенциального противника, чтобы избежать больших шагов. Кроме того, противник не должен иметь возможности определить разрыв индекса. $i-j$ между двумя случайно сгенерированными элементами последовательности $s_i,s_j \in S$

Решение пробной версии: следующая часть может содержать неполные/неправильные уравнения. Они также могут потребовать допущений, сделанных выше.

Количество уникальных значений $х^\альфа\мод N$ является $$N_{\alpha} = (1+q_1) \cdot (1+r_1)$$

Размер последовательностей:

Для определения наиболее распространенной и наибольшей длины последовательности $S_{\max}$ нам сначала нужно определить длину последовательности среди простых множителей $q_1,r_1$ с $$ g_q \эквив\альфа\мод q_1$$ $$ L_{q_1} = |\{g_q^k \mod q_1\text{, }\text{ для } k\in [1,q_1-1]\}|$$ $$ g_r \equiv \alpha \mod r_1$$ $$ L_{r_1} = |\{g_r^k \mod r_1\text{, }\text{ для } k\in [1,r_1-1]\}|$$

Позволять $С$ быть произведением множества общих простых множителей среди факторизации $L_{q_1}$ и $L_{p_1}$ (поэтому нет первостепенных сил в $С$)
Зная это, мы можем определить $|S|_{\max}$ (в большинстве случаев) с $$|S|_{\max} = \frac{L_{q_1} \cdot L_{r_1}}{C}$$ (одна известная проблема: не получится, если $L_{q_1}$ является полным делителем $L_{r_1}$ или наоборот)

Количество последовательностей:

В зависимости от выбранного $s_0$ это может быть частью $1$ снаружи $N_S$ различные последовательности с длиной $|S_{\max}|$ или, в некоторых редких случаях, также часть последовательности длиной $q_1-1$,$r_1-1$ или же $1$.
Общее количество последовательностей $N_S$ будет (в большинстве случаев) $$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}) }$$ (как указано выше, это не сработает, если $L_{q_1}$ является полным делителем $L_{r_1}$ или наоборот)
Количество различных последовательностей всегда не меньше $N_S > 2$. Цель состоит в том, чтобы это также было как можно меньше.

Нам также нужно позаботиться об экспоненте $\альфа$ быть достаточно большим, чтобы избежать факторизации.

Вопросы:

Зная это, мы можем найти трудно факторизуемое $N$ с $\альфа$ и небольшой $|S|_{\max}$. Но как мало может $|S|_{\max}$ быть для обеспечения безопасности?

Мы называем его достаточно безопасным, если злоумышленник, сгенерировавший два элемента случайной последовательности, $s_i, s_j$ потребности в среднем $2^{100}$ этапы вычислений для расчета разрыва индекса между $я$ и $j$ (при условии $s_i,s_j$ часть той же последовательности).

Q1: Будет ли $\около 102$-кусочек $|S|_{\max}$ достаточный? Если нет, то насколько большим он должен быть?
Q2: Имеет факторизацию $|S|_{макс.}$ влияние на безопасность? Например. лучше выбрать $|S|_{max} = d\cdot p$ с маленьким $д$ и большой премьер $р$?
Q3: Если мы выберем $|S|_{max} = A\cdot B \cdot C$ с $А,Б,С$ как можно более простым и похожим, а кроме того, заменить $\альфа$ с $$\alpha_A = \alpha^{BC} \mod \phi(N)$$ $$\alpha_B = \alpha^{AC} \mod \phi(N)$$ $$\alpha_C = \alpha^{AB} \mod \phi(N)$$ Случайно сгенерированные элементы будут иметь $3$-индексы как $s_{abc}$. Сколько шагов нужно, чтобы рассчитать разрыв индекса до $s_{деф}$?
Например. разрыв индекса $a-d$ будет рассчитываться с $\альфа_А$.
Q3: Будет ли это быстрее, чем $О(АВ+С)$ (пересечение поверхности с линией)?

Бонус-Q: Есть ли более полная/правильная/более простая формула для $|S|_{макс.}$ и $N_S$?

Пример: мы выбираем $2048$-кусочек $N = P \cdotQ$ с простыми факторами $q_2 \гг q_1$ и $r_2 \gg r_1$. С этим $\альфа = q_2\cdot r_2$ может быть $\около 1800$-bit и связанные с ним $|S|_{\max}$ может быть $100/200/300$-кусочек

Пример игрушки:

*пример для ошибки, предсказанные уравнения $1560$ вместо

Некоторые связанные вопросы и ответы: о $N_\альфа$ ,$\пробел$ об этих последовательностях