Documentation Center

  • Trial Software
  • Product Updates

powermod

Compute a modular power of a number or a polynomial

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

powermod(b, e, m)

Description

powermod(b, e, m) computes be mod m.

If b and m are numbers, the modular power be mod m can also be computed by the direct call b^e mod m. However, powermod(b, e, m) avoids the overhead of computing the intermediate result be and computes the modular power much more efficiently.

If b is a rational number, then the modular inverse of the denominator is calculated and multiplied with the numerator.

If the modulus m is an integer, then the base b must either be a number, a polynomial expression or a polynomial that is convertible to an IntMod(m)-polynomial.

If the modulus m is a polynomial expression, then the base b must either be a number, a polynomial expression or a polynomial over the coefficient ring of MuPAD® expressions.

If the modulus m is a polynomial of domain type DOM_POLY, then the base b must either be a number, or a polynomial of the same type as m or a polynomial expression that can be converted to a polynomial of the same type as m.

Note that the system function mod in charge of modular arithmetic may be changed by the user; see the help page of mod. The function powermod reacts accordingly. See Example 5.

Internally, polynomials are divided by the function divide.

Examples

Example 1

We compute 3^(123456) mod 7:

powermod(3, 123456, 7)

If the base is a rational number, the modular inverse of the denominator is computed and multiplied with the numerator:

powermod(3/5, 1234567, 7)

Example 2

The coefficients of the following polynomial expression are computed modulo 7:

powermod(x^2 + 7*x - 3, 10, 7)

Example 3

The power of the following polynomial expression is reduced modulo the polynomial x2 + 1:

powermod(x^2 + 7*x - 3, 10, x^2 + 1)

Example 4

The type of the return value coincides with the type of the base: a polynomial is returned if the base is a polynomial:

powermod(poly(x^2 + 7*x - 3), 2, x^2 + 1),
powermod(poly(x^2 + 7*x - 3), 2, poly(x^2 + 1))

If the base is a polynomial expression, powermod returns a polynomial expression:

powermod(x^2 + 7*x - 3, 2, x^2 + 1),
powermod(x^2 + 7*x - 3, 2, poly(x^2 + 1))

Example 5

The following re-definition of _mod switches to a symmetric representation of modular numbers:

R := Dom::IntegerMod(17):
_mod := mods: powermod(poly(2*x^2, R), 3, poly(3*x + 1, R))

The following command restores the default representation:

_mod := modp: powermod(poly(2*x^2, R), 3, poly(3*x + 1, R))

unalias(R):

Parameters

b

The base: an integer, a rational number, or a polynomial of type DOM_POLY, or a polynomial expression

e

The power: a nonnegative integer

m

The modulus: an integer (at least 2), or a polynomial of type DOM_POLY, or a polynomial expression

Return Values

Depending on the type of b, the return value is an integer, a polynomial, or a polynomial expression. FAIL is returned if an expression cannot be converted to a polynomial.

Overloaded By

b

See Also

MuPAD Functions

Was this topic helpful?