DLOG

This function computes the discrete logarithm x such that b^x \equiv a \pmod n, when a solution exists.

The problem is:

b^x \equiv a \pmod n

Discrete logarithms are fundamental in computational number theory and cryptography. The implementation uses SymPy’s internal strategy selection across algorithms such as baby-step giant-step and Pohlig-Hellman.

Excel Usage

=DLOG(n, a, b, order, prime_order)
  • n (int, required): Modulus of the congruence.
  • a (int, required): Target residue value.
  • b (int, required): Base of exponentiation.
  • order (int, optional, default: null): Optional order of the subgroup containing the base.
  • prime_order (bool, optional, default: null): Whether the subgroup order is known to be prime.

Returns (int): Exponent x satisfying b**x ≡ a (mod n).

Example 1: Discrete logarithm documented example

Inputs:

n a b order prime_order
41 15 7

Excel formula:

=DLOG(41, 15, 7, , )

Expected output:

3

Example 2: Discrete logarithm modulo a small prime

Inputs:

n a b order prime_order
17 13 3

Excel formula:

=DLOG(17, 13, 3, , )

Expected output:

4

Example 3: Discrete logarithm with power of two exponent

Inputs:

n a b order prime_order
29 16 2

Excel formula:

=DLOG(29, 16, 2, , )

Expected output:

4

Example 4: Discrete logarithm using provided subgroup order

Inputs:

n a b order prime_order
17 4 2 8

Excel formula:

=DLOG(17, 4, 2, 8, )

Expected output:

2

Python Code

from sympy import discrete_log as sympy_discrete_log

def dlog(n, a, b, order=None, prime_order=None):
    """
    Solve discrete logarithms in modular arithmetic.

    See: https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.residue_ntheory.discrete_log

    This example function is provided as-is without any representation of accuracy.

    Args:
        n (int): Modulus of the congruence.
        a (int): Target residue value.
        b (int): Base of exponentiation.
        order (int, optional): Optional order of the subgroup containing the base. Default is None.
        prime_order (bool, optional): Whether the subgroup order is known to be prime. Default is None.

    Returns:
        int: Exponent x satisfying b**x ≡ a (mod n).
    """
    try:
        return int(sympy_discrete_log(n, a, b, order=order, prime_order=prime_order))
    except Exception as e:
        return f"Error: {str(e)}"

Online Calculator

Modulus of the congruence.
Target residue value.
Base of exponentiation.
Optional order of the subgroup containing the base.
Whether the subgroup order is known to be prime.