Discrete logarithms, multiplicative orders, in GMP?
Paul.Zimmermann at loria.fr
Wed Jul 11 10:12:26 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?
I suggest using Pari/GP:
%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.
More information about the gmp-discuss