# Is there a way to determine the number of subgroups (with size $s$) while computing $A^b \bmod P$? Constructing a $P$ with $n$ times size $s$?

If you compute $$A^b \bmod P$$ for all $$b$$ the set of results $$R$$ depend at $$A$$ (and $$P$$).

$$R = \{A^b \bmod P, \forall \space b \in \mathbb{N}\}$$

In case $$R$$ contain all numbers from 1 to $$P-1$$, it has the size $$s = |R| = P-1$$ then $$A$$ is a prime root of $$P$$. In all other cases size $$s < P-1$$.

1. Can you determine how many $$A$$'s with subgroup size $$s$$ a certain $$P$$ has?

2. Can you construct a $$P$$ which has $$n$$ $$A$$'s with size $$s$$?

3. Is there a max number of $$A$$'s with the same size $$s$$ (independent of size $$P$$)?

4. Does 1-3.) change if you add the condition A need to be a prime as well?

I did some testing. I noticed the size of $$s$$ is a product of some prime factors of $$P-1$$.

E.g. $$109619 = 2*23*2383+1$$

With Primes as possible $$A$$'s the numbers $$1601, 13619, 17321, 36833, 104473$$ generate a subgroup of size $$s=46=2*23$$

So far I got not more than 5 $$A$$'s which a prime as well for any $$P$$ I tested. Is that a max number or is my $$P$$ just too small?

• I suggest you study some elementary group theory. – fkraiem Apr 29 '19 at 19:14

1.Can you determine how many $$A$$'s with subgroup size $$s$$ a certain $$P$$ has?

If $$s$$ is a divisor of $$P-1$$, then there will be precisely $$\phi(s)$$ elements with that has order $$s$$ (assuming the convention that $$\phi(1) = 1$$); otherwise, there will be 0 elements with that order.

2.Can you construct a $$p$$ which has $$n$$ $$A$$'s with size $$s$$?

If $$n = \phi(s)$$, then you need to find any prime $$p$$ of the form $$p = ks+1$$ (for an integer $$k$$), that is, a prime $$p$$ with $$p \equiv 1 \pmod{s}$$. If $$n \ne \phi(s)$$, then, no, you cannot.

3.Is there a max number of $$A$$'s with the same size (independent of size $$P$$)?

No, it is unbounded.

4.Does 1-3.) change if you add the condition A need to be a prime as well?

1 and 2 does; however it's unclear how - values from the group $$\mathbb{Z}_p^*$$ which just happen to have the same representation as primes in $$\mathbb{N}$$ isn't a particularly clean condition.

3 does not; if we consider an arbitrary large safe prime $$p$$ [1], then we have $$(p-1)/2$$ elements of order $$p-1$$ and of the order $$(p-1)/2$$; every integer (hence every prime) between 2 and $$p-2$$ are in one of those two groups, and hence (by making $$p$$ arbitrarily large), we can make one of those two groups contain an arbitrarily large set of primes.

[1] There's no proof that there exist arbitrarily large safe primes, but it is almost certainly true

• Thanks for fast response, especially for the relation between $\phi(s)$ and the count. Will have some trials. @4.3. But with increasing $P$ also the group size $s$ increases. So they are not independent in that case. But you can make it as big you like, so it should work. – J. Doe Apr 29 '19 at 21:16
• Something wrong here. I did some testing. E.g. number $P=403617=( 3 *19 * 73* 97)$ and $P-1 = 32*12613=2^5*12613$. If I pick $s=32$ as a divisor of $P-1$ then $\phi(s=32)=16$ elements should exist with order $s$ (poncho's answer for case 1.). In test I found 60 numbers (instead of 16) with order $s$, so 60 numbers with $number^{32} = 1 \mod p$. (with 16 in exponent they are not 1, all of them are 162280). Some numbers: 8093, 8969, 22193, 28387, 41077 47387, 54833, 61561, 71249, 80447, 83563, 91199, 91807, 95191 – J. Doe May 1 '19 at 19:10
• @J.Doe: the rule I gave assumed $P$ was prime; if it's not, then $\mathbb{Z}_P^*$ is not a cyclic group (and certainly not isomorphic to $\mathbb{Z}_{P-1}$), with a considerably more complex structure, and so it doesn't hold – poncho May 2 '19 at 12:50