Search code examples
maplemodular-arithmetic

Solving modular equations in maple

I want to ask Maple, for example, for which j the following is true:

10^j mod 543 = 82

How can I ask Maple this?

Also, is there a way to solve for j without a computer?

Solution

  • This is called the The Discrete Logarithm Problem. It is a difficult problem---computationally intensive. See the Wikipedia page. It has discussion of eight algorithms for the problem. The Maple command is numtheory:-mlog.

    numtheory:-mlog(82, 10, 543);

    Maple responds

     12

    To obtain all such integers j, use the extended form of the command:

    numtheory:-mlog(82, 10, 543, 'c');

    Maple again responds with 12, and c is set to 180, meaning that j = 12 + 180*k is a solution for any nonnegative integer k.