Montgomery Reduction for GF(2)[x] ?

From: Tom St Denis (tomstdenis_at_iahu.ca)
Date: 05/31/03 

Date: Sat, 31 May 2003 01:33:04 GMT

I was just thinking. Wouldn't Montgomery reduction also work for
polynomials in GF(2)[x] ? Consider an odd polynomial v(x) and a
polynomial you want to reduce p(x).

1. for t from 1 to k do
2. if the lsb of p(x) is one then
3. p(x) = p(x) + v(x)
4. p(x) = p(x) / x

The result is congruent to p(x) modulo v(x) times x^{-k} so you can use
the same Montgomery tricks.

The algorithm only requires XOR and right shift operations and of course
can be optimized to use multiple bits [a byte driven algorithm would be
fast] at a time.

Now I'm certain I'm not the first to propose this but in all of the
papers I've read I have never seen it proposed. Is this one of those
"no duh" ideas or just not very many people have thought of this?

Tom

Relevant Pages

  • Re: multiple.....
    ... ad is multiple of u. ... So any u in Z that divides rsmust divide rs. ... and if f,g are monic polynomials in Ksuch that fg is in Dthen ... Contents of polynomials and invertibility, ...
    (sci.math)
  • Re: decomposition of polynomials
    ... So now if x is any root of f, it makes the product of these two ... Don't forget that you can throw away any multiple of f. ... polynomials g and h with f | g o h, then any root x of f ... So the field extension can be done in two steps, ...
    (sci.math)
  • Re: derivatives and determinant
    ... Simplify the entries of A to polynomials. ... f is a multiple of p. ... the column swap negates it again so detremains unchanged. ... of the product of generalized diagonals. ...
    (sci.math)
  • Re: JSH: Fool all of the people, all of the time?
    ... > find easily works to provoke confusion. ... that is a multiple of 2. ... there's really any difference between talking about polynomials *as* ... here, and it only mentions algebraic integers very briefly, in the ...
    (sci.math)
  • JSH: Key insight, algebra
    ... The mathematics handles ALL CASES as notice all I've done really is ... multiples of polynomials were these trivial ... If you use a multiple as I have, you can see how factors distribute ... how it divides off. ...
    (sci.math)