Discrete logarithms, multiplicative orders, in GMP?

[Zimmermann Paul]

       Alasdair,

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

I suggest using Pari/GP:

? p=2^64-59
%3 = 18446744073709551557
? g = znprimroot(p)
%4 = Mod(2, 18446744073709551557)
? znlog(5,g) # solving 2^x = 5 mod p
%5 = 4806564010799003099

? polrootsmod(x^2-11,p) # solving x^2 = 11 mod p
%11 = [Mod(6461983710974175130, 18446744073709551557), Mod(11984760362735376427, 18446744073709551557)]~

You can use Pari/GP in library mode, in which case you can call it from a C
program where you can access GMP functions too.

Paul Zimmermann