Re: symbol catenation and montgomery

[Torbjorn Granlund]

address@hidden writes:

  Thanks.  That's interesting since the OpenSSL timing is about 1.5x
  faster than a 600 mhz Athlon that a friend of mine tested a few months
  ago.
  
Perhaps he didn't use GMP 3.1?  We had the redc code in GMP 3.0, but
the cutoff point between O(n^2) redc and (O(M(n)) division wasn't
right.

     There are a number of flaws with the redc implementation in GMP.
     First, only mpz_powm actually uses redc, while mpz_powm_ui does not.
     Second, mpz_powm is implemented on top of other mpz calls, not mpn
     as it should.  Calling mpn directly would shave off several ms.
  
  I'm not familiar with GMP programming so I don't know what those
  routines do.  I looked at the source code a *long* time ago and
  obviously it's been tuned a lot since then.

mpz are high level routines for signed integers.  They handle
reallocations and operand checking.  mpn are low level routines with
minimal overhead.

-- 
Torbjörn