[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 01:54:11 +0200
User-agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.6

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


reply via email to

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