#16161: Add list parameter to xgcd implementation
--------------------------------+-----------------------------
Reporter: fcolas | Owner:
Type: PLEASE CHANGE | Status: new
Priority: minor | Milestone: sage-6.2
Component: basic arithmetic | Keywords: gcd, xgcd
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
--------------------------------+-----------------------------
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)
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/16161>
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.
