Important: The numtheory package has been deprecated.  Use the superseding command NumberTheory[ModularLog] instead.

The function mlog computes the discrete logarithm  (also called the index) of x to the base a (mod n). It finds an integer y such that $a^y=x\mathbf{mod}n$ if possible, otherwise it returns FAIL.

When the optional argument c is provided, it is to be the fourth argument. If c is present in the calling sequence, the characteristic of the domain of the answer will be assigned to it. In this case all of the solutions to the logarithm are mlog(x, a, n) + k * c for any non-negative integer k.

When the optional argument m is provided, it must be the final argument in the calling sequence.  This argument indicates the solution method that the user wishes to be employed.  There are three possible choices for this parameter: method=shanks, which forces Shanks' Baby-Step Giant-Step algorithm to be employed in solving mlog(x, a, n); method=indcalc, which forces mlog(x, a, n) to employ the use of the Index Calculus method; or method=optimal, which automatically chooses the method based on the size of the problem.  If no method is specified by the user, the default is method=optimal.

If x and n are coprime and a is a primitive root of n, then there is a unique solution of logarithm of x to the base a modulo phi(n).

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

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

$3$

$\mathrm{mlog}\left(5\,2\,7\,'c'\right)$

$\mathrm{FAIL}$

$c$

$3$

$x≔\mathrm{mlog}\left(17\,13\,101\,'c'\right)$

$x≔5$

$\mathrm{print}\left(\mathrm{`all\; the\; solutions\; of\; logarithm\; are`}\right)$

$\mathrm{all\; the\; solutions\; of\; logarithm\; are}$

$x+c'k'$

$5+50k$

$\mathrm{\phi }\left(101\right)$

$100$

$\mathrm{index}\left(15\,\mathrm{primroot}\left(47\right)\,47\,'c'\right),c$

$21,46$

$\mathrm{\phi }\left(47\right)$

$46$

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

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

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

mlog:   "using Shanks method to compute log[a](x) mod p"
mlog:   "where n=10007, a=25, and x=1441."

$5000$

$\mathrm{mlog}\left(1441\,5\,10007\,\mathrm{method}=\mathrm{indcalc}\right)$

mlog:   "using the indexed calculus method to compute log[a](x) mod n"
mlog:   "where n=10007, a=5, and x=1441."
mlog:   "found new equation 1 out of 4"
mlog:   "found new equation 2 out of 4"
mlog:   "found new equation 3 out of 4"
mlog:   "found new equation 4 out of 4"

$5000$