NumberTheory - Maple Programming Help

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

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{ModularLog}\left(9,4,11\right)$
 ${3}$ (1)

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

 > $\mathrm{ModularLog}\left(5,2,7\right)$
 > $\mathrm{ModularLog}\left(17,13,101,\mathrm{output}=\left[\mathrm{result},\mathrm{char}\right]\right)$
 ${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$.

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

Compatibility

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