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