The current logic for IntegerModRing_abstract.log() is as follows:

1. If logarithm_exists=True was passed: Call Pari's znlog with just the elements.
2. Else, if the modulus is prime: Compute the orders of a,b and (if the logarithm exists) call Pari's znlog with the elements and the order of b.
3. Else, use generic discrete_log (i.e., Pohlig–Hellman).

The main reason things are done like this appears to be that znlog is not guaranteed to terminate if the logarithm doesn't exist, and checking if it exists is not straightforward when the ambient group is non-cyclic. Since we're already at it, here's what Pari does in znlog:

1. If the order of the base element is given, factor it and use Pohlig–Hellman.
2. Else, factor the modulus and solve each prime-power part separately using either index calculus (if p is a suitable prime) or Pohlig–Hellman with either BSGS or Pollard ρ for the base cases (depending on size).

We really shouldn't resort to generic discrete_log() right away if the modulus isn't prime: While indeed (ℤ/n)* is usually non-cyclic, we can typically reduce to the cyclic case using CRT, which we can then pass on to Pari after checking that the logarithm exists (by comparing orders). This patch takes care of this.

Summary of the new algorithm:

1. Factor the modulus.
2. Solve the problem modulo each prime power separately:
   1. Modulo powers of two, use Sage's discrete_log.
   2. Modulo odd prime powers, check that the logarithm exists and call Pari's znlog.
3. Use CRT to combine the local solutions.

The reason to treat powers of two differently is that this is the only case where the unit group is not always cyclic, hence we might run into Pari's infinite loop when no solution exists (side note: I'm not sure if this can actually happen, but of course we should rely only on documented behaviour). Since 2-groups are a very easy case for generic discrete_log(), we simply deal with that in Sage instead of risking the infinite loop. In all other cases, unit groups modulo prime powers are cyclic, hence we can safely call Pari after checking the orders.

I know factoring the modulus looks scary, but let me point out that we're already doing that in all cases:

• If logarithm_exists=True is given, the order is factored in Pari first thing.
• Else, we are computing the orders of elements in Sage, which requires first factoring the group order.

The new doctests introduced in the patch are cases where the old algorithm would take a very long time (if it managed to finish at all without getting killed for lack of memory), whereas the new algorithm takes much less than a second. I also tested the old and new code with thousands of random DLPs modulo (1) random integers, and (2) primes, of sizes up to 2^64, and there didn't appear to be any noticeable performance degradation even in the previous best case of prime moduli. For composite integers, the new code is unsurprisingly a lot faster on average.

I found out about the current, suboptimal implementation here: https://web.archive.org/web/20210813155145/https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled

CC: @JohnCremona @kwankyu @defeo @edgarcosta @kedlaya

Component: number theory

Keywords: discrete logarithms, finite rings, composite characteristic

Author: Lorenz Panny

Branch/Commit: d866118

Reviewer: Travis Scrimshaw, Edgar Costa

Issue created by migration from https://trac.sagemath.org/ticket/32375