1 /* Test mpz_powm, mpz_mul, mpz_mod, mpz_mod_ui, mpz_div_ui. 2 3 Copyright 1991, 1993, 1994, 1996, 1999, 2000, 2001, 2009, 2012 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 http://www.gnu.org/licenses/. */ 20 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 25 #include "gmp.h" 26 #include "gmp-impl.h" 27 #include "tests.h" 28 29 void debug_mp (mpz_t, int); 30 31 #define SIZEM 13 32 33 /* Check that all sizes up to just above MUL_TOOM22_THRESHOLD have been tested 34 a few times. FIXME: If SIZEM is set too low, this will never happen. */ 35 int 36 allsizes_seen (unsigned int *allsizes) 37 { 38 mp_size_t i; 39 40 for (i = 1; i < MUL_TOOM22_THRESHOLD + 4; i++) 41 if (allsizes[i] < 4) 42 return 0; 43 return 1; 44 } 45 46 int 47 main (int argc, char **argv) 48 { 49 mpz_t base, exp, mod; 50 mpz_t r1, r2, t1, exp2, base2; 51 mp_size_t base_size, exp_size, mod_size; 52 int i; 53 int reps = 1000; 54 gmp_randstate_ptr rands; 55 mpz_t bs; 56 unsigned long bsi, size_range; 57 unsigned int allsizes[1 << (SIZEM + 2 - 1)]; 58 59 tests_start (); 60 TESTS_REPS (reps, argv, argc); 61 62 rands = RANDS; 63 64 mpz_init (bs); 65 66 mpz_init (base); 67 mpz_init (exp); 68 mpz_init (mod); 69 mpz_init (r1); 70 mpz_init (r2); 71 mpz_init (t1); 72 mpz_init (exp2); 73 mpz_init (base2); 74 75 memset (allsizes, 0, (1 << (SIZEM + 2 - 1)) * sizeof (int)); 76 77 for (i = 0; i < reps || ! allsizes_seen (allsizes); i++) 78 { 79 mpz_urandomb (bs, rands, 32); 80 size_range = mpz_get_ui (bs) % SIZEM + 2; 81 82 do /* Loop until mathematically well-defined. */ 83 { 84 mpz_urandomb (bs, rands, size_range); 85 base_size = mpz_get_ui (bs); 86 mpz_rrandomb (base, rands, base_size); 87 88 mpz_urandomb (bs, rands, 7L); 89 exp_size = mpz_get_ui (bs); 90 mpz_rrandomb (exp, rands, exp_size); 91 } 92 while (mpz_cmp_ui (base, 0) == 0 && mpz_cmp_ui (exp, 0) == 0); 93 94 do 95 { 96 mpz_urandomb (bs, rands, size_range); 97 mod_size = mpz_get_ui (bs); 98 mpz_rrandomb (mod, rands, mod_size); 99 } 100 while (mpz_cmp_ui (mod, 0) == 0); 101 102 allsizes[SIZ(mod)] += 1; 103 104 mpz_urandomb (bs, rands, 2); 105 bsi = mpz_get_ui (bs); 106 if ((bsi & 1) != 0) 107 mpz_neg (base, base); 108 109 /* printf ("%ld %ld %ld\n", SIZ (base), SIZ (exp), SIZ (mod)); */ 110 111 mpz_set_ui (r2, 1); 112 mpz_mod (base2, base, mod); 113 mpz_set (exp2, exp); 114 mpz_mod (r2, r2, mod); 115 116 for (;;) 117 { 118 if (mpz_tstbit (exp2, 0)) 119 { 120 mpz_mul (r2, r2, base2); 121 mpz_mod (r2, r2, mod); 122 } 123 if (mpz_cmp_ui (exp2, 1) <= 0) 124 break; 125 mpz_mul (base2, base2, base2); 126 mpz_mod (base2, base2, mod); 127 mpz_tdiv_q_2exp (exp2, exp2, 1); 128 } 129 130 mpz_powm (r1, base, exp, mod); 131 MPZ_CHECK_FORMAT (r1); 132 133 if (mpz_cmp (r1, r2) != 0) 134 { 135 fprintf (stderr, "\nIncorrect results in test %d for operands:\n", i); 136 debug_mp (base, -16); 137 debug_mp (exp, -16); 138 debug_mp (mod, -16); 139 fprintf (stderr, "mpz_powm result:\n"); 140 debug_mp (r1, -16); 141 fprintf (stderr, "reference result:\n"); 142 debug_mp (r2, -16); 143 abort (); 144 } 145 146 if (mpz_tdiv_ui (mod, 2) == 0) 147 continue; 148 149 mpz_powm_sec (r1, base, exp, mod); 150 MPZ_CHECK_FORMAT (r1); 151 152 if (mpz_cmp (r1, r2) != 0) 153 { 154 fprintf (stderr, "\nIncorrect results in test %d for operands:\n", i); 155 debug_mp (base, -16); 156 debug_mp (exp, -16); 157 debug_mp (mod, -16); 158 fprintf (stderr, "mpz_powm_sec result:\n"); 159 debug_mp (r1, -16); 160 fprintf (stderr, "reference result:\n"); 161 debug_mp (r2, -16); 162 abort (); 163 } 164 } 165 166 mpz_clear (bs); 167 mpz_clear (base); 168 mpz_clear (exp); 169 mpz_clear (mod); 170 mpz_clear (r1); 171 mpz_clear (r2); 172 mpz_clear (t1); 173 mpz_clear (exp2); 174 mpz_clear (base2); 175 176 tests_end (); 177 exit (0); 178 } 179 180 void 181 debug_mp (mpz_t x, int base) 182 { 183 mpz_out_str (stderr, base, x); fputc ('\n', stderr); 184 } 185