Score:0

Given $N$ with $d$ prime factors. Can the number of unique values $x^d \mod N$ calculated for $d>2$? Does the total amount decrease at some point?

at flag

Given a number $N$ with $d$ unique prime factors. Can the number of unique values $v$ with $$v \equiv x^d \mod N$$ $$x\in[0,N-1]$$ $$N = \prod_{i=1}^{d} p_i$$ be calculated for $d>2$? (Q1)
Does the total amount decrease at some point? (Q2)


For simplification we assume each prime factor $p_i > 5$.
Or for target use case each $p_i$ is big enough to avoid easy factorization.


Solving trial:
For $d=1$ it's trivial. If we insert every value from $0$ to $N-1$ for $x$ in $x^1 \mod N$. There we always have $N$ unique values.
So $N_{x^1} = N$

For $d=2$ we have two interacting groups from $p_1$ and $p_2$ with size $p_1-1$ and $p_2-1$ with a shared prime factor of at least $2$. If we combine them we get (in most cases) a group size of
$$L = \mathrm{lcm}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ And a number of $L_n$ instances $$L_n = \mathrm{gcd}(\frac{p_1-1}{2}-1, \frac{p_2-1}{2}-1)$$ And some special cases for $0$, $1$, numbers with the '$\frac{p_i-1}{2}$'-th power ($\mod N$) and some special special case if the base is also $p_i^2$
With this we can calculate the total number of quadratic residue ($d=2$) $N_{x^2}$ among $\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$$ (more details in answer and question)

Q1: Is there a more general equation for $d>2$?


Testing around:
In some test for $d \in [2,3,4,5,6]$ I computed all possible values and noticed the ratio $$R_d = \frac{N_{x^d}}{N}$$ can be $1$ for $d\in [3,5]$ but also just $0.1$. For $d=2$ it's $R_2 \approx 0.25$.
$R_4$ was always $<0.05$ in test cases. $R_6$ seems to be even smaller with some $R_6<0.001$

Q2.1: Will this ratio continue to decrease for larger (even) $d$?

Q2.2: Does the total amount of $N_{x^d}$ decrease at some $d$?
Let's assume $N$ gets 512-bit bigger for each new prime factor, will there be a $d$ (with a $d \cdot 512$-bit $N$) which has less $N_{x^d}$ than $N_{x^2}$ (with $2\cdot 512 = 1024$-bit $N$)? (Q2.3)


Examples:
$d=2$
$N = 50471 =41\cdot 1231$ with $N_{x^2}=12936$ and $R_2 = 0.256$
$ N = 28363 = 113 \cdot 251$ with $N_{x^2}= 7182 $ and $R_2 = 0.253$

$d=3$
$N =18031=13\cdot 19\cdot 73$ with $N_{x^3}=875$ and $R_3 =0.04$
$N =11339=17\cdot 23\cdot 29$ with $N_{x^3}=11339$ and $R_3 =1.0$

$d=4$
$N =97867=7\cdot 11\cdot 31\cdot 41$ with $N_{x^4}=4224$ and $R_4=0.04$
$N =63427=7\cdot 13\cdot 17\cdot 41$ with $N_{x^4}=880$ and $R_4=0.01$

$d=5$
$N =3453307=11\cdot 13\cdot 19\cdot 31\cdot 41$ with $N_{x^5}=46683$ and $R_5=0.0135$
$N =1659931=7\cdot 13\cdot 17\cdot 29\cdot 37$ with $N_{x^5}=1659931$ and $R_5=1.0$

$d=6$
$N=28709681=7\cdot 11\cdot 13\cdot 23\cdot 29\cdot 43$ with $N_{x^6}=51840$ and $R_6=0.0018$
$N=35797223=7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 41$ with $N_{x^6}=408240$ and $R_6=0.011$
$N=28527037=7\cdot 11\cdot 17\cdot 19\cdot 31\cdot 37$ with $N_{x^6}=18109$ and $R_6=0.000635$

Score:1
ru flag
  1. Yes, for square free $N$ the formula is $$\prod_{i=1}^d\left(1+\frac{p_i-1}{(d,p_i-1)}\right)$$

  2. The above expression will equal $N$ iff $(d,p_i-1)=1$ for all $i$. For odd $d$ we can find arbitrarily many primes with this property. It follows that the supremum of $R_d$ is 1, for odd $d$ which includes large values of $d$

Conversely, for any given $d$ we can construct $N$ from primes all of which are 1 mod $d$. In such a way we can find $N$ such that $R_d(N)=O(d^{-d})$, but such $N$ are sparse.

J. Doe avatar
at flag
interesting, I thought it's a more complicated equation. Thanks for answering again. Just one note: is $(a,b)$ a common short term for $\mathrm{gcd}(a,b)$ or did you just omit them for any reason?
J. Doe avatar
at flag
so related to Q2.2. If $N$ increases by about $B$ bit with each factor we would also need such many unique prime factors ($2^B$) to decrease the total count which is impossible (not that many primes)
Daniel S avatar
ru flag
$(a,b)$ for the greatest common divisor is common notation in number theory, though the more explicit $\mathrm{gcd}(a,b)$ is often used in cryptography. I think that unless $d$ is very large or $B$ is very small, there should still be plenty of primes.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.