"Efficient" way to build a table of multiplicative orders modulo $p$ of a fixed integer $a$

Question

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.

Answer 1

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.

Answer 2

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