# Finding a (small) prime great enough that there are at least m elements of order m

I'm hoping that someone can provide me with some results or point me in the right direction.

I'm working with finite fields; really, I'm just doing arithmetic modulo a prime $p$. I'm taking elements to powers, so I believe this deals with the multiplicative group in particular. Now I basically require that there are at least $m$ elements of a certain order (or greater). We can call this order $n$. I'm wondering if there's a fairly simple and/or easy way to get an estimate of $p$, like how great $p$ must be. The idea is, I want to work with a prime that's big enough to contain $m$ elements of order $n$, but preferably not much larger than the minimum prime that does so.

Extra Credit I'd like an easy way to find the $m$ elements of order $n$. I'm really looking for the simplest way to accomplish both of these goals.

MAIN GOAL I'm trying to ensure that $p$ doesn't need to be astronomically large compared to $m$ and $n$.

-
At the risk of asking the obvious, do you mean order in the multiplicative group? –  John M Jul 18 '11 at 3:10
If I'm not mistaken, assuming $n$ is a divisor of $p-1$, then the Euler's totient function $\phi(n)$ gives you the number of elements of order $n$. –  John M Jul 18 '11 at 3:21
@John M: I'm taking numbers to powers. So for example, I'd say the order of 2 modulo 7 is 3 since $2^0\equiv1$ and $2^3\equiv1$. I think that this is the multiplicative group. –  Matt Groff Jul 18 '11 at 3:24
NOTE: I don't need to be very precise here. This is to attempt to speed up an algorithm, so I may end up going through every number between 1 and $p$ and finding its order. As long as $p$ isn't astronomically large compared to $m$ and $n$, things should suffice. Also, $m$ and $n$ are probably close in value. –  Matt Groff Jul 18 '11 at 3:27
Continuing the example of $\pmod 7, \phi(6)=2$, so there are two elements of order $6$, namely $3$ and $5$. As remarked below, there are a fair number of elements of maximum order, so just trying until you find one will be reasonable. Once you have found one, taking it to powers coprime to $p-1$ will get you the rest. –  Ross Millikan Jul 18 '11 at 3:30

Here's a specific estimate for $p$: Pick prime $p \geq \max(n+1,m^2+1,11)$. Then you'll have $\phi(p-1)$ elements of order $p-1$ which is greater than or equal to desired order $n$. Noting that we have the lower bound $\phi(n) \geq \sqrt n$ for $n > 6$, you'll have $\phi(p-1) \geq m$.

-

The following should give you a start. Any prime $p$ has $\phi(p-1)$ primitive roots, where $\phi$ is the Euler $\phi$-function.

In the literature, you can find explicit lower bounds for $\phi(n)$ in terms of $n$. It turns out that $\phi(n)$ cannot be much smaller than $n$. If memory serves right (and it often doesn't) we can't get much below $n/(\ln n)$ if $n$ is at all large.

If, as in your case, we are satisfied with elements of large but not necessarily maximum order, we can proceed as follows.

Let $g$ be a primitive root of $p$, and let $d$ be a positive divisor of $\phi(p)$. Then $g^k$ has order $d$ modulo $p$ if and only if $k$ is of the form $j\phi(p)/d$, where $\gcd(j,d)=1$. Thus there are exactly $\phi(d)$ incongruent elements of order $d$ modulo $p$.

So by taking $d=(p-1)/2$, we get another big collection of elements of large order.

Being largely ignorant in computational number theory, I must decline the opportunity for extra credit.

Added: If $\phi(p)$ happens to be on the small side compared to $p$, that's because $p-1$ has too many small divisors $d$. But then there is some compensation because of the elements of large order $(p-1)/d$.

-
Note that the order $d$ must divide $\phi(p)=p-1$, so OP will need a prime such that $p\equiv 1 \pmod{d}$. –  anon Jul 18 '11 at 5:28
According to how I read the original problem, $m=d$ and $n=\phi(d)$ are givens, and a prime $p$ is an unknown that is sought after. So you can't "start with $p$," can you? –  anon Jul 18 '11 at 6:08
Oh, you're right. I skimmed too hastily. –  anon Jul 18 '11 at 6:24

The multiplicative group is cyclic of order $p-1$, so there are $\phi(p-1)$ elements of order $p-1$, where $\phi$ is Euler's totient function. You can also calculate how many are of each lesser order if you know the factorization of $p-1$. There is a small discussion of this in Wikipedia and more details in any group theory book. So $p$ doesn't have to be much greater than $m$.

-