給定ññN和ddd主要原因。唯一值的數量Xd反對ñXd反對ñx^d mod N計算為d>2d>2d>2?總金額會在某個時候減少嗎？
給定一個數字 $ N $ 和 $ d $ 獨特的主要因素。唯一值的數量 $ v $ 和 $$ v \equiv x^d \mod N $$ $$ x\in[0,N-1] $$ $$ N = \prod_{i=1}^{d} p_i $$ 計算為 $ d>2 $ ? ( Q1 )
總金額會在某個時候減少嗎？（Q2）
為簡化起見，我們假設每個主要因素 $ p_i > 5 $ .
或者對於每個目標案例 $ p_i $ 足夠大以避免容易的因式分解。
解決試驗：
對於 $ d=1 $ 這是微不足道的。如果我們插入每個值 $ 0 $ 至 $ N-1 $ 為了 $ x $ 在 $ x^1 \mod N $ . 我們總是在那裡 $ N $ 獨特的價值觀。
所以 $ N_{x^1} = N $
為了 $ d=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} $ ‘-次冪（ $ \mod N $ ) 和一些特殊情況，如果基礎也是 $ p_i^2 $
有了這個，我們可以計算二次剩餘的總數（ $ d=2 $ ) $ N_{x^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：**有沒有更一般的方程 $ d>2 $ ?
周圍測試：
在一些測試中 $ d \in [2,3,4,5,6] $ 我計算了所有可能的值並註意到了比率 $$ R_d = \frac{N_{x^d}}{N} $$ 可 $ 1 $ 為了 $ d\in [3,5] $ 但也只是 $ 0.1 $ . 為了 $ d=2 $ 它是 $ R_2 \approx 0.25 $ .
$ R_4 $ 一直都是 $ <0.05 $ 在測試案例中。 $ R_6 $ 似乎更小了一些 $ R_6<0.001 $
**Q2.1：**這個比率會隨著更大（偶數）而繼續下降嗎？ $ d $ ?
**Q2.2：**總金額是否 $ N_{x^d} $ 減少一些 $ d $ ?
讓我們假設 $ N $ 對於每個新的素數因子都會增大 512 位，是否會有 $ d $ （帶有一個 $ d \cdot 512 $ -少量 $ N $ ) 其中有較少 $ N_{x^d} $ 比 $ N_{x^2} $ （和 $ 2\cdot 512 = 1024 $ -少量 $ N $ )? （Q2.3）
例子：
$ d=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 $
$ d=3 $
$ N =18031=13\cdot 19\cdot 73 $ 和 $ N_{x^3}=875 $ 和 $ R_3 =0.04 $
$ N =11339=17\cdot 23\cdot 29 $ 和 $ N_{x^3}=11339 $ 和 $ R_3 =1.0 $
$ d=4 $
$ N =97867=7\cdot 11\cdot 31\cdot 41 $ 和 $ N_{x^4}=4224 $ 和 $ R_4=0.04 $
$ N =63427=7\cdot 13\cdot 17\cdot 41 $ 和 $ N_{x^4}=880 $ 和 $ R_4=0.01 $
$ d=5 $
$ N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41 $ 和 $ N_{x^5}=46683 $ 和 $ R_5=0.0135 $
$ N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37 $ 和 $ N_{x^5}=1659931 $ 和 $ R_5=1.0 $
$ d=6 $
$ N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43 $ 和 $ N_{x^6}=51840 $ 和 $ R_6=0.0018 $
$ N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41 $ 和 $ N_{x^6}=408240 $ 和 $ R_6=0.011 $
$ N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37 $ 和 $ N_{x^6}=18109 $ 和 $ R_6=0.000635 $
- 是的，免費平方 $ N $ 公式是 $$ \prod_{i=1}^d\left(1+\frac{p_i-1}{(d,p_i-1)}\right) $$
- 上面的表達式將等於 $ N $ 當且當 $ (d,p_i-1)=1 $ 對所有人 $ i $ . 對於奇數 $ d $ 我們可以找到任意多個具有此性質的素數。由此可見，上 $ R_d $ 為 1，為奇數 $ d $ 其中包括大的價值 $ d $
相反，對於任何給定的 $ d $ 我們可以構造 $ N $ 從質數全部是 1 mod $ d $ . 這樣我們就可以找到 $ N $ 這樣 $ R_d(N)=O(d^{-d}) $ , 但是這樣 $ N $ 是稀疏的。