_basecase or _sec? [

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  mod (div_r_sec) is more important than general division.
  
The mod avariant is the only one used presently, but it seemed to make
sense to provide both with the same source code.

  And modular inverse is more important than general gcdext.

Hmm...can one use Newton for any a^(-1) mod b (when that exists)?  (I
listed gcdext for the sake of inverses, and omitted gcd.)

  I've also seen some need for add_1/sub_1.
  
OK.

  Modular inverse is a bit tricky, I have an implementation (at
  http://git.lysator.liu.se/nettle/nettle/blobs/master/sec-modinv.c) which
  is some 50 time slower than mpn_gcdext. As far as I'm aware, this is a
  "novel" algorithm. I think it could be extended to return the gcd and/or
  a success/fail indication without leaking.
  
This looks reasonable, and not unlike something I played with the other
day.  We can always start with something slow, and improve it.

Some ideas for faster code:

1. Determine a 2 x 2 matrix which will make guaranteed progress of k
   bits, using O(k) bits of the operands.
2. Apply the matrix using mpn_addmul and mpn_submul.
3. Loop back unless we are done.

Brilliant, isn't it?  :-)

Of course, 1 is impossible at least when we have reduced the operands to
be "prematurely" equal, but that's a degenerate case for inverse (but
not for general gcd(ext)).

I am not familiar with the Jebelean (or Möller!) criteria for gcd, but
my intuition suggests that there exists a O(k)-bit matrix which reduces
k bits from the operands.  And the same intuition suggests that it can
be computed from O(k) high bits.  Am I wrong?

-- 
Torbjörn