flintlib / flint

FLINT (Fast Library for Number Theory)
http://www.flintlib.org
GNU Lesser General Public License v3.0
444 stars 244 forks source link

Base more integer operations on fft_small #1365

Open fredrik-johansson opened 1 year ago

fredrik-johansson commented 1 year ago

Things that ought to use fft_small for huge operands:

fredrik-johansson commented 1 year ago

FWIW, the crossover for powm based on fmpz_fdiv_qr_preinvn instead of mpz_powm (which uses REDC) is around 10^5 bits. I suppose this would be lower if we precomputed the transform. Is there a way to implement REDC efficiently using fft_small?

fredrik-johansson commented 1 year ago

Note: fmpz_fprint and fmpz_fread will need to be updated to use the new radix conversion code.