galois.poly_exp_mod

galois.poly_exp_mod(poly, power, modulus)[source]

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

The algorithm is more efficient than exponentiating first and then reducing modulo \(g(x)\). Instead, this algorithm repeatedly squares \(f\), reducing modulo \(g\) at each step.

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 [1]: GF = galois.GF(31)

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

In [3]: g = galois.Poly.Random(7, field=GF); g
Out[3]: Poly(12x^7 + 2x^6 + 15x^4 + 27x^3 + 9x^2 + 30x + 15, GF(31))

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

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