fast gcd

bodrato at bodrato at
Wed Oct 14 10:23:54 CEST 2009


> * is it possible to compute only part of the matrix M (say 3 out of 4
>   coefficients) and still be able to reconstruct efficiently M^{-1} (a;b),
>   using the fact that M is unimodular?

For a component, you need two products and a subtraction as usual. For the
other one, a product, the subtraction and a... division.

A1= A*d - B*b; B1= (A-A1*a)/b

[A1,B1]~ == [a,b;(d*a-1)/b,d]^-1 * [A,B]~


More information about the gmp-devel mailing list