Given an integer $a$, I would like to build a table of entries $(p, \text{ord}\_p(a))$, where $p$ runs over the prime numbers not dividing $a$ and not exceeding a fixed parameter $P$, and $\text{ord}\_p(a)$ is the multiplicative order of $a$ modulo $p$.
I known that computing the multiplicative order is a difficult problem, since it is related to the discrete logarithm problem, so I'm not expecting a very efficient algorithm to build such a table. However, I would like to know if there is some trick to build the table more efficiently than just computing $\text{ord}\_p(a)$ for each $p$. For instance, can some of the computation done to compute $\text{ord}\_p(a)$ be used to speed up the computation of $\text{ord}\_q(a)$ for $q \neq p$? Can $\text{ord}\_p(a)$ be computed in parallel for more primes $p$? The only thing I could come up is that working modulo $p\_1 \cdots p\_k$, one can in fact compute the multiplicative order of $a$ modulo $p\_i$ in parallel, but $p\_1 \cdots p\_k$ gets very large so it does not seem a great advantage.


**Notes:**


* I'm interested in $a$ and $p$ in the range of a 32-bits / 64-bits integers.
* I would like to use only operations for 32-bits / 64-bits integers, no fancy arbitrary-size-integer arithmetic.
* I'm assuming that the list of primes $p$ is precomputed.



"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$
Order computations are generally easier than discrete logarithms, and they are *much* easier if you know the factorization of the group order.


If you're dealing with a precomputed list of 32- or 64-bit primes, then you can precompute the factorization of $p-1$ for each $p$. Given this factorization, order computations mod $p$ can be very efficient: Chapter 7 ("Fast order algorithms") of [Sutherland's thesis](https://math.mit.edu/%7Edrew/sutherland-phd.pdf) is a good reference for this.


