Home | History | Annotate | Line # | Download | only in tests 
      1 /* test mpz_probab_prime_p
      2 
      3 Copyright 2001, 2002, 2004, 2011, 2012, 2014, 2016 Free Software
      4 Foundation, Inc.
      5 
      6 This file is part of the GNU MP Library test suite.
      7 
      8 The GNU MP Library test suite is free software; you can redistribute it
      9 and/or modify it under the terms of the GNU General Public License as
     10 published by the Free Software Foundation; either version 3 of the License,
     11 or (at your option) any later version.
     12 
     13 The GNU MP Library test suite is distributed in the hope that it will be
     14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
     15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
     16 Public License for more details.
     17 
     18 You should have received a copy of the GNU General Public License along with
     19 the GNU MP Library test suite.  If not, see https://www.gnu.org/licenses/.  */
     20 
     21 #include "testutils.h"
     22 
     23 static int
     24 isprime (unsigned long int t)
     25 {
     26   unsigned long int q, r, d;
     27 
     28   if (t < 32)
     29     return (0xa08a28acUL >> t) & 1;
     30   if ((t & 1) == 0)
     31     return 0;
     32 
     33   if (t % 3 == 0)
     34     return 0;
     35   if (t % 5 == 0)
     36     return 0;
     37   if (t % 7 == 0)
     38     return 0;
     39 
     40   for (d = 11;;)
     41     {
     42       q = t / d;
     43       r = t - q * d;
     44       if (q < d)
     45 	return 1;
     46       if (r == 0)
     47 	break;
     48       d += 2;
     49       q = t / d;
     50       r = t - q * d;
     51       if (q < d)
     52 	return 1;
     53       if (r == 0)
     54 	break;
     55       d += 4;
     56     }
     57   return 0;
     58 }
     59 
     60 static void
     61 check_one (mpz_srcptr n, int want)
     62 {
     63   int  got;
     64 
     65   got = mpz_probab_prime_p (n, 25);
     66 
     67   /* "definitely prime" is fine if we only wanted "probably prime" */
     68   if (got == 2 && want == 1)
     69     want = 2;
     70 
     71   if (got != want)
     72     {
     73       printf ("mpz_probab_prime_p\n");
     74       dump   ("  n    ", n);
     75       printf ("  got =%d", got);
     76       printf ("  want=%d\n", want);
     77       abort ();
     78     }
     79 }
     80 
     81 static void
     82 check_pn (mpz_ptr n, int want)
     83 {
     84   check_one (n, want);
     85   mpz_neg (n, n);
     86   check_one (n, want);
     87 }
     88 
     89 static void
     90 check_small (void)
     91 {
     92   mpz_t  n;
     93   long   i;
     94 
     95   mpz_init (n);
     96 
     97   for (i = 0; i < 1700; i++)
     98     {
     99       mpz_set_si (n, i);
    100       check_pn (n, isprime (i));
    101     }
    102 
    103   mpz_clear (n);
    104 }
    105 
    106 void
    107 check_composites (void)
    108 {
    109   int i;
    110   int reps = 1000;
    111   mpz_t a, b, n, bs;
    112   unsigned long size_range, size;
    113 
    114   mpz_init (a);
    115   mpz_init (b);
    116   mpz_init (n);
    117   mpz_init (bs);
    118 
    119   for (i = 0; i < reps; i++)
    120     {
    121       mini_urandomb (bs, 16);
    122       size_range = mpz_get_ui (bs) % 10 + 1; /* 0..1024 bit operands */
    123 
    124       mini_urandomb (bs, size_range);
    125       size = mpz_get_ui (bs);
    126       mini_rrandomb (a, size);
    127 
    128       mini_urandomb (bs, size_range);
    129       size = mpz_get_ui (bs);
    130       mini_rrandomb (b, size);
    131 
    132       /* Exclude trivial factors */
    133       if (mpz_cmp_ui (a, 1) == 0)
    134 	mpz_set_ui (a, 2);
    135       if (mpz_cmp_ui (b, 1) == 0)
    136 	mpz_set_ui (b, 2);
    137 
    138       mpz_mul (n, a, b);
    139 
    140       check_pn (n, 0);
    141     }
    142   mpz_clear (a);
    143   mpz_clear (b);
    144   mpz_clear (n);
    145   mpz_clear (bs);
    146 }
    147 
    148 static void
    149 check_primes (void)
    150 {
    151   static const char * const primes[] = {
    152     "2", "17", "65537",
    153     /* diffie-hellman-group1-sha1, also "Well known group 2" in RFC
    154        2412, 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 } */
    155     "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
    156     "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
    157     "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
    158     "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
    159     "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
    160     "FFFFFFFFFFFFFFFF",
    161     NULL
    162   };
    163 
    164   mpz_t n;
    165   int i;
    166 
    167   mpz_init (n);
    168 
    169   for (i = 0; primes[i]; i++)
    170     {
    171       mpz_set_str_or_abort (n, primes[i], 0);
    172       check_one (n, 1);
    173     }
    174   mpz_clear (n);
    175 }
    176 
    177 void
    178 testmain (int argc, char *argv[])
    179 {
    180   check_small ();
    181   check_composites ();
    182   check_primes ();
    183 }
    184