John Cremona on Wed, 03 Oct 2018 21:04:38 +0200


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

Re: vector version of gcdext?

Thanks for the replies.  I was planning to use this with polynomials in one variable over a cyclotomic field.  I'll use mathnf.

John

On Wed, 3 Oct 2018 at 17:36, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
* Bill Allombert [2018-10-03 18:31]:
> On Wed, Oct 03, 2018 at 04:47:40PM +0100, J E Cremona wrote:
> > The function gcd() allows 2 inputs as in gcd(2,3) or a vector of inputs as
> > in gcd([6,10,15]),  but the extended version only allows the first form.
> > It would not be hard to write an extended vector version (and I can of
> > course write my own) -- feature request?
>
> Hello John,
>
> The issue is that there are several solutions and no obvious canonical
> ones in that case. What would your extended vector version do ?
>
> Sometime we want small solutions, in which case a LLL based solution is
> better

That's what mathnf(t_VEC) implements [ Havas-Majewski ] for integer entries.
For polynomials, the implementation is not efficient, but OK for small
matrices.

> , and often we want the dual of gcdext, that is:
> given p_1...p_n, find a_1...a_n such that
>
> \sum a_i\*\prod_{i \neq j} p_j = 1
>
> (that is a_i = delta_i,j [mod p_j])

Not too hard to get that one from the other ...

  Q = vecprod(P);
  mathnf(vector(#P, i, Q/P[i]))

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]
`