The ModularLog function computes the discrete logarithm of rationals under modular arithmetics. The base b discrete logarithm of a modulo n is a number $y$ such that $b^y=a\mathbf{mod}n$.

If a is not an integer, then the denominator of a must be relatively prime to the modulus n.

If the output option is not specified, then the return value is the smallest non-negative $y$, if it exists. An error message is displayed if $y$ does not exist.

If the output option is specified, then the return value is a sequence obtained from output by replacing each instance of $\mathrm{result}$ with $y$ and each instance of $\mathrm{char}$ or $\mathrm{characteristic}$ with a number $s$ such that for every non-negative integer $t$, $b^{st+y}=a\mathbf{mod}n$ and $s$ is minimal. Similarly, an error message is displayed if $y$ does not exist.

When the method option is not specified or set to $\mathrm{optimal}$, then the algorithm used is chosen automatically based on the size of the problem. Set method to $\mathrm{shanks}$ to force Shanks' Baby-Step Giant-Step algorithm. Set method to $\mathrm{indexcalculus}$ to force the Index Calculus algorithm.

$\mathrm{with}\left(\mathrm{NumberTheory}\right)\:$

$\mathrm{ModularLog}\left(9\,4\,11\right)$

$3$

$\mathrm{ModularLog}\left(5\,2\,7\right)$

Error, (in NumberTheory:-ModularLog) no solutions exist

$\mathrm{ModularLog}\left(17\,13\,101\,\mathrm{output}=\left[\mathrm{result}\,\mathrm{char}\right]\right)$

$5,50$

$\mathrm{infolevel}\left[\mathrm{ModularLog}\right]≔4$

${\mathrm{infolevel}}_{\mathrm{ModularLog}}≔4$

$\mathrm{ModularLog}\left(1441\,5\,10007\,\mathrm{method}=\mathrm{shanks}\right)$

ModularLog:   "using Shanks' method to compute log[25](1441) mod 10007"

$5000$

$\mathrm{ModularLog}\left(1441\,5\,10007\,\mathrm{method}=\mathrm{indexcalculus}\right)$

ModularLog:   "using the index calculus method to compute log[5](1441) mod 10007"
ModularLog:   "found new equation 1 out of 4"
ModularLog:   "found new equation 2 out of 4"
ModularLog:   "found new equation 3 out of 4"
ModularLog:   "found new equation 4 out of 4"

$5000$

$\mathrm{ModularLog}\left(\frac{2}{3}\,6\,41\right)$

$11$

The NumberTheory[ModularLog] command was introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.