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.