2010/1/3 David Harvey <[email protected]>: > > > On Jan 3, 9:03 am, Bill Hart <[email protected]> wrote: > >> I figured I probably did misunderstand. What I think they are trying >> to get at is that one can use coefficients modulo 2^N+1 except at >> certain levels because the roots of unity are actually the same. But >> then the discussion becomes one of combining a Fermat and Mersenne >> transform, which is the basic strategy that the implementation uses. I >> got confused. I still am. > > I think they are saying that to multiply two integers whose product > has N bits, choose a and b (as in Lemma 1 of their paper) such that a > + b ~ N and then multiply modulo 2^a - 1 (use Mersenne transform) and > modulo 2^b + 1 (use Fermat transform). The smoothness comes from the > freedom to choose a and b.
Hmm, that's definitely not what I thought they meant. I thought their coefficients were modulo 2^a - 1 and 2^b + 1. How do they multiply modulo 2^b + 1? That sounds like a negacyclic convolution, not a Fermat transform. I can see why that would be less efficient than an ordinary cyclic convolution. You need twice as many roots of unity. > >> Sorry to be obtuse, but I am still confused. >> >> What is modulo 2^N - 1, the coefficients of the FFT? Or are we >> multiplying large integers modulo 2^N - 1. > > The latter. The former doesn't work as far as I know. Interesting. I have to confess I don't see the obstacle (except that as pointwise mults the divisibility properties might be difficult to meet). After all, you say above that the original integers are multiplied modulo 2^b - 1, so why not the pointwise mults. What just occurred to me is that perhaps their Mersenne transform effectively does the first layer or two of the pointwise mults, and that is how they are getting twice the length. Not sure. > >> Yes. It's an old idea. Jason Moxham implemented it many years ago, and >> I think this was one of the things he actually posted to the GMP list >> a few years before we started on FLINT. Dan Bernstein seemed to think >> the idea went back much further. > > OK. I don't know if the functions mpn_mulmod_2expp1 and mpn_mulmod_2expm1 that Jason implemented in MPIR actually do this or not. I didn't check yet. Anyhow, he claimed to have it working for not just 3, but 5 and any odd length for the p1 version and 2, etc, for the even version. > > david > > -- > > You received this message because you are subscribed to the Google Groups > "mpir-devel" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/mpir-devel?hl=en. > > > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
