Re: symbol catenation and montgomery

[Torbjorn Granlund]

address@hidden (Niels Möller) writes:

  According to Henrik Grubbström (address@hidden), there are a few
  compilers that define __STDC__ only in strict ansi mode. I can see two
  ways to fix that, either do some autoconf test and insert a symbol in
  gmp.h depending on the result, or doing a test using only cpp,
  something like
  
There are compilers that define __STDC__ to 0 when in semi ANSI mode
too.  But before somebody can give an example of a compiler where the
current code really fails, I don't think we should change anything.

  Secondly, someone told me that gmp's modular exponentiation is slow,
  because it doesn't use montgomery style multiplication. I've had a
  look at mpz/powm.c, but I can't really tell if that is true. To me,
  the mpz_redc resembles montgomery reduction a little, but on the other
  hand it is used only for small moduli, so I guess it is something
  different. What is the status, and do you have any plans for a more
  optimized powm function? The tasks.html file doesn't say much about
  this. 
  
We have redc code, but since it is O(n^2) it won't be faster than
division, which is O(M(n)*log(n)).

We're talking about asymptotically fast redc, but I don't know if that
will be implemented any time soon.

Is GMP slower than other packages for modular exponentiation?

-- 
Torbjörn