Compute a modular power of a number or a polynomial
This functionality does not run in MATLAB.
powermod(b
, e
, m
)
powermod(b, e, m)
computes b^{e} mod m.
If b
and m
are numbers,
the modular power b^{e} 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 b^{e} 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
.
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)
The coefficients of the following polynomial expression are computed modulo 7:
powermod(x^2 + 7*x  3, 10, 7)
The power of the following polynomial expression is reduced modulo the polynomial x^{2} + 1:
powermod(x^2 + 7*x  3, 10, x^2 + 1)
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))
The following redefinition 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):

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

The power: a nonnegative integer 

The modulus: an integer (at least 2),
or a polynomial of
type 
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.
b