I need a fast way to get the remainder from the division of two polynomials in c++. In "Modern Computer Algebra 3rd Edition" i found in the chapter 9 this pseudocode for the division using newton iteration:
if deg a < deg b then return q = 0 and r = a
m <− deg a − deg b
call Algorithm 9.3 to compute the inverse of rev(b) ∈ D[x] rem x^(m+1)
3. q∗ <− rev(a) · rev(b)^-1 mod x^(m+1)
4. return q = rev(q∗) and r = a − b*q
This is pretty straight forward but the thing I can't understand is the algorithm 9.3:
g0 <− 1, r <− log2 l
for i = 1, . . . , r do gi <− (2(gi−1) − f*(gi−1)^2) rem x^2^i
return gr
in algorithm 9.3 to compute
rem x^2^i
we need to divide (2(gi−1) − f*(gi−1)^2) by x^2^i
and keep the remainder, but this would require again the algorithm for the division. now i have two questions: how can i get the remainder
in algorithm 9.3 (f is a polynomial)? in the algorithm 9.3 should it be rem x^(m+1)?
Thanks