Dat un număr $N$ cu $d$ factori primi unici. Poate numărul de valori unice $v$ cu
$$v \equiv x^d \mod N$$
$$x\în[0,N-1]$$
$$N = \prod_{i=1}^{d} p_i$$
fi calculat pentru $d>2$? (Î1)
Suma totală scade la un moment dat? (Q2)
Pentru simplificare presupunem fiecare factor prim $p_i > 5$.
Sau pentru cazul de utilizare țintă fiecare $p_i$ este suficient de mare pentru a evita factorizarea ușoară.
Rezolvarea procesului:
Pentru $d=1$ este banal. Dacă introducem fiecare valoare de la $0$ la $N-1$ pentru $x$ în $x^1 \mod N$. Acolo avem mereu $N$ valori unice.
Asa de $N_{x^1} = N$
Pentru $d=2$ avem două grupuri care interacționează din $p_1$ și $p_2$ cu dimensiunea $p_1-1$ și $p_2-1$ cu un factor prim comun de cel puțin $2$. Dacă le combinăm, obținem (în cele mai multe cazuri) o dimensiune a grupului de
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
Și un număr de $L_n$ instanțe
$$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
Si cateva cazuri speciale pt $0$, $1$, numere cu „$\frac{p_i-1}{2}$'-a putere ($\mod N$) și un caz special special dacă și baza este $p_i^2$
Cu aceasta putem calcula numărul total de reziduuri pătratice ($d=2$) $N_{x^2}$ printre $\mathbb Z/N\mathbb Z$:
$$N_{x^2} = L_n\cdot L + 2 + 2 (\frac{p_1-1}{2}-1)+2(\frac{p_2-1}{2}-1)+2$ $
(mai multe detalii în Răspuns și întrebare)
Î1: Există o ecuație mai generală pentru $d>2$?
Testarea în jur:
Într-un test pentru $d \în [2,3,4,5,6]$ Am calculat toate valorile posibile și am observat raportul
$$R_d = \frac{N_{x^d}}{N}$$
poate fi $1$ pentru $d\în [3,5]$ dar și doar $0.1$. Pentru $d=2$ este $R_2 \aproximativ 0,25$.
$R_4$ a fost mereu $<0.05$ în cazuri de testare. $R_6$ pare a fi chiar mai mic cu unele $R_6<0,001$
Q2.1: Va continua acest raport să scadă pentru mai mari (chiar) $d$?
Q2.2: Nu suma totală de $N_{x^d}$ scade la unele $d$?
Sa presupunem $N$ devine cu 512 biți mai mare pentru fiecare factor prim nou, va exista un $d$ (cu $d \cdot 512$-pic $N$) care are mai puțin $N_{x^d}$ decât $N_{x^2}$ (cu $2\cdot 512 = 1024$-pic $N$)? (Q2.3)
Exemple:
$d=2$
$N = 50471 =41\cdot 1231$ cu $N_{x^2}=12936$ și $R_2 = 0,256 $
$ N = 28363 = 113 \cdot 251$ cu $N_{x^2}= 7182 $ și $R_2 = 0,253 $
$d=3$
$N =18031=13\cdot 19\cdot 73$ cu $N_{x^3}=875$ și $R_3 =0,04$
$N =11339=17\cdot 23\cdot 29$ cu $N_{x^3}=11339$ și $R_3 =1,0$
$d=4$
$N =97867=7\cdot 11\cdot 31\cdot 41$ cu $N_{x^4}=4224$ și $R_4=0,04$
$N =63427=7\cdot 13\cdot 17\cdot 41$ cu $N_{x^4}=880$ și $R_4=0,01$
$d=5$
$N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41$ cu $N_{x^5}=46683$ și $R_5=0,0135$
$N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37$ cu $N_{x^5}=1659931$ și $R_5=1,0$
$d=6$
$N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43$ cu $N_{x^6}=51840$ și $R_6=0,0018$
$N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41$ cu $N_{x^6}=408240$ și $R_6=0,011$
$N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37$ cu $N_{x^6}=18109$ și $R_6=0,000635$
