Discrete logarithms, multiplicative orders, in GMP?
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