powermod -- compute a modular
power of a number or a polynomial
Introductionpowermod(b, e, m) computes b^e mod
m.
Call(s)powermod(b, e, m)
Parametersb |
- | 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 |
ReturnsDepending 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
Related
Functions_mod, divide, modp, mods, poly
Detailsb 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.
Example
1We 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
Example
2The 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
Example
3The 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
Example
4The 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
Example
5The 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):