Line data    Source code

       1             : /* Random initialization for P-1 and P+1.
       2             : 
       3             : Copyright 2005, 2006, 2008 Paul Zimmermann, Alexander Kruppa, Dave Newman.
       4             : 
       5             : This file is part of the ECM Library.
       6             : 
       7             : The ECM Library is free software; you can redistribute it and/or modify
       8             : it under the terms of the GNU Lesser General Public License as published by
       9             : the Free Software Foundation; either version 3 of the License, or (at your
      10             : option) any later version.
      11             : 
      12             : The ECM Library is distributed in the hope that it will be useful, but
      13             : WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
      14             : or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
      15             : License for more details.
      16             : 
      17             : You should have received a copy of the GNU Lesser General Public License
      18             : along with the ECM Library; see the file COPYING.LIB.  If not, see
      19             : http://www.gnu.org/licenses/ or write to the Free Software Foundation, Inc.,
      20             : 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA. */
      21             : 
      22             : #include <stdio.h>
      23             : #include <stdlib.h>
      24             : 
      25             : # include "ecm-impl.h"
      26             : 
      27             : #ifdef HAVE_UNISTD_H
      28             : # include <unistd.h> /* getpid */
      29             : #endif
      30             : 
      31             : #ifdef TIME_WITH_SYS_TIME
      32             : # include <sys/time.h>
      33             : # include <time.h>
      34             : #else
      35             : # if HAVE_SYS_TIME_H
      36             : #  include <sys/time.h>
      37             : # else
      38             : #  include <time.h>
      39             : # endif
      40             : #endif
      41             : 
      42             : #if defined (_MSC_VER) || defined (__MINGW32__)
      43             : # include <windows.h>
      44             : # include <wincrypt.h>
      45             : #endif
      46             : 
      47             : /* initialize the random number generator if needed */
      48             : void
      49         291 : init_randstate (gmp_randstate_t rng)
      50             : {
      51         291 :   if (mpz_cmp_ui (rng->_mp_seed, 0) == 0)
      52         291 :     gmp_randseed_ui (rng, get_random_ul ());
      53         291 : }
      54             : 
      55             : /* put in 'a' a valid random seed for P-1, i.e. gcd(a,n)=1 and a <> {-1,1} */
      56             : void
      57         212 : pm1_random_seed (mpz_t a, mpz_t n, gmp_randstate_t randstate)
      58             : {
      59             :   mpz_t q;
      60             : 
      61         212 :   init_randstate (randstate);
      62         212 :   mpz_init (q);
      63             :   do
      64             :     {
      65         212 :       mpz_urandomb (a, randstate, 32);
      66         212 :       mpz_gcd (q, a, n);
      67             :     }
      68         212 :   while (mpz_cmp_ui (q, 1) != 0 || mpz_cmp_ui (a, 1) == 0 ||
      69         212 :          mpz_cmp_si (a, -1) == 0);
      70         212 :   mpz_clear (q);
      71         212 : }
      72             : 
      73             : /* put in seed a valid random seed for P+1 */
      74             : void
      75          50 : pp1_random_seed (mpz_t seed, mpz_t n, gmp_randstate_t randstate)
      76             : {
      77             :   mpz_t q;
      78             : 
      79          50 :   init_randstate (randstate);
      80             :   /* need gcd(p^2-4, n) = 1. */
      81          50 :   mpz_init (q);
      82             :   do
      83             :     {
      84          50 :       mpz_urandomb (q, randstate, 32);
      85          50 :       mpz_add_ui (q, q, 1);
      86          50 :       mpz_set (seed, q);
      87          50 :       mpz_mul (q, q, q);
      88          50 :       mpz_sub_ui (q, q, 4);
      89          50 :       mpz_gcd (q, q, n);
      90             :     }
      91          50 :   while (mpz_cmp_ui (q, 1) != 0);
      92          50 :   mpz_clear (q);
      93          50 : }
      94             : 
      95             : /* Produces a random unsigned long value */
      96             : 
      97             : #if defined (_MSC_VER) || defined (__MINGW32__)
      98             : unsigned long 
      99             : get_random_ul (void)
     100             : {
     101             :   SYSTEMTIME tv;
     102             :   HCRYPTPROV Prov;
     103             : 
     104             :   if (CryptAcquireContext (&Prov, NULL, NULL, PROV_RSA_FULL,
     105             :     CRYPT_VERIFYCONTEXT))
     106             :     {
     107             :       int r;
     108             :       unsigned long rnd;
     109             :     
     110             :       r = CryptGenRandom (Prov, sizeof (unsigned long), (void *) &rnd);
     111             :       CryptReleaseContext (Prov, 0);
     112             :       if (r)
     113             :         return rnd;
     114             :     }
     115             :   
     116             :   GetSystemTime (&tv);
     117             :   /* This gets us 27 bits of somewhat "random" data based on the time clock.
     118             :      It would probably do the program justice if a better random mixing was done
     119             :      in the non-MinGW get_random_ul if /dev/random does not exist */
     120             :   return ((tv.wHour<<22)+(tv.wMinute<<16)+(tv.wSecond<<10)+tv.wMilliseconds) ^
     121             :          ((tv.wMilliseconds<<17)+(tv.wMinute<<11)+(tv.wHour<<6)+tv.wSecond);
     122             : }
     123             : 
     124             : #else
     125             : 
     126             : unsigned long 
     127         291 : get_random_ul (void)
     128             : {
     129             :   FILE *rndfd;
     130             :   unsigned long t;
     131             : 
     132             :   /* Try /dev/urandom. Warning: this is slow for small numbers or B1. */
     133         291 :   rndfd = fopen ("/dev/urandom", "rb");
     134         291 :   if (rndfd != NULL)
     135             :     {
     136             :       int res;
     137             : 
     138         291 :       res = fread (&t, sizeof (unsigned long), 1, rndfd);
     139         291 :       fclose (rndfd);
     140         291 :       if (res == 1)
     141         291 :         return t;
     142             :     }
     143             : 
     144             :   /* Multiply by large primes to get a bit of avalanche effect */
     145           0 :   return (unsigned long) time (NULL) * 1431655751UL +
     146           0 :          (unsigned long) getpid () * 2147483629UL;
     147             : }
     148             : #endif