examples/next-prime.c

   1 /* next-prime.c
   2  *
   3  * Command line tool for prime search.
   4  *
   5  */
   6
   7 /* nettle, low-level cryptographics library
   8  *
   9  * Copyright (C) 2007 Niels Möller
  10  *
  11  * The nettle library is free software; you can redistribute it and/or modify
  12  * it under the terms of the GNU Lesser General Public License as published by
  13  * the Free Software Foundation; either version 2.1 of the License, or (at your
  14  * option) any later version.
  15  *
  16  * The nettle library is distributed in the hope that it will be useful, but
  17  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  18  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  19  * License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public License
  22  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  23  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  24  * MA 02111-1307, USA.
  25  */
  26
  27 #if HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <time.h>
  34
  35 #include "bignum.h"
  36
  37 #include "getopt.h"
  38
  39 static void
  40 usage(void)
  41 {
  42   fprintf(stderr, "Usage: next-prime [OPTIONS] number\n\n"
  43           "Options:\n"
  44           "      --help         Display this message.\n"
  45           "  -v, --verbose      Display timing information.\n"
  46           "      --factorial    Use factorial of input number.\n"
  47           "  -s  --sieve-limit  Number of primes to use for sieving.\n");
  48 }
  49
  50 int
  51 main(int argc, char **argv)
  52 {
  53   mpz_t n;
  54   mpz_t p;
  55
  56   int c;
  57   int verbose = 0;
  58   int factorial = 0;
  59   int prime_limit = 200;
  60
  61   clock_t start;
  62   clock_t end;
  63
  64   enum { OPT_FACTORIAL = -100 };
  65   static const struct option options[] =
  66     {
  67       /* Name, args, flag, val */
  68       { "help", no_argument, NULL, '?' },
  69       { "verbose", no_argument, NULL, 'v' },
  70       { "factorial", no_argument, NULL, 'f' },
  71       { "sieve-limit", required_argument, NULL, 's' },
  72       { NULL, 0, NULL, 0}
  73     };
  74
  75   while ( (c = getopt_long(argc, argv, "v?s:", options, NULL)) != -1)
  76     switch (c)
  77       {
  78       case 'v':
  79         verbose = 1;
  80         break;
  81       case '?':
  82         usage();
  83         return EXIT_FAILURE;
  84       case 'f':
  85         factorial = 1;
  86         break;
  87       case 's':
  88         prime_limit = atoi(optarg);
  89         if (prime_limit < 0)
  90           {
  91             usage();
  92             return EXIT_FAILURE;
  93           }
  94         break;
  95       default:
  96         abort();
  97
  98       }
  99
 100   argc -= optind;
 101   argv += optind;
 102
 103   if (argc != 1)
 104     {
 105       usage();
 106       return EXIT_FAILURE;
 107     }
 108
 109   mpz_init(n);
 110
 111   if (factorial)
 112     {
 113       long arg;
 114       char *end;
 115       arg = strtol(argv[0], &end, 0);
 116       if (*end || arg < 0)
 117         {
 118           fprintf(stderr, "Invalid number.\n");
 119           return EXIT_FAILURE;
 120         }
 121       mpz_fac_ui(n, arg);
 122     }
 123   else if (mpz_set_str(n, argv[0], 0))
 124     {
 125       fprintf(stderr, "Invalid number.\n");
 126       return EXIT_FAILURE;
 127     }
 128
 129   if (mpz_cmp_ui(n, 2) <= 0)
 130     {
 131       printf("2\n");
 132       return EXIT_SUCCESS;
 133     }
 134
 135   mpz_init(p);
 136
 137   start = clock();
 138   nettle_next_prime(p, n, 25, prime_limit, NULL, NULL);
 139   end = clock();
 140
 141   mpz_out_str(stdout, 10, p);
 142   printf("\n");
 143
 144   if (verbose)
 145     {
 146       mpz_t d;
 147
 148       mpz_init(d);
 149       mpz_sub(d, p, n);
 150
 151       /* Avoid using gmp_fprintf, to stay compatible with gmp-3.1. */
 152       fprintf(stderr, "bit size: %lu, diff: ", (unsigned long) mpz_sizeinbase(p, 2));
 153       mpz_out_str(stderr, 10, d);
 154       fprintf(stderr, ", total time: %.3g s\n",
 155               (double)(end - start) / CLOCKS_PER_SEC);
 156     }
 157   return EXIT_SUCCESS;
 158 }