Cho một số $N$ với $d$ thừa số nguyên tố duy nhất. Có thể số lượng giá trị duy nhất $v$ với
$$v \equiv x^d \mod N$$
$$x\in[0,N-1]$$
$$N = \prod_{i=1}^{d} p_i$$
được tính cho $d>2$? (Q1)
Liệu tổng số tiền giảm tại một số điểm? (quý 2)
Để đơn giản hóa, chúng tôi giả sử mỗi thừa số nguyên tố $p_i > 5$.
Hoặc cho từng trường hợp sử dụng mục tiêu $p_i$ đủ lớn để tránh dễ dàng phân tích thành thừa số.
Giải quyết thử nghiệm:
Vì $d=1$ nó tầm thường. Nếu chúng ta chèn mọi giá trị từ $0$ đến $N-1$ vì $x$ Trong $x^1 \mod N$. Ở đó chúng tôi luôn có $N$ những giá trị độc đáo.
Cho nên $N_{x^1} = N$
Vì $d=2$ chúng tôi có hai nhóm tương tác từ $p_1$ và $p_2$ với kích thước $p_1-1$ và $p_2-1$ với thừa số nguyên tố chung ít nhất là $2$. Nếu chúng tôi kết hợp chúng, chúng tôi sẽ nhận được (trong hầu hết các trường hợp) một nhóm có kích thước
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
Và một số $L_n$ trường hợp
$$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$
Và một số trường hợp đặc biệt đối với $0$, $1$, các số có dấu '$\frac{p_i-1}{2}$'-thứ sức mạnh ($\mod N$) và một số trường hợp đặc biệt đặc biệt nếu cơ sở cũng là $p_i^2$
Với điều này, chúng ta có thể tính tổng số dư bậc hai ($d=2$) $N_{x^2}$ giữa $\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$ $
(chi tiết hơn trong câu trả lời và câu hỏi)
Q1: Có một phương trình tổng quát hơn cho $d>2$?
Kiểm tra xung quanh:
Trong một số thử nghiệm cho $d \trong [2,3,4,5,6]$ Tôi đã tính toán tất cả các giá trị có thể và nhận thấy tỷ lệ
$$R_d = \frac{N_{x^d}}{N}$$
có thể $1$ vì $d\in [3,5]$ nhưng cũng chỉ $0.1$. Vì $d=2$ nó là $R_2 \khoảng 0,25$.
$R_4$ đã luôn luôn $<0.05$ trong các trường hợp thử nghiệm. $R_6$ dường như thậm chí còn nhỏ hơn với một số $R_6<0,001$
Q2.1: Tỷ lệ này sẽ tiếp tục giảm cho lớn hơn (thậm chí) $d$?
Q2.2: Liệu tổng số lượng $N_{x^d}$ giảm tại một số $d$?
Hãy giả sử $N$ lớn hơn 512-bit cho mỗi thừa số nguyên tố mới, liệu sẽ có một $d$ (với một $d \cdot 512$-chút $N$) cái nào có ít hơn $N_{x^d}$ hơn $N_{x^2}$ (với $2\cdot 512 = 1024$-chút $N$)? (Q2.3)
Ví dụ:
$d=2$
$N = 50471 =41\cdot 1231$ với $N_{x^2}=12936$ và $R_2 = 0,256$
$N = 28363 = 113 \cchấm 251$ với $N_{x^2}= 7182 $ và $R_2 = 0,253$
$d=3$
$N =18031=13\cdot 19\cdot 73$ với $N_{x^3}=875$ và $R_3 =0,04$
$N =11339=17\cdot 23\cdot 29$ với $N_{x^3}=11339$ và $R_3 =1,0$
$d=4$
$N =97867=7\cdot 11\cdot 31\cdot 41$ với $N_{x^4}=4224$ và $R_4=0,04$
$N =63427=7\cdot 13\cdot 17\cdot 41$ với $N_{x^4}=880$ và $R_4=0,01$
$d=5$
$N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41$ với $N_{x^5}=46683$ và $R_5=0,0135$
$N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37$ với $N_{x^5}=1659931$ và $R_5=1,0$
$d=6$
$N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43$ với $N_{x^6}=51840$ và $R_6=0,0018$
$N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41$ với $N_{x^6}=408240$ và $R_6=0,011$
$N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37$ với $N_{x^6}=18109$ và $R_6=0,000635$
