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.


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

2 Answers 2


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 is a good reference for this.


I've implemented an algorithm precisely for this problem. Below is a short description of the algorithm I've used. The algorithms are likely standard, and I believe there are further optimizations that one could do to it, but should get one started and suffice for many purposes. As a rough benchmark, my code computes $ord_p(a)$ for all $p \le 10^9$ in $\approx 90$ seconds on my laptop. If you want an implementation (in C++), send me a private message.

First, you want to compute the prime factorizations for $p-1$ for primes $p \le P$. If $P$ is small, you can run the sieve of Erastothenes and save the factors to memory. However, if $P$ is large you may run to memory problems. There's a way around this, by exploiting the fact that you go through all of the primes $p \le P$ in order:

Let $N = \sqrt{P}$. Maintain an array $A$ of vectors of length $N$, initialized so that $A[i], i \le N$ is empty if $i$ is not a prime and $A[i] = \{i\}$ if $i$ is a prime. Then, process the integers $n = 1, 2, \ldots , P$ from smallest to largest. (In your application, "processing" means roughly "check if $n$ is a prime, if yes, calculate $ord_n(a)$".) After processing, for each element $p$ of $A[n \pmod{N}]$, remove $p$ from $A[n \pmod{N}]$ and insert $p$ to $A[(n + p) \pmod{N}]$.

This procedure gives you access to the prime factors of $n \le P$ that are smaller than $N$ in almost linear time. (As $N = \sqrt{P}$, any $n \le P$ may have at most one prime factor that is larger than $N$. Such a large prime factor is easy to determine given all other prime factors.)

Second, you want to compute $ord_p(a)$. With the method above you have access to the prime factorization of $p-1$. Then compute $ord_p(a)$ by computing for each prime $q$ the quantity $(q^{v_q(p-1)}, ord_p(a))$ -- that is, the ``$q$-part'' of $ord_p(a)$. This may be done as follows: Let $v = v_q(p-1)$. For each $e = 0, 1, \ldots , v$, check whether $$a^{(p-1)/q^e} \equiv 1 \pmod{p}.$$ If $E$ is the largest $e$ for which this holds, then $(q^{v_q(p-1)}, ord_p(a)) = q^{v - E}$.

Of course, you want to compute $a^{(p-1)/q^e}$ by fast exponentation (see https://en.wikipedia.org/wiki/Exponentiation_by_squaring). Multiplying the "$q$-part" of $ord_p(a)$ over all primes $q$ dividing $p-1$ then gives you $ord_p(a)$.

  • $\begingroup$ Would you be willing to share your implementation? I believe it would be extremely useful to continue this sequence: oeis.org/A359446 $\endgroup$
    – ordptt
    Mar 5 at 3:24
  • $\begingroup$ I've put up an implemenation here: pastebin.com/ap6MqrFH $\endgroup$ Mar 6 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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