Question about gmp...

[Sisyphus]

----- Original Message ----- 
From: "David Cleaver" <wraithx at morpheus.net>
To: "gmp-discuss" <gmp-discuss at swox.com>
Sent: Monday, January 23, 2006 8:26 AM
Subject: Question about gmp...


> Hello everyone,
>
> I have just begun learning gmp and was going to write my own program
> involving the miller-rabin "primality" test, when I came across
> mpz_probab_prime_p.  When I did a little more digging I saw that that
> function made a call to mpz_millerrabin.  Once there I saw almost all
> the code I needed to write my program.  But, here's where my questions
> start:
> 1)  I've read before that if the function isn't documented in the man
> pages, I shouldn't use it if I want to keep forward compatibility.  So,
> should most of the functionality in millerrabin.c not be duplicated for
> fear of them being deprecated?
> 2)  I've seen references to mpz_srcptr and mpz_ptr in millerrabin.c.
> Are these ok to use or do they fall into the same category as up above?
>
> The reason I'm asking is because I want to use my own set of bases when
> doing these tests and I'd like to make sure the miller-rabin function is
> performing as fast as possible.  Thanks in advance for any comments or
> suggestions you may have.
>

I think it's best to use the high level (documented) mpz functions for your
miller-rabin tests. It shouldn't be difficult to do that without suffering
any significant performance hit - so there's really no reason to do it any
other way :-)

I find that the miller-rabin test I use (written using the high level mpz
functions) is slightly faster than mpz_probab_prime_p - presumably because
it doesn't have the overhead of performing trial divisions. eg, for a 16650
bit prime the miller-rabin test took 34.9 seconds, mpz_probab_prime_p took
35.6 seconds.

Cheers,
Rob