Учитывая (например) разные простые числа $р,к$ с $2 р+1$, и 4$+3$ премьер, а также (то же самое для $q$).
Позволять
$$N = (4 п+3)\cdot (4 д+3)$$
При этом последовательность
$$s_{i+1} = s_i^4 \mod N$$
будет $p\cdotq$ элементы (в большинстве случаев) для $s_0 = г^4 \mod N$ почти для всех случайных значений $г$.
В зависимости от выбранного $г$ связанные $s_0 = г^4 \mod N$ будет (почти всегда) членом 1 из 4 непересекающихся последовательностей длины $p\cdotq$.
Вопрос:
$\text{ }\mathrm{ I }.$ Есть ли простой способ проверить, является ли случайным $г$ приводит к члену последовательности $S_1,S_2,S_3,S_4$?
$\mathrm{II}.$ Или мы можем произвести случайный $г'$ которые все являются членами одной и той же последовательности?
(Оба без утечки секретной информации. $s_0$ или другой $ф(р)$ тоже можно сравнить)
(Также было бы полезно сократить его до менее чем 4 последовательностей одинакового размера.)
Подробнее: Если мы сделаем $\mathrm{II}.$ мы также должны гарантировать соответствующие $s_0$ не следовать известному порядку. Например. если мы производим $г'$ с фиксированным выбранным членом последовательности $s_m$ и $r' = s_m^{4^r} \mod N$ мы всегда знаем точную позицию, связанную с $s_m$ для каждого $г$ $\mapsto s_{m+r+1}$.
Особые случаи: Для некоторых $г$ последовательность будет иметь только $р,к$ или же $1$ элемент. Мы игнорируем их здесь. Чтобы избежать этого, нам нужно выбрать $г$ с
$$r\in[2,N-1] $$
$$r\mod (4 п+3)\не=0 $$
$$ r\mod (4 q+3)\not=0 $$
$$ r \not\in\{r_*^{2p+1} \mod N \}\land r \not\in\{r_*^{2q+1} \mod N \}$$
противник также сможет генерировать эти случайные элементы на своей машине. Даны 2 случайных $г$ он не должен знать индекса расстояния между их родственными $s_0$ среди целевой последовательности. Если он каким-то образом знает это за 2 случайных $г$ он не должен быть в состоянии легко вычислить это для 3-го случайного $г$ (в большинстве случаев). показатель степени $\альфа = 4$ может быть заменен трудно вычисляемым эквивалентом.
Пример: $N= 7849=47 \cdot 167$ будет производить $4$ последовательности длиной 451$ = 11\cdot 41$
(плюс частные случаи длины $11,41,1$)
