Cofactor canonicalisation of mpn_gcdext

[abbott]

Hi,

Niels> One other observation, before I get to the main part of this posting:
Niels> It is clear that there exists an s in the range 2 |s| < |v/g|, but it
Niels> wasn't clear to me that this is what's naturally produced by Euclid's
Niels> algorithm; I'm more familier with the bounds |s| < |v|/g, or the

Bill> The most canonical value for s,t is such that -t/s is the one-but-last
Bill> convergent of the continued fraction associated to u/v.

A moment of pedantry...
  I would like to make a distinction here:
  (A)  Niels wrote about "what's naturally produced by EA"
  (B)  Bill wrote about "The most canonical value"

  With luck these two are actually the same in almost all cases
  (see my summary below)


I looked through Shoup's arguments (and exercise 4.9), and concluded the
following: strict inequality is guaranteed whenever  lambda >= 3.
I then looked at the various cases where  lambda  was small.
In summary, strict inequality is guaranteed except for the
following inputs  (a,b)  and assuming  a >= b >= 0
  (0,0)      very special case
  (N,0)      trivial case
  (N,N)      another trivial case
  (2*N,N)    very easy case
  (K*N,2*N)  with K >= 3 and K odd

As Niels noted the only cases where strict inequality fails are where
|s| = 1  or  |t| = 1.


I admit I am a little puzzled about why it is important that the
inequality  2*|s| < |v/g|  be strict.  Niels (22 Nov 2009 22:02:35)
introduced this strict version saying 

  It is clear that there exists an s in the range 2 |s| < |v/g|

On reading it I had assumed it was just a typo: since s is defined
modulo  |v/g|  it is clear that we can choose a residue which
satisfies the non-strict form  2 |s| <= |v/g|.

While the non-strict form does on its own admit ambiguity (i.e. s = +/- v/2g)
I note that, when taken together, the two non-strict inequalities
(one for |s| and the other for |t|) do indeed determine s and t uniquely
(i.e. the ambiguity disappears) since at most only one of v/g and u/g is even.

In summary  I think we can have both (A) and (B) together because
 * Shoup's Thm 4.3(vi) gives us the non-strict inequalities
 * the two non-strict inequalities together determine s & t uniquely


John.