-1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ I suggest you study some elementary group theory. $\endgroup$ – fkraiem Apr 29 at 19:14
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – J. Doe Apr 29 at 21:16
  • $\begingroup$ 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 $\endgroup$ – J. Doe May 1 at 19:10
  • 1
    $\begingroup$ @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 $\endgroup$ – poncho May 2 at 12:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.