#16161: Add list parameter to xgcd implementation
------------------------------------+------------------------
Reporter: fcolas | Owner:
Type: PLEASE CHANGE | Status: new
Priority: minor | Milestone: sage-6.2
Component: basic arithmetic | Resolution:
Keywords: gcd, xgcd | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
------------------------------------+------------------------
Description changed by fcolas:
Old description:
> It is not possible to use xgcd() with a list parameter.
>
> Bézout coefficients with more than two integers could be implemented in
> xgcd() (i.e. a1*u1 + a2*u2 + ... + an*un = g)
>
> Example:
> {{{
> sage: xgcd2([385, 231, 165, 105])
> (1, [-2, 1, 2, 2])
> }}}
>
> Actually this is already done using LLL in Magma to get a small solution
> [https://magma.maths.usyd.edu.au/magma/handbook/text/311#2923]
>
> I think something which looks like this may work:
>
> {{{
> """
> 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)
> }}}
New description:
It is not possible to use xgcd() with a list parameter.
Bézout coefficients with more than two integers could be implemented in
xgcd() (i.e. a1*u1 + a2*u2 + ... + an*un = g)
Example:
{{{
sage: xgcd2([385, 231, 165, 105])
(1, [-2, 1, 2, 2])
}}}
Actually this is already done using LLL in Magma to get a small solution
[https://magma.maths.usyd.edu.au/magma/handbook/text/311#2923]
I think something which looks like this should work:
{{{
"""
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)
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/16161#comment:1>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" 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-trac.
For more options, visit https://groups.google.com/d/optout.
