improved Montgomery multiplication
Philip McLaughlin
pbmcl@netscape.net
Fri, 20 Jun 2003 19:58:20 -0700
--------------080902090507030906000202
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 8bit
Dear Dr. Harley,
Sorry, guess again! :-)
I haven't tested the techniques described in the paper myself, so I
don't know how practical they will be. It is unlikely that anyone has
programmed any of them yet, since the paper was only posted May 7.
Regards to all,
Phil McLaughlin
harley@argote.ch wrote:
>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.
> .-. .-.
> / \ .-. .-. / \
> / \ / \ .-. _ .-. / \ / \
> / \ / \ / \ / \ / \ / \ / \
> / \ / \ / `-' `-' \ / \ / \
> \ / `-' `-' \ /
> `-' `-'
>
>
--------------080902090507030906000202
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=ISO-8859-1">
<title></title>
</head>
<body>
Dear Dr. Harley,<br>
<br>
Sorry, guess again! :-)<br>
<br>
I haven't tested the techniques described in the paper myself, so I don't
know how practical they will be. It is unlikely that anyone has programmed
any of them yet, since the paper was only posted May 7.<br>
<br>
Regards to all,<br>
Phil McLaughlin<br>
<br>
<a class="moz-txt-link-abbreviated" href="mailto:harley@argote.ch">harley@argote.ch</a> wrote:<br>
<blockquote type="cite" cite="mid20030620150501.B6E73C454@argote.ch">
<pre wrap="">Hi Paul,
You wrote:
</pre>
<blockquote type="cite">
<pre wrap="">did somebody out there implement Phil McLaughlin's new frameworks
for Montgomery multiplication in gmp? It just appeared in Math of Comp
<a class="moz-txt-link-rfc2396E" href="http://www.ams.org/journal-getitem?pii=S0025-5718-03-01543-6"><http://www.ams.org/journal-getitem?pii=S0025-5718-03-01543-6></a>.
</pre>
</blockquote>
<pre wrap=""><!---->
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.
.-. .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' `-'
</pre>
</blockquote>
<br>
</body>
</html>
--------------080902090507030906000202--