galois.poly_pow

galois.poly_pow(base_poly, exponent, modulus_poly)

Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f(x)^k\ \textrm{mod}\ g(x)\).

Parameters

  • base_poly (galois.Poly) – The polynomial to be exponentiated \(f(x)\).

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

  • modulus_poly (galois.Poly) – The reducing polynomial \(g(x)\).

Returns

The resulting polynomial \(h(x) = f(x)^k\ \textrm{mod}\ g(x)\).

Return type

galois.Poly

Notes

This function implements the Square-and-Multiply Algorithm for polynomials. The algorithm is more efficient than exponentiating first and then reducing modulo \(g(x)\), especially for very large exponents. Instead, this algorithm repeatedly squares \(f(x)\), reducing modulo \(g(x)\) at each step. This function is the polynomial equivalent of galois.pow().

References

Examples

In [1]: GF = galois.GF(31)

In [2]: f = galois.Poly.Random(10, field=GF); f
Out[2]: Poly(20x^10 + 16x^9 + 17x^8 + 3x^7 + 29x^6 + 24x^5 + 19x^4 + 5x^3 + 11x^2 + 3x + 4, GF(31))

In [3]: g = galois.Poly.Random(7, field=GF); g
Out[3]: Poly(2x^7 + 14x^6 + 2x^5 + 28x^4 + 22x^3 + 17x^2 + 22x + 15, GF(31))

# %timeit f**10_000 % g
# 2.61 s ± 339 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [4]: f**10_000 % g
Out[4]: Poly(26x^6 + 15x^5 + 12x^3 + 15x^2 + 5x + 8, GF(31))

# %timeit galois.poly_pow(f, 10_000, g)
# 9.88 ms ± 778 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
In [5]: galois.poly_pow(f, 10_000, g)
Out[5]: Poly(26x^6 + 15x^5 + 12x^3 + 15x^2 + 5x + 8, GF(31))