improved Montgomery multiplication

[Dr. Robert J. Harley]

Hi Paul,

You wrote:
>did somebody out there implement Phil McLaughlin's new frameworks
>for Montgomery multiplication in gmp? It just appeared in Math of Comp
><http://www.ams.org/journal-getitem?pii=S0025-5718-03-01543-6>.

There's no detail in the abstract, but I guess that he suggests doing
modular multiplication by precomputing inverses with 2^(k*2^n)+1 and
using Schönhage-style multiplication for integers, or with x^(k*2^n)+1
and using Nussbaumer-style multiplication for polynomials, instead of
the most practical cases of 2^N or x^N.  Montgomery's original paper
did not restrict to the latter cases so I am not sure why this is a
"new framework".  To answer your question, I played with some trivial
examples in GP a few years ago but never wrote a proper
implementation... sorry.

PS: Maybe I'm mistaken and there is something great in the article;
    I'll read it to find out next time I'm in an appropriate library! :)

Regards,
  Rob.
     .-.                                                               .-.
    /   \           .-.                                 .-.           /   \
   /     \         /   \       .-.     _     .-.       /   \         /     \
  /       \       /     \     /   \   / \   /   \     /     \       /       \
 /         \     /       \   /     `-'   `-'     \   /       \     /         \
            \   /         `-'                     `-'         \   /
             `-'                                               `-'