integer gcd/"Bezout" with more than 2 arguments

[John Cremona]

I was wondering what would be the best way in Flint to do the following:   given integers a1, a2, ..., an find integers x1,x2,...,xn such that gcd(a1,a2,...,an) = sum(xi*ai).  When n=2 this is just the extended Euclidean algorithm.  Applying that recursively or sequentially gives a bad solution wuth the x's very skewed in size.  Another solution is possible by computing the Smith Normal Form of the vector of a's as a 1xn matrix.  Of course the set of all solutions is a coset of the rank n-1 lattice (if the integer vectors orthogonal to the vector (a1,...,an)) so finding the "best" solution (smallest x's, in some sense) is a special case of the closest vector problem.

In my application I only need this for small n (no more than 8) but it would be good to have a general solution, preferebly in the Flint library itself!  (I could not find it, but if it is there already please tell me).

John

[Albin Ahlbäck]

Hello John,

As far as I'm aware, there is no function for Bézout's identity with 2+
arguments in FLINT. However, you could create one recursively as follows.

Suppose a1, ..., an are integers. Then there exists integers x1 and x2
such that

x1 a1 + x2 a2 = gcd(a1, a2).

Then there exists integers y1 and y2 such that

y1 gcd(a1, a2) + y2 a3 = gcd(gcd(a1, a2), a3)

y1 (x1 a1 + x2 a2) + y2 a3 = gcd(a1, a2, a3)

(x1 y1) a1 + (x2 y1) a2 + y2 a3 = gcd(a1, a2, a3).

Of course, you can extend this to how many inputs you'd like.

It would be a good idea to have a generalized extended Euclidean
algorithm in FLINT, just like fmpz_vec_content. We'll see if we have
time to implement this in the future.

Best,
Albin

> --
>
> ---
> You received this message because you are subscribed to the Google
> Groups "flint-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to flint-devel...@googlegroups.com
> <mailto:flint-devel...@googlegroups.com>.
> To view this discussion on the web, visit
> https://groups.google.com/d/msgid/flint-devel/CAD0p0K6rt0%3DgJW_haUe%3DiyON1zrh8BqXRHds2jYq%2BrUpuHiB%2BQ%40mail.gmail.com <https://groups.google.com/d/msgid/flint-devel/CAD0p0K6rt0%3DgJW_haUe%3DiyON1zrh8BqXRHds2jYq%2BrUpuHiB%2BQ%40mail.gmail.com?utm_medium=email&utm_source=footer>.

[John Cremona]

Thanks,Albin. The strategy you describe is just what I meant by recursive strategy in my post. You end up with very big coefficients at the beginning of the solution.

I remember hearing a talk about this many years ago in Dagstuhl, from Wieb Bosma I think. (He worked in Magma group for a while and is now I think in Amsterdam.)  That was back in the day when LLL was quite new, and his method may have been based on that. I will try to look that up. And also to see what pari does.

John

[John Cremona]

There's an algorithm briefly described in Hendrik Lenstra's article on Lattices in the book "Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography" (Buhler and Stevenhagen, eds.).

You form a lattice of rank n+1 using the quadratic  function q(x) = sum_{i=1}^{n}x_i^2  + M*x_{n+1}^2 + N*(x_{n+1} - sum_{i=1}^{n} a_i*x_i)^2   where N,M are "large positive integers" with N>>M.  Find a reduced basis for the lattice, and see if there is a basis vector x with M <= q(x) < N.  If so then the first n coordinates solve the problem (with the gcd being x_{n+1}).  There is guarenteed to be such a vector unless all the input a_i are 0, if the reduced basis is "2-reduced".

It should not be hard toimplement this using the function fmpz_lll(), with an LLL context of type GRAM set with fmpz_lll_context_init() though a Flint expert would do it more easily than me!