Дан номер $N$ с $д$ уникальные первичные факторы. Может ли количество уникальных значений $v$ с
$$v \эквив x^d \mod N$$
$$x\in[0,N-1]$$
$$N = \prod_{i=1}^{d} p_i$$
рассчитываться для $д>2$? (Q1)
Уменьшается ли общая сумма в какой-то момент? (Q2)
Для упрощения будем считать, что каждый простой множитель $p_i > 5$.
Или для целевого варианта использования каждый $p_i$ достаточно велик, чтобы избежать простой факторизации.
Решение пробной версии:
За $д=1$ это тривиально. Если мы вставим каждое значение из $0$ к $N-1$ за $х$ в $x^1 \mod N$. Там у нас всегда $N$ уникальные значения.
Так $N_{х^1} = N$
За $д=2$ у нас есть две взаимодействующие группы из $p_1$ и $p_2$ с размером $p_1-1$ и $p_2-1$ с общим простым делителем не менее $2$. Если мы объединим их, мы получим (в большинстве случаев) размер группы
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
И ряд $L_n$ экземпляры
$$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
И некоторые частные случаи для $0$, $1$, числа с '$\frac{p_i-1}{2}$'-я степень ($\мод Н$) и какой-то особый частный случай, если база также $p_i^2$
При этом мы можем вычислить общее количество квадратичных вычетов ($д=2$) $N_{х^2}$ среди $\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$ $
(подробнее в отвечать и вопрос)
Q1: Существует ли более общее уравнение для $д>2$?
Тестирование вокруг:
В каком-то тесте на $d \in [2,3,4,5,6]$ Я вычислил все возможные значения и заметил соотношение
$$R_d = \frac{N_{x^d}}{N}$$
возможно $1$ за $d\in [3,5]$ но и просто $0.1$. За $д=2$ это $R_2 \около 0,25$.
$R_4$ был всегда $<0.05$ в тестовых примерах. $R_6$ кажется, даже меньше с некоторыми $R_6<0,001$
Q2.1: Будет ли это отношение продолжать уменьшаться для больших (четных) $д$?
Q2.2: Общая сумма $N_{x^d}$ уменьшится в какой-то $д$?
Предположим $N$ становится на 512 бит больше для каждого нового простого множителя, будет ли $д$ (с $d \cdot 512$-кусочек $N$) у которого меньше $N_{x^d}$ чем $N_{х^2}$ (с $2\cdot 512 = 1024$-кусочек $N$)? (Q2.3)
Примеры:
$д=2$
$N = 50471 =41\cdot 1231$ с $N_{x^2}=12936$ и $R_2 = 0,256$
$ N = 28363 = 113 \cdot 251$ с $N_{x^2}= 7182 $ и $R_2 = 0,253$
$д=3$
$N =18031=13\cdot 19\cdot 73$ с $N_{x^3}=875$ и $R_3 =0,04$
$N =11339=17\cточка 23\cточка 29$ с $N_{x^3}=11339$ и $R_3 =1.0$
$д=4$
$N =97867=7\cточка 11\cточка 31\cточка 41$ с $N_{x^4}=4224$ и $R_4=0,04$
$N =63427=7\cточка 13\cточка 17\cточка 41$ с $N_{x^4}=880$ и $R_4=0,01$
$д=5$
$N =3453307=11\cточка 13\cточка 19\cточка 31\cточка 41$ с $N_{x^5}=46683$ и $R_5=0,0135$
$N =1659931=7\cточка 13\cточка 17\cточка 29\cточка 37$ с $N_{x^5}=1659931$ и $R_5=1.0$
$д=6$
$N=28709681=7\cточка 11\cточка 13\cточка 23\cточка 29\cточка 43$ с $N_{x^6}=51840$ и $R_6=0,0018$
$N=35797223=7\cточка 11\cточка 17\cточка 23\cточка 29\cточка 41$ с $N_{x^6}=408240$ и $R_6=0,011$
$N=28527037=7\cточка 11\cточка 17\cточка 19\cточка 31\cточка 37$ с $N_{x^6}=18109$ и $R_6=0.000635$
