Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

3 Answers

up vote 3 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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