2
$\begingroup$

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$.

  • 0
    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.2011-07-18

3 Answers 3

2

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$.

4

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$.

  • 0
    Oh, you're right. I skimmed too hastily.2011-07-18
3

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$.