## `powermod` -- compute a modular power of a number or a polynomial

#### Introduction

`powermod(`b, e, m`)` computes b^e mod m.

#### Call(s)

`powermod(b, e, m)`

#### Parameters

`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

#### Returns

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.

### Overloadable:

`b`

#### Related Functions

`_mod`, `divide`, `modp`, `mods`, `poly`

#### Details

- 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` calls `_mod` and reacts accordingly. Cf. example 5.
- Internally, polynomials are divided by the function `divide`.

#### Example 1

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

#### Example 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

#### Example 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

#### 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))

                  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 5

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):

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000