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