Paper with an improved bound for half-gcd matrix sizes

Niels Möller nisse at
Wed Feb 8 19:57:26 CET 2023


Juraj Sukop and myself just published a short paper with an improved
bound (+ one correction) to my older gcd paper which describes the
algorithm used in GMP.


>From my perspective, it's a stronger and more rigorous argument, related
to this comment at,

  /* Furthermore, assume M ends with a quotient (1, q; 0, 1),
     then either q or q + 1 is a correct quotient, and M1 will
     start with either (1, 0; 1, 1) or (2, 1; 1, 1). This
     rules out the case that the size of M * M1 is much
     smaller than the expected M->n + M1->n. */

and it clarifies some of the subtler details.

Thanks to Paul for helping out in getting the paper published, and
suggesting publishing on HAL.


Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list