| 36 | /** Compute the quotient of a polynomial division of val by mod, putting the quotient in div and the remainder in val. */ |
| 37 | template<typename F> |
| 38 | void DivMod(const std::vector<typename F::Elem>& mod, std::vector<typename F::Elem>& val, std::vector<typename F::Elem>& div, const F& field) { |
| 39 | size_t modsize = mod.size(); |
| 40 | CHECK_SAFE(mod.size() > 0 && mod.back() == 1); |
| 41 | if (val.size() < mod.size()) { |
| 42 | div.clear(); |
| 43 | return; |
| 44 | } |
| 45 | CHECK_SAFE(val.back() != 0); |
| 46 | div.resize(val.size() - mod.size() + 1); |
| 47 | while (val.size() >= modsize) { |
| 48 | auto term = val.back(); |
| 49 | div[val.size() - modsize] = term; |
| 50 | val.pop_back(); |
| 51 | if (term != 0) { |
| 52 | typename F::Multiplier mul(field, term); |
| 53 | for (size_t x = 0; x < mod.size() - 1; ++x) { |
| 54 | val[val.size() - modsize + 1 + x] ^= mul(mod[x]); |
| 55 | } |
| 56 | } |
| 57 | } |
| 58 | } |
| 59 | |
| 60 | /** Make a polynomial monic. */ |
| 61 | template<typename F> |