Discrete logarithms, multiplicative orders, in GMP?

Alasdair McAndrew amca01 at gmail.com
Wed Jul 11 09:25:19 CEST 2012


Thanks for your reply.  Yes, I know I could program the Pohlig-Hellman or
Baby step-Giant step for discrete logs (and I've done that for other
systems); it'd just be nice not to have to!  I'd also like a method for
modular square roots.  Are there any user-written libraries which extend
the functionality of GMP either for my purposes or others?

Thanks again,
Alasdair

On Wed, Jul 11, 2012 at 5:04 PM, Torbjorn Granlund <tg at gmplib.org> wrote:

> 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.
>
> --
> Torbjörn
>


More information about the gmp-discuss mailing list