David Harvey d.har...@unsw.edu.au writes:
I guess you could mitigate this a bit by rounding u up to get a
polynomial with reasonably low weight.
Yes, but doesn't this miss the whole point???
You could round up so you get at most, say, three factors (x^{2^k_j} -
1). That should reduce the
David Harvey d.har...@unsw.edu.au writes:
It is possible to do everything using the polynomial f(x) you suggest
above (in this case the factorisation does lift to Z[x]), and I think
this may have been what I tried first.
But it has a few disadvantages:
(1) the bit bounds for the
On 04/04/2014, at 4:28 AM, Niels Möller ni...@lysator.liu.se wrote:
(1) the bit bounds for the coefficients get worse. For example if u =
5 then f(x) = x^5 + x^4 + x + 1, so when you compute say a(x) b(x) mod
f(x) (in Z[x]), every coefficient in the result is a sum of up to
*five* terms from
/mul_spfft.c
in the next major GMP release. Perhaps this would make mpn_mulmod_bnm1
trickier to maintain (at least as a cutting-edge primitive)?
I must admit that I don't recall the exact operation of the small primes
code. Each separate polynomial multiply should compute a convoluttion
as usually
Torbjorn Granlund t...@gmplib.org writes:
We should integrate the small primes FFT code,
https://gmplib.org/repo/gcd-nisse/file/0d591aa7e02c/mpn/generic/mul_spfft.c
in the next major GMP release. Perhaps this would make mpn_mulmod_bnm1
trickier to maintain (at least as a cutting-edge
ok I see we are far from a public mulmod_bnm1 interface. May I ask that in the
meantime, you don't change the internal functions mpn_mul_fft, mpn_fft_best_k
and mpn_fft_next_size, so that we can use them for the wrap-around trick
(for example in GMP-ECM)?
Paul
David Harvey d.har...@unsw.edu.au writes:
The main problem with this approach is that there is not much
granularity in the choice of r.
In my code, I used some huristics like this: Start with r = 5, and
choose the appropriate size k for the splitting into pieces, and
transform size 2^n. Then
Zimmermann Paul paul.zimmerm...@inria.fr writes:
Are there any plans to put mpn_mulmod_bnm1 in the public API?
No immediate plans. To me, it seems stable enough, if documented
together with mpn_mulmod_bnm1_itch and mpn_mulmod_bnm1_next_size.
Regards,
/Niels
--
Niels Möller. PGP-encrypted
