Karim Belabas on Wed, 09 Dec 2020 16:41:40 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: muldep


* Bill Allombert [2020-12-09 16:36]:
> On Wed, Dec 09, 2020 at 03:29:16PM +0100, Denis Simon wrote:
> > Thank you John for your suggestion.
> > 
> > As a first step, you probably mean something like
> > Factoring into coprimes in essentially linear time, by Bernstein ?
> 
> Yes, this is what ZV_cba does.

Not quite: Z_cba (only 2 inputs) is linear time, but the coprime base
extension (~ ZV_cba) still uses the naive quadratic algorithm.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`