galois.poly_exp_mod

galois.poly_exp_mod(poly, power, modulus)

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

In [435]: f = galois.Poly.Random(10, field=GF); f
Out[435]: Poly(13x^10 + 27x^9 + 14x^8 + 7x^7 + 29x^6 + 23x^4 + 28x^3 + 4x^2 + 27x + 3, GF(31))

In [436]: g = galois.Poly.Random(7, field=GF); g
Out[436]: Poly(16x^7 + 14x^6 + 17x^5 + 26x^4 + 5x^3 + 20x^2 + 20x + 23, GF(31))

# %timeit f**200 % g
# 1.23 s ± 41.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
In [437]: f**200 % g
Out[437]: Poly(4x^6 + 16x^5 + 4x^4 + 3x^3 + 3x^2 + 13x + 19, 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 [438]: galois.poly_exp_mod(f, 200, g)
Out[438]: Poly(4x^6 + 16x^5 + 4x^4 + 3x^3 + 3x^2 + 13x + 19, GF(31))