Return the polynomial (quotient, remainder) of poly divided by mod.
(poly, mod, gf)
| 195 | return [gf.mul(inv, v) for v in poly] |
| 196 | |
| 197 | def poly_divmod(poly, mod, gf): |
| 198 | """Return the polynomial (quotient, remainder) of poly divided by mod.""" |
| 199 | assert len(mod) > 0 and mod[-1] == 1 # Require monic mod. |
| 200 | if len(poly) < len(mod): |
| 201 | return ([], poly) |
| 202 | val = list(poly) |
| 203 | div = [0 for _ in range(len(val) - len(mod) + 1)] |
| 204 | while len(val) >= len(mod): |
| 205 | term = val[-1] |
| 206 | div[len(val) - len(mod)] = term |
| 207 | # If the highest coefficient in val is nonzero, subtract a multiple of mod from it. |
| 208 | val.pop() |
| 209 | if term != 0: |
| 210 | for x in range(len(mod) - 1): |
| 211 | val[1 + x - len(mod)] ^= gf.mul(term, mod[x]) |
| 212 | # Prune trailing zero coefficients. |
| 213 | while len(val) > 0 and val[-1] == 0: |
| 214 | val.pop() |
| 215 | return div, val |
| 216 | |
| 217 | def poly_gcd(a, b, gf): |
| 218 | """Return the polynomial GCD of a and b.""" |
no test coverage detected