[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: symbol catenation and montgomery

From: Torbjorn Granlund
Subject: Re: symbol catenation and montgomery
Date: 29 Sep 2000 12:15:06 +0200
User-agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.6

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
  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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]