O secvență ciclică poate fi produsă cu
$$s_{i+1} = s_i^a \mod N$$
cu $N = P \cdot Q$ și $P = 2\cdot p+1$ și $Q = 2\cdot q+1$ cu $P,Q,p,q$ numere prime diferite.
și $a$ o rădăcină primitivă a $p$ și $q$.
Lăsa $s_0 = x_0$ să fie un reziduu pătratic $\mod N$ și secvența ciclică $S = \{x_0^{a^i} \mod N\}$
(Ignorăm bazele de cazuri speciale precum $0,1$ Aici)
Întrebare:
Cum pot membrii (pseudo)-aleatori $x_r$ din aceeași secvență (nu trebuie să fie egal cu $S$) să fie produs fără scurgeri de variabile legate de securitate (cum ar fi $P,Q,p,q$) sau indicii acestora $i$ în
$$x_r = s_i = x_0^{a^i} \mod N $$
sau date mai multe valori aleatoare $x_1,x_2$ spațierea lor index $j$ în
$$x_1=x_2^{a^j}\mod N$$
Mai multe informatii:
Ca exponent $a$ este o rădăcină primitivă a $p,q$ lungimea $L_S$ a secvenței $S$ este (în majoritatea cazurilor)
$$L_S = \mathrm{lcm}(p-1,q-1)$$
Numărul de astfel de secvențe $N_S$ este
$$N_S = \mathrm{gcd}(p-1,q-1)$$
Cazuri speciale: Pentru un punct de plecare al $0$ sau $1$ lungimea ciclului este de numai 1.
Dacă avem $p$-a putere ($\mod N$) ciclul ar avea doar o lungime de $1$ în $\mathbb Z/p\mathbb Z$.
Combinat cu lungimea ciclului pt $q$ obținem o lungime de $\mathrm{lcm}(1,q-1) = q-1$
La fel $q$-a putere $\mathrm{lcm}(p-1,1) = p-1$
Sunt două din fiecare, în funcție de faptul că este multiplu de $P^2 \mod N$ pentru $p$-a putere sau multiplu de $Q^2$ pentru $q$-a-puterea.
Pentru valorile de pornire $(P^2)^q,(Q^2)^p \mod N$ obținem doar o lungime de ciclu de $1$ fiecare ca în $\mathbb Z/p\mathbb Z$ cu $P^2 \equiv 1 \mod p$ si putere $q$ ramanand aceeasi valoare.
Cu aceasta știm numărul total de reziduuri pătratice $N_{x^2}$ printre $\mathbb Z/N\mathbb Z$:
$$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$
-------------
Rezolvarea procesului
Pentru a rezolva această problemă, am putea fie să transferăm o variabilă aleatoare dintr-o secvență aleatoare la secvența țintă, fie să ne limităm cumva numerele aleatoare la membrii secvenței țintă.
Pentru a transfera dintr-o secvență $s_1$ oricărui membru al altei secvenţe $s_2$ căutăm vreun exponent $b$ cu
$$x_{s_1}^b \equiv x_{s_2}^{a^i} \mod N$$
Știm deja despre $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. Pe lângă rădăcina primitivă $a$ acesta este și cazul tuturor celorlalte rădăcini primitive din $p,q$.
Dar din câte știu, este greu de testat pentru o întâmplare $b$.
Cu toate acestea, știm asta $P,Q$ nu poate fi o putere a unei rădăcini primitive. Asa de $b$ poate fi o putere a acestora
$$ b \equiv P^k \mod \phi(N)$$
Trebuie doar să avem grijă de asta $k$ este $\nu= 1$ (acest lucru s-ar scurge $P$) si tot $N_S$ secvențele pot fi parcurse.
Putem face acest lucru prin setare $k$ la
$$ k = 1 + N_S \cdot n $$
cu $n \în \mathbb{N_+}$ (și $b \nu\în \{0,P\}$) (editați: acest lucru nu pare să parcurgă întotdeauna toate)
Dar încă nu știm dacă este curentul nostru $x_r$ se află în interiorul secvenţelor ţintă. De asemenea, acest lucru ar putea dura mult timp dacă $N_S$ este mare (ceea ce probabil este cazul în cazul de utilizare).
Ceva idei pentru a remedia asta?
O altă modalitate ar genera o valoare bazată pe $x_0$ și ascundeți indicele cu un exponent $c$ ca
$$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$
și generează o valoare aleatorie $x_r$ la această secvență
$$x_r = x_0^{c^r} \mod N$$
cu o întâmplare $r$ la alegere. Cu toate acestea în creștere $r$ cu unu ar deplasa indicele întotdeauna la aceeași sumă. Dacă diferența de indice este cunoscută pentru două aleatorii $x_{r_1}, x_{r_2}$ ar fi cunoscut pentru orice altă valoare aleatoare produsă în acest fel. De asemenea, acesta ar fi un calcul costisitor fără partajare $\phi(N)$
Ceva idei pentru a remedia asta?
-------
Exemple de numere:
$N=6313, P=59, Q=107, p=29, q=53$
cu $N_S = 4$ cicluri de lungime $L_S = 364$
si un total de $N_{x^2} = 1620 $ pătrate
Rădăcină primitivă din $p$ și $q$ va fi $a=3$
Puterea schimbătorului de secvență $b$ ar putea fi
$$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$
Cu toate acestea, aceasta $b$ circulă doar între două secvențe și nu toate.
Sunt și multe $b$ care poate parcurge toate secvențele ($2912$ ?), dar încă nu s-a dat seama cum să le calculeze. Cel mai mic astfel de $b$ va fi $5$.
Sau aici câteva alternative:
$$b \in [5 , 10 , 11 , 15 , 17, 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51 $ .,]
Dacă limităm $b$ la exponenții care au aplicat $N_S = 4$ timpii rezultă numai în aceeași variabilă $32$ au ramas:
$$b \în [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3044, 3104 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$
-------
(această întrebare se bazează pe răspunsul la a întrebare similară )
