1/* Test mpz_powm_ui, mpz_mul, mpz_mod. 2 3Copyright 1991, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software 4Foundation, Inc. 5 6This file is part of the GNU MP Library. 7 8The GNU MP Library is free software; you can redistribute it and/or modify 9it under the terms of the GNU Lesser General Public License as published by 10the Free Software Foundation; either version 3 of the License, or (at your 11option) any later version. 12 13The GNU MP Library is distributed in the hope that it will be useful, but 14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16License for more details. 17 18You should have received a copy of the GNU Lesser General Public License 19along 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 28void dump_abort __GMP_PROTO ((mpz_t, mpz_t)); 29void debug_mp __GMP_PROTO ((mpz_t, int)); 30 31int 32main (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 148void 149dump_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 157void 158debug_mp (mpz_t x, int base) 159{ 160 mpz_out_str (stderr, base, x); fputc ('\n', stderr); 161} 162