Previous Page Next Page Contents

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

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




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000