On Jan 3, 9:03 am, Bill Hart <goodwillh...@googlemail.com> 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. > 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. > 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. david -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-de...@googlegroups.com. To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en.
