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