| 74 | /** Compute the GCD of two polynomials, putting the result in a. b will be cleared. */ |
| 75 | template<typename F> |
| 76 | void GCD(std::vector<typename F::Elem>& a, std::vector<typename F::Elem>& b, const F& field) { |
| 77 | if (a.size() < b.size()) std::swap(a, b); |
| 78 | while (b.size() > 0) { |
| 79 | if (b.size() == 1) { |
| 80 | a.resize(1); |
| 81 | a[0] = 1; |
| 82 | return; |
| 83 | } |
| 84 | MakeMonic(b, field); |
| 85 | PolyMod(b, a, field); |
| 86 | std::swap(a, b); |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | /** Square a polynomial. */ |
| 91 | template<typename F> |