Knuth–Eve algorithm: Difference between revisions

Revision as of 00:48, 31 July 2025

Revision as of 00:57, 31 July 2025

Line 41:

<math display="block"> p(x) = q(x) \cdot (x^2 - \alpha) + \gamma. </math>

<ref name="knuth1962"/><ref name="overill1997"/> This way, no operations are needed to compute the remainder polynomial, since it's just a constant. We apply this procedure [[Recursion (computer science)|recursively]] to <math>q</math>, expressing

<math display="block"> p(x) = \left( \left( q(x) \cdot (x^2 - \alpha_m) + \gamma_m \right) \cdots \right) \cdot (x^2 - \alpha_1) + \gamma_1. </math>