galois.poly_pow¶
- 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
Examples
In [1]: GF = galois.GF(31) In [2]: f = galois.Poly.Random(10, field=GF); f Out[2]: Poly(22x^10 + 17x^9 + 18x^7 + 9x^6 + 13x^5 + 5x^4 + 8x^3 + 13x^2 + 9x + 28, GF(31)) In [3]: g = galois.Poly.Random(7, field=GF); g Out[3]: Poly(10x^7 + 3x^6 + x^5 + 19x^4 + 24x^3 + 4x^2 + 13x + 19, 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(x^6 + 3x^4 + 23x^3 + 15x^2 + 29x + 16, 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 [5]: galois.poly_pow(f, 200, g) Out[5]: Poly(x^6 + 3x^4 + 23x^3 + 15x^2 + 29x + 16, GF(31))