# improved Montgomery multiplication

**Dr. Robert J. Harley
**
harley@argote.ch

*Fri, 20 Jun 2003 17:05:01 +0200 (CEST)*

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.
.-. .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' `-'