Cofactor canonicalisation of mpn_gcdext
abbott at dima.unige.it
Tue Nov 24 11:29:20 CET 2009
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
More information about the gmp-devel