Re: symbol catenation and montgomery

[Torbjorn Granlund]

address@hidden writes:

     I measured a^b mod c for random 1024-bit numbers a, b, c:
  
       mpz_powm (1024)    16.375ms
  
  That's pretty good!
  
Isn't an 1024-bit exponent somewhat larger than one usually uses for
RSA?  What does "openssl speed" do?

     I then run "openssl speed 1024" on the same machine.  I don't know how
     to interpret these numbers:
  
       rsa 1024 bits   0.0066s   0.0004s    152.6   2660.1
  
  The number of interest is 152.6.  It means openssl did 152.6 1024-bit
  RSA decryptions (each consisting of two 512-bit modexps and a CRT
  recombination) per second.  A 1024-bit modexp is maybe 3x as expensive
  as a 1024 bit RSA decryption because of the CRT.  So that means
  OpenSSL should do around 50 1024-bit modexps/sec or about 20 msec
  each, which means GMP is actually beating OpenSSL.  I'm pleasantly
  surprised.
  
  Can I ask what cpu you did that test on?
  
A 750MHz Athlon.  (I am using an unreleased version of GMP, but since
nobody has tried to optimize mpz_powm since the last release, the
times should be similar to those of GMP 3.1.)

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.

-- 
Torbjörn