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

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.

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

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