 NumberTheory - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Basic Mathematics : Logarithms : NumberTheory/ModularLog

NumberTheory

 ModularLog
 discrete logarithm under modular arithmetics

 Calling Sequence ModularLog(a, b, n, output = o, method = m)

Parameters

 a - rational b - integer n - positive integer output = o - (optional) keyword argument where o is a list of the names $\mathrm{result}$, $\mathrm{char}$, $\mathrm{characteristic}$ method = m - (optional) keyword argument where m is one of the names $\mathrm{optimal}$, $\mathrm{shanks}$, $\mathrm{indexcalculus}$

Description

 • 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\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}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\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.3em}{0.0ex}}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.

Examples

 > with(NumberTheory):
 > ModularLog(9, 4, 11);
 ${3}$ (1)

Since $5$ does not have a base $2$ logarithm modulo $7$, an error message is displayed.

 > ModularLog(5, 2, 7);
 > ModularLog(17, 13, 101, output = [result, char]);
 ${5}{,}{50}$ (2)

If ${\mathrm{infolevel}}_{\mathrm{ModularLog}}$ is set to $2$ or greater, userinfo messages will be printed. The ModularLog function prints messages at levels $2$ and $4$.

 > infolevel[ModularLog] := 4;
 ${{\mathrm{infolevel}}}_{{\mathrm{ModularLog}}}{≔}{4}$ (3)
 > ModularLog(1441, 5, 10007, method = shanks);
 ModularLog:   "using Shanks' method to compute log(1441) mod 10007"
 ${5000}$ (4)
 > ModularLog(1441, 5, 10007, method = indexcalculus);
 ModularLog:   "using the index calculus method to compute log(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}$ (5)
 > ModularLog( 2/3, 6, 41 );
 ${11}$ (6)

Compatibility

 • The NumberTheory[ModularLog] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.

 See Also