Here is what I did using LLL:
"""
INPUT: a list of integers
OUTPUT: (g, u) such that g = u1*a1 + u2*a2 + ... + un*an
"""
def xgcd2(a):
s = len(a)
c = ZZ(int(random()*10^s+1))
L = matrix(ZZ, s+1, s, lambda i, j: kronecker_delta(i, j))
L.set_row(s, a)
L.rescale_row(s, c)
U = (L.transpose()).LLL()
u = list(U[s-1])[:-1]
return (sum([ai*ui for (ai, ui) in zip(a, u)]), u)
This is done like this in Magma:
https://magma.maths.usyd.edu.au/magma/handbook/text/311#2923
(Maybe a small c could be enough?)
François
Le samedi 12 avril 2014 10:25:16 UTC+2, John Cremona a écrit :
>
> On 12 April 2014 00:06, Robert Bradshaw <[email protected] <javascript:>>
> wrote:
> > Note that this is implemented in various places, e.g.
> >
> https://github.com/sagemath/sagelib/blob/master/sage/ext/multi_modular.pyx
> > , but certainly a general user-friendly function would be nice to
> > have.
>
> Agreed. In my post I was mainly trying to make sure that the
> implementation was not done via the obvious induction / recursion, as
> that is well known to provide very skewed solutions. If one wants to
> get a small solution then using LLL is also possible.
>
> John
>
> >
> > On Fri, Apr 11, 2014 at 1:18 PM, John Cremona
> > <[email protected]<javascript:>>
> wrote:
> >> On 11 April 2014 19:33, Kannappan Sampath <[email protected]<javascript:>>
> wrote:
> >>>
> >>> On Fri, Apr 11, 2014 at 11:03 PM, David Roe
> >>> <[email protected]<javascript:>>
> wrote:
> >>>>
> >>>> Sounds like a good suggestion. Do you want to create a trac account
> so
> >>>> that you can create the ticket?
> >>>> David
> >>>
> >>>
> >>> I recall having created trac account for François.
> >>>
> >>> -KnS
> >>>
> >>>>
> >>>> On Fri, Apr 11, 2014 at 9:24 AM, François Colas
> >>>> <[email protected]<javascript:>>
> wrote:
> >>>>>
> >>>>> Hello group,
> >>>>>
> >>>>> I realised that extended GCD for several integers is not implemented
> in
> >>>>> Sage (i.e. xgcd2([a1, ..., an]))
> >>>>>
> >>>>> Actually this feature already exists in Magma :
> >>>>>
> >>>>> > ExtendedGreatestCommonDivisor([385, 231, 165, 105]);
> >>>>> 1 [ -2, 1, 2, 2 ]
> >>>>>
> >>>>> It could be interesting to have something like :
> >>>>>
> >>>>> g, u = xgcd2([a1, ..., an])
> >>>>>
> >>>>> with u such that :
> >>>>>
> >>>>> a1*u1 + ... + an*un = g
> >>
> >> Here is how I would implement it:
> >>
> >> sage: v = [385, 231, 165, 105]
> >> sage: _,_,U = Matrix(v).smith_form()
> >> sage: U.column(0)
> >> (-38, 76, -19, 2)
> >> sage: U.column(0) * vector(v)
> >> 1
> >>
> >>
> >>>>>
> >>>>> Do you think a new ticket could be posted?
> >>>>>
> >>>>> Thanks,
> >>>>>
> >>>>> François
> >>>>>
> >>>>> --
> >>>>> You received this message because you are subscribed to the Google
> Groups
> >>>>> "sage-devel" group.
> >>>>> To unsubscribe from this group and stop receiving emails from it,
> send an
> >>>>> email to [email protected] <javascript:>.
> >>>>> To post to this group, send email to
> >>>>> [email protected]<javascript:>.
>
> >>>>> Visit this group at http://groups.google.com/group/sage-devel.
> >>>>> For more options, visit https://groups.google.com/d/optout.
> >>>>
> >>>>
> >>>> --
> >>>> You received this message because you are subscribed to the Google
> Groups
> >>>> "sage-devel" group.
> >>>> To unsubscribe from this group and stop receiving emails from it,
> send an
> >>>> email to [email protected] <javascript:>.
> >>>> To post to this group, send email to
> >>>> [email protected]<javascript:>.
>
> >>>> Visit this group at http://groups.google.com/group/sage-devel.
> >>>> For more options, visit https://groups.google.com/d/optout.
> >>>
> >>>
> >>> --
> >>> You received this message because you are subscribed to the Google
> Groups
> >>> "sage-devel" group.
> >>> To unsubscribe from this group and stop receiving emails from it, send
> an
> >>> email to [email protected] <javascript:>.
> >>> To post to this group, send email to
> >>> [email protected]<javascript:>.
>
> >>> Visit this group at http://groups.google.com/group/sage-devel.
> >>> For more options, visit https://groups.google.com/d/optout.
> >>
> >> --
> >> You received this message because you are subscribed to the Google
> Groups "sage-devel" group.
> >> To unsubscribe from this group and stop receiving emails from it, send
> an email to [email protected] <javascript:>.
> >> To post to this group, send email to
> >> [email protected]<javascript:>.
>
> >> Visit this group at http://groups.google.com/group/sage-devel.
> >> For more options, visit https://groups.google.com/d/optout.
> >
> > --
> > You received this message because you are subscribed to the Google
> Groups "sage-devel" group.
> > To unsubscribe from this group and stop receiving emails from it, send
> an email to [email protected] <javascript:>.
> > To post to this group, send email to
> > [email protected]<javascript:>.
>
> > Visit this group at http://groups.google.com/group/sage-devel.
> > For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
