Improvement to mpz_nextprime

[Paul Zimmermann]

> Though, it might be interesting to verify with different numbers size.

Below is a test program, which gave on a 3Ghz Pentium 4 with gmp-4.2:

mpz_nextprime1 took 984ms  # original version
mpz_nextprime2 took 1008ms # suggested 'improvement'
mpz_nextprime3 took 776ms  # original with 1 Miller-Rabin test instead of 5

Note a significant speedup is obtained with only 1 Miller-Rabin test.

For some applications, it would be very useful to be able to give the
number of Miller-Rabin tests in argument to mpz_nextprime. I suggest:

   void mpz_nextprime3 (mpz_ptr p, mpz_srcptr t, int REPS)
   Same as mpz_nextprime, but with REPS Miller-Rabin tests instead of 5.

Paul

#include <stdio.h>
#include "gmp.h"
#include <sys/types.h>
#include <sys/resource.h>

int
cputime ()
{
  struct rusage rus;

  getrusage (0, &rus);
  return rus.ru_utime.tv_sec * 1000 + rus.ru_utime.tv_usec / 1000;
}

   void
   mpz_nextprime1 (mpz_ptr p, mpz_srcptr t)
   {
     mpz_add_ui (p, t, 1L);
     while (! mpz_probab_prime_p (p, 5))
      mpz_add_ui (p, p, 1L);
  }

  void
  mpz_nextprime2 (mpz_ptr p, mpz_srcptr t)
  {
    mpz_add_ui (p, t, 1L);
    mpz_setbit(p, 0);
    while (! mpz_probab_prime_p (p, 5))
      mpz_add_ui (p, p, 2L);
  }

  void
  mpz_nextprime3 (mpz_ptr p, mpz_srcptr t)
  {
    mpz_add_ui (p, t, 1L);
    while (! mpz_probab_prime_p (p, 1))
      mpz_add_ui (p, p, 1L);
  }

int
main()
{
  int st, i;

  mpz_t p;
  mpz_init (p);

  mpz_set_str (p, "100000000000000000000000000000000000000000000000000", 10);
  st = cputime ();
  for (i = 0; i < 1000; i++)
    mpz_nextprime1 (p, p);
  printf ("mpz_nextprime1 took %dms\n", cputime () - st);
  
  mpz_set_str (p, "100000000000000000000000000000000000000000000000000", 10);
  st = cputime ();
  for (i = 0; i < 1000; i++)
    mpz_nextprime2 (p, p);
  printf ("mpz_nextprime2 took %dms\n", cputime () - st);
  
  mpz_set_str (p, "100000000000000000000000000000000000000000000000000", 10);
  st = cputime ();
  for (i = 0; i < 1000; i++)
    mpz_nextprime3 (p, p);
  printf ("mpz_nextprime3 took %dms\n", cputime () - st);
  
  mpz_clear (p);
  return 0;
}