Marco Bodrato <bodr...@mail.dm.unipi.it> writes:
> Nothing special...
> Simply, if a multiplication mod B^{3n}+1 is needed, the code computes
> - a product mod B^{n}+1
> - a product mod B^{2n}-B^{n}+1
> - with CRT, the desired result is obtained.
Ok, and can the second product be computed more efficiently than full
product + mod operation?
> This is generalised for multiplications mod B^{kn}+1 for k in
> {3,5,7,13,17}.
Intuitively, I'd expect the gain is largest for k = 3 (since for larger
k, we get even further away from splitting in half). Is that right?
> If a product mod B^64-1 is required to mulmod_bnm1, then the function
> computes two multiplications: mod B^32-1, and mod B^32+1.
> Computing a product mod B^33+1 is now faster than computing mod
> B^32+1...
> ...but the product mod B^33+1 is simply not useful, the calling
> function needs the result mod B^32+1!
It seems a bit tricky to take this into account in
mpn_mulmod_bnm1_next_size, but maybe it's doable?
E.g, in this case we could try a top-level B^66 - 1 product, split in
B^33+1 and B^33-1; then the former suits your new algorithm well, but
the former can't be recursively split (at least not on a B boundary). If
we go up to B^72-1, this would split as (B^36+1)(B^18+1)(B^9+1)(B^9-1),
where B^9-1 can't be easily split, but the other factors are of the
requied form B^{3n}+1.
And we also have mpn_fft_next_size, but I'm not familiar with how that
works.
Regards,
/Niels
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
_______________________________________________
gmp-devel mailing list
gmp-devel@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-devel
