Does it help to use that the multiplicative group Z/nZ is isomorphic to the direct product Z/(p_1^e_1 Z) x Z/(p_2^e_2 Z) x ... x Z/(p_k^e_k Z) where n = p_1^e_1 * p_2^e_2 * ... * p_k^e_k ? In other words, you can do the computation in each group Z/(p_i^e_i Z) separately (parallelism, hooray!) and then use the Chinese Remainder Theorem (CRT) at the end. See Section 1.4 "The Legendre Symbol" in Henri Cohen's wonderful book "A Course in Computational Algebraic Number Theory". This book also talks about the CRT (Section 1.3.3). I did not even attempt to check whether there is something that makes this impossible or infeasible for the discrete log problem. Best regards, jj * Henry Baker <hbaker1@pipeline.com> [Dec 29. 2019 06:06]:
I've been playing around with arithmetic mod a composite number, and I needed to extend discrete logs to the entire set -- not just those elements representable as g^i for some primitive root g.
[...]