I have created a new ticket: http://trac.sagemath.org/ticket/16161
Le lundi 14 avril 2014 15:58:59 UTC+2, François Colas a écrit : > > 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]> 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]> >> wrote: >> >> On 11 April 2014 19:33, Kannappan Sampath <[email protected]> wrote: >> >>> >> >>> On Fri, Apr 11, 2014 at 11:03 PM, David Roe <[email protected]> >> 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]> >> 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]. >> >>>>> 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. >> >>>> >> >>>> >> >>>> -- >> >>>> 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. >> >>> >> >>> >> >>> -- >> >>> 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. >> >> >> >> -- >> >> 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. >> > >> > -- >> > 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. >> > -- 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.
