Циклическая последовательность может быть получена с помощью
$$s_{i+1} = s_i^a \mod N$$
с $N = P \cdotQ$ и $P = 2\cdot p+1$ и $Q = 2\cdotq+1$ с $P,Q,p,q$ разные простые числа.
и $а$ первобытный корень $р$ и $q$.
Позволять $s_0 = x_0$ быть квадратичным вычетом $\мод Н$ и циклическая последовательность $S = \{x_0^{a^i} \mod N\}$
(мы игнорируем основания для особых случаев, такие как $0,1$ здесь)
Вопрос:
Как могут (псевдо)-случайные члены $x_r$ той же последовательности (не обязательно должны быть равны $S$) производиться без утечки переменных, связанных с безопасностью (таких как $P,Q,p,q$) или их индексы $я$ в
$$x_r = s_i = x_0^{a^i} \mod N $$
или задано несколько случайных значений $x_1,x_2$ интервал между их индексами $j$ в
$$x_1=x_2^{a^j}\mod N$$
Еще немного информации:
Как показатель $а$ является первообразным корнем $р,к$ длина $L_S$ последовательности $S$ есть (в большинстве случаев)
$$L_S = \mathrm{lcm}(p-1,q-1)$$
Количество таких последовательностей $N_S$ является
$$N_S = \mathrm{gcd}(p-1,q-1)$$
Особые случаи: Для отправной точки $0$ или же $1$ длина цикла всего 1.
Если у нас есть $р$-я степень ($\мод Н$) цикл будет иметь только длину $1$ в $\mathbb Z/p\mathbb Z$.
В сочетании с длиной цикла для $q$ мы получаем длину $\mathrm{lcm}(1,q-1) = q-1$
Тем же $q$-я степень $\mathrm{lcm}(p-1,1) = p-1$
Каждого из них по два, в зависимости от того, кратно ли оно $P^2 \mod N$ за $р$-я степень или кратная $Q^2$ за $q$-я-сила.
Для начальных значений $(P^2)^q,(Q^2)^p \mod N$ мы получаем только длину цикла $1$ каждый как в $\mathbb Z/p\mathbb Z$ с $P^2 \экв 1 \mod p$ и сила $q$ остающееся прежним значением.
При этом мы знаем общее количество квадратичных вычетов $N_{х^2}$ среди $\mathbb Z/N\mathbb Z$:
$$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$
-------------
Решение суда
Чтобы решить эту проблему, мы могли бы либо перенести случайную величину из случайной последовательности в целевую последовательность, либо каким-то образом ограничить наши случайные числа членами целевой последовательности.
Для перехода из одной последовательности $s_1$ любому члену другой последовательности $s_2$ мы ищем некоторый показатель $b$ с
$$x_{s_1}^b \эквив x_{s_2}^{a^i} \mod N$$
Мы уже знаем о $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. Помимо примитивного корня $а$ это также относится ко всем другим примитивным корням из $р,к$.
Но насколько я знаю, это трудно проверить на случайном $b$.
Однако мы знаем, что $П,Q$ не может быть степенью первообразного корня. Так $b$ может быть сила тех
$$ b \эквив P^k \mod \phi(N)$$
Нам просто нужно позаботиться об этом $к$ является $\не= 1$ (это будет утечка $P$) и все $N_S$ последовательности могут циклически проходить через.
Мы можем сделать это, установив $к$ к
$$ k = 1 + N_S \cdot n $$
с $n \in \mathbb{N_+}$ (и $b \не\в \{0,P\}$) (редактировать: это, кажется, не всегда проходит через все из них)
Но мы до сих пор не знаем, является ли наш текущий $x_r$ находится внутри целевых последовательностей. Также это может занять некоторое время, если $N_S$ большой (что, вероятно, имеет место в случае использования).
Есть идеи, как это исправить?
Другим способом было бы создание значения на основе $x_0$ и скрыть индекс с показателем степени $с$ нравиться
$$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$
и сгенерировать случайное значение $x_r$ в этой последовательности
$$x_r = x_0^{c^r} \mod N$$
со случайным $г$ выбора. Однако увеличение $г$ на единицу будет сдвигать индекс всегда на одну и ту же величину. Если разность индексов известна для двух случайных $x_{r_1}, x_{r_2}$ это было бы известно для каждого другого случайного значения, полученного таким образом. Кроме того, это было бы дорогостоящим вычислением без совместного использования $\фи(N)$
Есть идеи, как это исправить?
-------
Примеры номеров:
$N=6313, P=59, Q=107, p=29, q=53$
с $N_S = 4$ циклы длины $L_S = 364$
и всего $N_{x^2} = 1620 $ квадраты
Первобытный корень из $р$ и $q$ было бы $а=3$
Мощность преобразователя последовательности $b$ может быть
$$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$
Однако это $b$ делает только цикл между двумя последовательностями, а не всеми из них.
Есть также много $b$ который может перебирать все последовательности ($2912$ ?), но пока не понял, как их вычислить. Самый маленький такой $b$ было бы $5$.
Или вот несколько альтернатив:
$$b \in [5 , 10 , 11 , 15 , 17 , 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51,.. ]$$
Если мы ограничим $b$ показателям, которые применялись $N_S = 4$ раз приводит к одной и той же переменной только $32$ остаются:
$$b \in [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3104, 3497, 3550, 3740, 4135, 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$
-------
(этот вопрос основан на ответе на аналогичный вопрос )
