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

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 + 3x^8 + 2x^7 + 3x^6 + x^5 + 5x^4 + 5x^3 + 6x^2 + 4, GF(7))

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