galois.poly_pow

class galois.poly_pow(poly, power, modulus)

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

The algorithm is more efficient than exponentiating first and then reducing modulo \(g(x)\). Instead, this algorithm repeatedly squares \(f(x)\), reducing modulo \(g(x)\) at each step. This is the polynomial equivalent of galois.pow().

Parameters

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

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

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

Returns

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

Return type

galois.Poly

Examples

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

In [602]: f = galois.Poly.Random(10, field=GF); f
Out[602]: Poly(25x^10 + 7x^9 + 25x^8 + 26x^7 + 25x^6 + 24x^5 + 2x^4 + 26x^3 + 2x + 13, GF(31))

In [603]: g = galois.Poly.Random(7, field=GF); g
Out[603]: Poly(27x^7 + 29x^6 + 2x^5 + 4x^4 + 8x^3 + 4x^2 + 14x + 3, GF(31))

# %timeit f**200 % g
# 1.23 s ± 41.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [604]: f**200 % g
Out[604]: Poly(30x^6 + 23x^5 + 29x^4 + 9x^3 + 15x^2 + 17x + 11, GF(31))

# %timeit galois.poly_pow(f, 200, g)
# 41.7 ms ± 468 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
In [605]: galois.poly_pow(f, 200, g)
Out[605]: Poly(30x^6 + 23x^5 + 29x^4 + 9x^3 + 15x^2 + 17x + 11, GF(31))