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., 51 Franklin Street, Fifth Floor, Boston,
  24  * MA 02111-1301, 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_HELP = 300 };
  65
  66   static const struct option options[] =
  67     {
  68       /* Name, args, flag, val */
  69       { "help", no_argument, NULL, OPT_HELP },
  70       { "verbose", no_argument, NULL, 'v' },
  71       { "factorial", no_argument, NULL, 'f' },
  72       { "sieve-limit", required_argument, NULL, 's' },
  73       { NULL, 0, NULL, 0}
  74     };
  75
  76   while ( (c = getopt_long(argc, argv, "vs:", options, NULL)) != -1)
  77     switch (c)
  78       {
  79       case 'v':
  80         verbose = 1;
  81         break;
  82       case OPT_HELP:
  83         usage();
  84         return EXIT_SUCCESS;
  85       case 'f':
  86         factorial = 1;
  87         break;
  88       case 's':
  89         prime_limit = atoi(optarg);
  90         if (prime_limit < 0)
  91           {
  92             usage();
  93             return EXIT_FAILURE;
  94           }
  95         break;
  96       case '?':
  97         return EXIT_FAILURE;
  98       default:
  99         abort();
 100
 101       }
 102
 103   argc -= optind;
 104   argv += optind;
 105
 106   if (argc != 1)
 107     {
 108       usage();
 109       return EXIT_FAILURE;
 110     }
 111
 112   mpz_init(n);
 113
 114   if (factorial)
 115     {
 116       long arg;
 117       char *end;
 118       arg = strtol(argv[0], &end, 0);
 119       if (*end || arg < 0)
 120         {
 121           fprintf(stderr, "Invalid number.\n");
 122           return EXIT_FAILURE;
 123         }
 124       mpz_fac_ui(n, arg);
 125     }
 126   else if (mpz_set_str(n, argv[0], 0))
 127     {
 128       fprintf(stderr, "Invalid number.\n");
 129       return EXIT_FAILURE;
 130     }
 131
 132   if (mpz_cmp_ui(n, 2) <= 0)
 133     {
 134       printf("2\n");
 135       return EXIT_SUCCESS;
 136     }
 137
 138   mpz_init(p);
 139
 140   start = clock();
 141   nettle_next_prime(p, n, 25, prime_limit, NULL, NULL);
 142   end = clock();
 143
 144   mpz_out_str(stdout, 10, p);
 145   printf("\n");
 146
 147   if (verbose)
 148     {
 149       mpz_t d;
 150
 151       mpz_init(d);
 152       mpz_sub(d, p, n);
 153
 154       /* Avoid using gmp_fprintf, to stay compatible with gmp-3.1. */
 155       fprintf(stderr, "bit size: %lu, diff: ", (unsigned long) mpz_sizeinbase(p, 2));
 156       mpz_out_str(stderr, 10, d);
 157       fprintf(stderr, ", total time: %.3g s\n",
 158               (double)(end - start) / CLOCKS_PER_SEC);
 159     }
 160   return EXIT_SUCCESS;
 161 }