discrete logarithm under modular arithmetics
ModularLog(a, b, n, output = o, method = m)
output = o
(optional) keyword argument where o is a list of the names result, char, characteristic
method = m
(optional) keyword argument where m is one of the names optimal, shanks, indexcalculus
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 by=amodn.
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 result with y and each instance of char or characteristic with a number s such that for every non-negative integer t, bs⁢t+y=amodn 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 optimal, then the algorithm used is chosen automatically based on the size of the problem. Set method to shanks to force Shanks' Baby-Step Giant-Step algorithm. Set method to indexcalculus to force the Index Calculus algorithm.
ModularLog(9, 4, 11);
Since 5 does not have a base 2 logarithm modulo 7, an error message is displayed.
ModularLog(5, 2, 7);
Error, (in NumberTheory:-ModularLog) no solutions exist
ModularLog(17, 13, 101, output = [result, char]);
If infolevelModularLog is set to 2 or greater, userinfo messages will be printed. The ModularLog function prints messages at levels 2 and 4.
infolevel[ModularLog] := 4;
ModularLog(1441, 5, 10007, method = shanks);
ModularLog: "using Shanks' method to compute log(1441) mod 10007"
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"
ModularLog( 2/3, 6, 41 );
The NumberTheory[ModularLog] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document
What kind of issue would you like to report? (Optional)