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

Parameters

Description

Examples

Compatibility

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 result, char, characteristic

method = m

-

(optional) keyword argument where m is one of the names optimal, shanks, 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 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, bst+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.

Examples

withNumberTheory:

ModularLog9,4,11

3

(1)

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

ModularLog5,2,7

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

ModularLog17,13,101,output=result,char

5,50

(2)

If infolevelModularLog is set to 2 or greater, userinfo messages will be printed. The ModularLog function prints messages at levels 2 and 4.

infolevelModularLog4

infolevelModularLog4

(3)

ModularLog1441,5,10007,method=shanks

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

5000

(4)

ModularLog1441,5,10007,method=indexcalculus

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)

ModularLog23,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

NumberTheory

NumberTheory[PrimitiveRoot]