galois.pow

galois.pow(base, exponent, modulus)

Efficiently performs modular exponentiation.

Parameters

  • base (int, galois.Poly) – The integer or polynomial base \(a\).

  • exponent (int) – The non-negative integer exponent \(k\).

  • modulus (int, galois.Poly) – The integer or polynomial modulus \(m\).

Returns

The modular exponentiation \(a^k\ \textrm{mod}\ m\).

Return type

int, galois.Poly

Notes

This function implements the Square-and-Multiply Algorithm. The algorithm is more efficient than exponentiating first and then reducing modulo \(m\), especially for very large exponents. Instead, this algorithm repeatedly squares \(a\), reducing modulo \(m\) at each step.

References

Examples

Compute the modular exponentiation of an integer.

In [1]: galois.pow(3, 100, 7)
Out[1]: 4

In [2]: 3**100 % 7
Out[2]: 4

Compute the modular exponentiation of a polynomial.

In [3]: GF = galois.GF(7)

In [4]: a = galois.Poly.Random(3, field=GF)

In [5]: m = galois.Poly.Random(10, field=GF)

In [6]: galois.pow(a, 100, m)
Out[6]: Poly(6x^9 + 5x^8 + 5x^7 + 3x^6 + 2x^4 + 3x^3 + 5x + 1, GF(7))

In [7]: a**100 % m
Out[7]: Poly(6x^9 + 5x^8 + 5x^7 + 3x^6 + 2x^4 + 3x^3 + 5x + 1, GF(7))