ni...@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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel