next up previous
Next: Hensel Lifting Up: Division with remainder using Newton Previous: Modular inverses using Newton iteration

Division with remainder using Newton iteration

Algorithm 7  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $a,b \in ...
...\> $r$\ := $a - b \, q$\ \\
\> {\bf return} $(q,r)$\end{tabbing}\end{minipage}}


Theorem 11   Let R be a commutative ring with unity. Let a and b be univariate polynomials over R with respective degrees n and m such that n $ \geq$ m $ \geq$ 0 and b $ \neq$ 0 monic. Algorithm 7 computes the quotient and the remainder of a w.r.t. b in $ \bf M$(n - m) + $ \bf M$(m) + $ \cal {O}$(m) operations in R


Proof. We do not give here a proof and we refer to Theorem 9.5 in [vzGG99]. However, roughly speaking, Algorithm 7 consists essentially in $ \qedsymbol$


Remark 15   If several divisions by a given b needs to be performed then we may precompute the inverse of revm(b) modulo some powers x, x2,... of x. Assuming that R possesses suitable primitive roots of unity ee can also save their DTF.


next up previous
Next: Hensel Lifting Up: Division with remainder using Newton Previous: Modular inverses using Newton iteration
Marc Moreno Maza
2003-06-06