mpz_prevprime

[Niels Möller]

Seth Troisi <braintwo at gmail.com> writes:

> In order to profile parts of this I also added tune/speed support for
> mpz_nextprime
> https://github.com/sethtroisi/libgmp/pull/6/files
> Note that I change the behavior of s->size to mean size bits instead
> of limbs for for measuring mpz_nextprime, as the function is slow (in the
> worstcase it can take >5 second for a 1500 bit input, and >90 seconds for a
> ~2700 bit input)

Good. I imagine mpz_nextprime performance has some room for improvement.

For benchmarking, maybe one should use something other than arithmetic
mean for averaging, since some numbers will be much slower than others?

> For implementing mpz_prevprime, I tried to reuse as much code as possible
> with a macro for the function body, I'm not sure how readable it ended up.
> it also possible this could be speed up if I used separate code for each of
> the functions, by calculating the negative modulo and using unsigned
> integers everywhere. I'm open to hearing how folks thinks code could be
> better reused / structured.

Maybe it would make sense to generalize a bit further, and write a
function to find the first prime (if any) in an arithmetic sequence.
I.e., find the smallest k >= such that A + kB is prime (if any). A
corresponds the current input to mpz_nextprime, and B could be either a
signed long or a bignum.

Implementation strategy would be roughly the same: Consider the
sequences A + kB (mod p) for some list of small primes, and find first k
so that they all are non-zero, then do a heavier primality test (or a
compositeness test, if we want to make that distinction). One would also
need some initial checks to identify inputs for which there is no such
prime.

> Finally for mpz_prevprime(rop, op <= 2) it's not clear what rop should be
> set to, so I use the smallest prime (2).

I'd prefer using the function return value to indicate success/failure.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.