| 126 | */ |
| 127 | template<typename F> |
| 128 | bool RecFindRoots(std::vector<std::vector<typename F::Elem>>& stack, size_t pos, std::vector<typename F::Elem>& roots, bool fully_factorizable, int depth, typename F::Elem randv, const F& field) { |
| 129 | auto& ppoly = stack[pos]; |
| 130 | // We assert ppoly.size() > 1 (instead of just ppoly.size() > 0) to additionally exclude |
| 131 | // constants polynomials because |
| 132 | // - ppoly is not constant initially (this is ensured by FindRoots()), and |
| 133 | // - we never recurse on a constant polynomial. |
| 134 | CHECK_SAFE(ppoly.size() > 1 && ppoly.back() == 1); |
| 135 | /* 1st degree input: constant term is the root. */ |
| 136 | if (ppoly.size() == 2) { |
| 137 | roots.push_back(ppoly[0]); |
| 138 | return true; |
| 139 | } |
| 140 | /* 2nd degree input: use direct quadratic solver. */ |
| 141 | if (ppoly.size() == 3) { |
| 142 | CHECK_RETURN(ppoly[1] != 0, false); // Equations of the form (x^2 + a) have two identical solutions; contradicts square-free assumption. */ |
| 143 | auto input = field.Mul(ppoly[0], field.Sqr(field.Inv(ppoly[1]))); |
| 144 | auto root = field.Qrt(input); |
| 145 | if ((field.Sqr(root) ^ root) != input) { |
| 146 | CHECK_SAFE(!fully_factorizable); |
| 147 | return false; // No root found. |
| 148 | } |
| 149 | auto sol = field.Mul(root, ppoly[1]); |
| 150 | roots.push_back(sol); |
| 151 | roots.push_back(sol ^ ppoly[1]); |
| 152 | return true; |
| 153 | } |
| 154 | /* 3rd degree input and more: recurse further. */ |
| 155 | if (pos + 3 > stack.size()) { |
| 156 | // Allocate memory if necessary. |
| 157 | stack.resize((pos + 3) * 2); |
| 158 | } |
| 159 | auto& poly = stack[pos]; |
| 160 | auto& tmp = stack[pos + 1]; |
| 161 | auto& trace = stack[pos + 2]; |
| 162 | trace.clear(); |
| 163 | tmp.clear(); |
| 164 | for (int iter = 0;; ++iter) { |
| 165 | // Compute the polynomial (trace(x*randv) mod poly(x)) symbolically, |
| 166 | // and put the result in `trace`. |
| 167 | TraceMod(poly, trace, randv, field); |
| 168 | |
| 169 | if (iter >= 1 && !fully_factorizable) { |
| 170 | // If the polynomial cannot be factorized completely (it has an |
| 171 | // irreducible factor of degree higher than 1), we want to avoid |
| 172 | // the case where this is only detected after trying all BITS |
| 173 | // independent split attempts fail (see the assert below). |
| 174 | // |
| 175 | // Observe that if we call y = randv*x, it is true that: |
| 176 | // |
| 177 | // trace = y + y^2 + y^4 + y^8 + ... y^(FIELDSIZE/2) mod poly |
| 178 | // |
| 179 | // Due to the Frobenius endomorphism, this means: |
| 180 | // |
| 181 | // trace^2 = y^2 + y^4 + y^8 + ... + y^FIELDSIZE mod poly |
| 182 | // |
| 183 | // Or, adding them up: |
| 184 | // |
| 185 | // trace + trace^2 = y + y^FIELDSIZE mod poly. |
no test coverage detected