Discrete logarithms, multiplicative orders, in GMP?

Torbjorn Granlund tg at gmplib.org
Wed Jul 11 09:04:30 CEST 2012

Alasdair McAndrew <amca01 at gmail.com> writes:

  I've been doing a little bit of number theoretical work with mostly small
  numbers (64 bits at most), and several times I've needed to compute
  discrete logarithms, or find the order of a number.  That is, given a prime
  p and a,b < p, to find the order of a: the least value n such that a^n = 1
  (mod p), and the discrete log of a to the base b: to find the number e such
  that b^e = a (mod p) if e exists.  It would be very convenient to have such
  functionality in GMP, rather than having to load yet another library.  Are
  there any plans to add such functionality?  Or is there some cunning way of
  obtaining these from built in GMP functions?
There are cunning ways to do this.  We do not plan to put them into GMP.

Several of the algorithms used for integer factoring are applicable for
computing discrete logarithms.  For moderate size numbers, you may use
Pollard rho.  For huge numbers, you may use the Number Field Sieve.
Trust your search engine to find articles about these algorithms' use
for discrete logarithms computation.


More information about the gmp-discuss mailing list