powermod
-- compute a modular
power of a number or a polynomialpowermod(
b, e, m)
computes b^e mod
m.
powermod(b, e, m)
b |
- | the base: a number, or a polynomial of type DOM_POLY , or a polynomial expression |
e |
- | the power: a nonnegative integer |
m |
- | the modulus: a number, or a polynomial of type DOM_POLY , or a polynomial expression |
Depending on the type of b
, the return value is a
number, a polynomial or a polynomial expression. FAIL
is returned if an expression
cannot be converted to a polynomial.
b
_mod
, divide
, modp
, mods
, poly
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.b
is a rational number, then the modular inverse of
the denominator is calculated and multiplied with the numerator.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.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.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
._mod
in charge of modular arithmetic
may be changed by the user; see the help page of _mod
. The function
powermod
calls _mod
and reacts accordingly. Cf.
example 5.divide
.We compute 3^123456 mod 7:
>> powermod(3, 123456, 7)
1
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)
2
The coefficients of the following polynomial expression are computed modulo 7:
>> powermod(x^2 + 7*x - 3, 10, 7)
2 4 6 14 16 18 20 3 x - x - 3 x + x - x - 2 x + x - 3
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)
1029668584 x - 534842913
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))
poly(- 56 x - 33, [x]), poly(- 56 x - 33, [x])
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))
- 56 x - 33, - 56 x - 33
The following re-definition of _mod
switches to a symmetric
representation of modular numbers:
>> alias(R = Dom::IntegerMod(17)): _mod := mods: powermod(poly(2*x^2, R), 3, poly(3*x + 1, R))
poly(-4, [x], R)
The following command restores the default representation:
>> _mod := modp: powermod(poly(2*x^2, R), 3, poly(3*x + 1, R))
poly(13, [x], R)
>> unalias(R):