1 /* Test mpz_powm_ui, mpz_mul, mpz_mod. 2 3 Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software 4 Foundation, Inc. 5 6 This file is part of the GNU MP Library. 7 8 The GNU MP Library is free software; you can redistribute it and/or modify 9 it under the terms of the GNU Lesser General Public License as published by 10 the Free Software Foundation; either version 3 of the License, or (at your 11 option) any later version. 12 13 The GNU MP Library is distributed in the hope that it will be useful, but 14 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16 License for more details. 17 18 You should have received a copy of the GNU Lesser General Public License 19 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 20 21 #include <stdio.h> 22 #include <stdlib.h> 23 24 #include "gmp.h" 25 #include "gmp-impl.h" 26 #include "tests.h" 27 28 void dump_abort __GMP_PROTO ((mpz_t, mpz_t)); 29 void debug_mp __GMP_PROTO ((mpz_t, int)); 30 31 int 32 main (int argc, char **argv) 33 { 34 mpz_t base, exp, mod; 35 mpz_t r1, r2, base2; 36 mp_size_t base_size, exp_size, mod_size; 37 unsigned long int exp2; 38 int i; 39 int reps = 1000; 40 gmp_randstate_ptr rands; 41 mpz_t bs; 42 unsigned long bsi, size_range; 43 44 tests_start (); 45 rands = RANDS; 46 47 mpz_init (bs); 48 49 if (argc == 2) 50 reps = atoi (argv[1]); 51 52 mpz_init (base); 53 mpz_init (exp); 54 mpz_init (mod); 55 mpz_init (r1); 56 mpz_init (r2); 57 mpz_init (base2); 58 59 for (i = 0; i < reps; i++) 60 { 61 mpz_urandomb (bs, rands, 32); 62 size_range = mpz_get_ui (bs) % 13 + 2; 63 64 do /* Loop until mathematically well-defined. */ 65 { 66 mpz_urandomb (bs, rands, size_range); 67 base_size = mpz_get_ui (bs); 68 mpz_rrandomb (base, rands, base_size); 69 70 mpz_urandomb (bs, rands, 6L); 71 exp_size = mpz_get_ui (bs); 72 mpz_rrandomb (exp, rands, exp_size); 73 exp2 = mpz_getlimbn (exp, (mp_size_t) 0); 74 } 75 while (mpz_cmp_ui (base, 0) == 0 && exp2 == 0); 76 77 do 78 { 79 mpz_urandomb (bs, rands, size_range); 80 mod_size = mpz_get_ui (bs); 81 mpz_rrandomb (mod, rands, mod_size); 82 } 83 while (mpz_cmp_ui (mod, 0) == 0); 84 85 mpz_urandomb (bs, rands, 2); 86 bsi = mpz_get_ui (bs); 87 if ((bsi & 1) != 0) 88 mpz_neg (base, base); 89 90 /* printf ("%ld %ld\n", SIZ (base), SIZ (mod)); */ 91 92 #if 0 93 putc ('\n', stderr); 94 debug_mp (base, -16); 95 debug_mp (mod, -16); 96 #endif 97 98 mpz_powm_ui (r1, base, exp2, mod); 99 MPZ_CHECK_FORMAT (r1); 100 101 mpz_set_ui (r2, 1); 102 mpz_set (base2, base); 103 104 mpz_mod (r2, r2, mod); /* needed when exp==0 and mod==1 */ 105 while (exp2 != 0) 106 { 107 if (exp2 % 2 != 0) 108 { 109 mpz_mul (r2, r2, base2); 110 mpz_mod (r2, r2, mod); 111 } 112 mpz_mul (base2, base2, base2); 113 mpz_mod (base2, base2, mod); 114 exp2 = exp2 / 2; 115 } 116 117 #if 0 118 debug_mp (r1, -16); 119 debug_mp (r2, -16); 120 #endif 121 122 if (mpz_cmp (r1, r2) != 0) 123 { 124 fprintf (stderr, "\ntest %d: Incorrect results for operands:\n", i); 125 debug_mp (base, -16); 126 debug_mp (exp, -16); 127 debug_mp (mod, -16); 128 fprintf (stderr, "mpz_powm_ui result:\n"); 129 debug_mp (r1, -16); 130 fprintf (stderr, "reference result:\n"); 131 debug_mp (r2, -16); 132 abort (); 133 } 134 } 135 136 mpz_clear (bs); 137 mpz_clear (base); 138 mpz_clear (exp); 139 mpz_clear (mod); 140 mpz_clear (r1); 141 mpz_clear (r2); 142 mpz_clear (base2); 143 144 tests_end (); 145 exit (0); 146 } 147 148 void 149 dump_abort (mpz_t dividend, mpz_t divisor) 150 { 151 fprintf (stderr, "ERROR\n"); 152 fprintf (stderr, "dividend = "); debug_mp (dividend, -16); 153 fprintf (stderr, "divisor = "); debug_mp (divisor, -16); 154 abort(); 155 } 156 157 void 158 debug_mp (mpz_t x, int base) 159 { 160 mpz_out_str (stderr, base, x); fputc ('\n', stderr); 161 } 162