Direct division in factor rings
Patrick M. Fitzpatrick, C. Wolf · Electronics Letters · 2002
Conventional techniques for division in the polynomial factor ring [z]/〈m〉 or the integer ring ℤn use a combination of inversion and multiplication. A new algorithm is presented that computes the division directly and therefore eliminates the multiplication step. The algorithm requires 2 degree(m) (resp. 2 log2 n) steps, each of which uses only shift and multiply-subtract operations.