Discrete logarithms, multiplicative orders, in GMP?

Alasdair McAndrew amca01 at gmail.com
Thu Jul 12 09:05:45 CEST 2012


I can use (and have used) libpari in a C program,  but the trouble of
mixing libpari and gmp is all the conversions between the PARI type GEN, C
types unsigned long etc, and GMP mpz_t.   It'd be much more convenient to
have one library which does it all.

cheers,
Alasdair

On Wed, Jul 11, 2012 at 6:12 PM, Zimmermann Paul
<Paul.Zimmermann at loria.fr>wrote:

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


More information about the gmp-discuss mailing list