Back to index

lightning-sunbird  0.9+nobinonly
primegen.c
Go to the documentation of this file.
00001 /*
00002  *  primegen.c
00003  *
00004  * Generates random integers which are prime with a high degree of
00005  * probability using the Miller-Rabin probabilistic primality testing
00006  * algorithm.
00007  *
00008  * Usage:
00009  *    primegen <bits> [<num>]
00010  *
00011  *    <bits>   - number of significant bits each prime should have
00012  *    <num>    - number of primes to generate
00013  *
00014  * ***** BEGIN LICENSE BLOCK *****
00015  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00016  *
00017  * The contents of this file are subject to the Mozilla Public License Version
00018  * 1.1 (the "License"); you may not use this file except in compliance with
00019  * the License. You may obtain a copy of the License at
00020  * http://www.mozilla.org/MPL/
00021  *
00022  * Software distributed under the License is distributed on an "AS IS" basis,
00023  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00024  * for the specific language governing rights and limitations under the
00025  * License.
00026  *
00027  * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.
00028  *
00029  * The Initial Developer of the Original Code is
00030  * Michael J. Fromberger.
00031  * Portions created by the Initial Developer are Copyright (C) 1998
00032  * the Initial Developer. All Rights Reserved.
00033  *
00034  * Contributor(s):
00035  *
00036  * Alternatively, the contents of this file may be used under the terms of
00037  * either the GNU General Public License Version 2 or later (the "GPL"), or
00038  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00039  * in which case the provisions of the GPL or the LGPL are applicable instead
00040  * of those above. If you wish to allow use of your version of this file only
00041  * under the terms of either the GPL or the LGPL, and not to allow others to
00042  * use your version of this file under the terms of the MPL, indicate your
00043  * decision by deleting the provisions above and replace them with the notice
00044  * and other provisions required by the GPL or the LGPL. If you do not delete
00045  * the provisions above, a recipient may use your version of this file under
00046  * the terms of any one of the MPL, the GPL or the LGPL.
00047  *
00048  * ***** END LICENSE BLOCK ***** */
00049 /* $Id: primegen.c,v 1.7 2004/04/27 23:04:37 gerv%gerv.net Exp $ */
00050 
00051 #include <stdio.h>
00052 #include <stdlib.h>
00053 #include <string.h>
00054 #include <limits.h>
00055 #include <time.h>
00056 
00057 #include "mpi.h"
00058 #include "mplogic.h"
00059 #include "mpprime.h"
00060 
00061 #undef MACOS         /* define if running on a Macintosh */
00062 
00063 #ifdef MACOS
00064 #include <console.h>
00065 #endif
00066 
00067 #define NUM_TESTS 5  /* Number of Rabin-Miller iterations to test with */
00068 
00069 #ifdef DEBUG
00070 #define FPUTC(x,y) fputc(x,y)
00071 #else
00072 #define FPUTC(x,y) 
00073 #endif
00074 
00075 int main(int argc, char *argv[])
00076 {
00077   unsigned char *raw;
00078   char          *out;
00079   unsigned long nTries;
00080   int         rawlen, bits, outlen, ngen, ix, jx;
00081   int           g_strong = 0;
00082   mp_int      testval;
00083   mp_err      res;
00084   clock_t     start, end;
00085 
00086 #ifdef MACOS
00087   argc = ccommand(&argv);
00088 #endif
00089 
00090   /* We'll just use the C library's rand() for now, although this
00091      won't be good enough for cryptographic purposes */
00092   if((out = getenv("SEED")) == NULL) {
00093     srand((unsigned int)time(NULL));
00094   } else {
00095     srand((unsigned int)atoi(out));
00096   }
00097 
00098   if(argc < 2) {
00099     fprintf(stderr, "Usage: %s <bits> [<count> [strong]]\n", argv[0]);
00100     return 1;
00101   }
00102        
00103   if((bits = abs(atoi(argv[1]))) < CHAR_BIT) {
00104     fprintf(stderr, "%s: please request at least %d bits.\n",
00105            argv[0], CHAR_BIT);
00106     return 1;
00107   }
00108 
00109   /* If optional third argument is given, use that as the number of
00110      primes to generate; otherwise generate one prime only.
00111    */
00112   if(argc < 3) {
00113     ngen = 1;
00114   } else {
00115     ngen = abs(atoi(argv[2]));
00116   }
00117 
00118   /* If fourth argument is given, and is the word "strong", we'll 
00119      generate strong (Sophie Germain) primes. 
00120    */
00121   if(argc > 3 && strcmp(argv[3], "strong") == 0)
00122     g_strong = 1;
00123 
00124   /* testval - candidate being tested; nTries - number tried so far */
00125   if ((res = mp_init(&testval)) != MP_OKAY) {
00126     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
00127     return 1;
00128   }
00129   
00130   if(g_strong) {
00131     printf("Requested %d strong prime value(s) of %d bits.\n", 
00132           ngen, bits);
00133   } else {
00134     printf("Requested %d prime value(s) of %d bits.\n", ngen, bits);
00135   }
00136 
00137   rawlen = (bits / CHAR_BIT) + ((bits % CHAR_BIT) ? 1 : 0) + 1;
00138 
00139   if((raw = calloc(rawlen, sizeof(unsigned char))) == NULL) {
00140     fprintf(stderr, "%s: out of memory, sorry.\n", argv[0]);
00141     return 1;
00142   }
00143 
00144   /* This loop is one for each prime we need to generate */
00145   for(jx = 0; jx < ngen; jx++) {
00146 
00147     raw[0] = 0;  /* sign is positive */
00148 
00149     /* Pack the initializer with random bytes    */
00150     for(ix = 1; ix < rawlen; ix++) 
00151       raw[ix] = (rand() * rand()) & UCHAR_MAX;
00152 
00153     raw[1] |= 0x80;             /* set high-order bit of test value     */
00154     raw[rawlen - 1] |= 1;       /* set low-order bit of test value      */
00155 
00156     /* Make an mp_int out of the initializer */
00157     mp_read_raw(&testval, (char *)raw, rawlen);
00158 
00159     /* Initialize candidate counter */
00160     nTries = 0;
00161 
00162     start = clock(); /* time generation for this prime */
00163     do {
00164       res = mpp_make_prime(&testval, bits, g_strong, &nTries);
00165       if (res != MP_NO)
00166        break;
00167       /* This code works whether digits are 16 or 32 bits */
00168       res = mp_add_d(&testval, 32 * 1024, &testval);
00169       res = mp_add_d(&testval, 32 * 1024, &testval);
00170       FPUTC(',', stderr);
00171     } while (1);
00172     end = clock();
00173 
00174     if (res != MP_YES) {
00175       break;
00176     }
00177     FPUTC('\n', stderr);
00178     puts("The following value is probably prime:");
00179     outlen = mp_radix_size(&testval, 10);
00180     out = calloc(outlen, sizeof(unsigned char));
00181     mp_toradix(&testval, (char *)out, 10);
00182     printf("10: %s\n", out);
00183     mp_toradix(&testval, (char *)out, 16);
00184     printf("16: %s\n\n", out);
00185     free(out);
00186     
00187     printf("Number of candidates tried: %lu\n", nTries);
00188     printf("This computation took %ld clock ticks (%.2f seconds)\n",
00189           (end - start), ((double)(end - start) / CLOCKS_PER_SEC));
00190     
00191     FPUTC('\n', stderr);
00192   } /* end of loop to generate all requested primes */
00193   
00194   if(res != MP_OKAY) 
00195     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
00196 
00197   free(raw);
00198   mp_clear(&testval);       
00199   
00200   return 0;
00201 }