1 /* Copyright 2013-2015 Free Software Foundation, Inc.
2
3 This file is part of the GNU MP Library test suite.
4
5 The GNU MP Library test suite is free software; you can redistribute it
6 and/or modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 3 of the License,
8 or (at your option) any later version.
9
10 The GNU MP Library test suite is distributed in the hope that it will be
11 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
13 Public License for more details.
14
15 You should have received a copy of the GNU General Public License along with
16 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
17
18 #include <stdio.h>
19 #include <stdlib.h> /* for strtol */
20
21 #include "gmp-impl.h"
22 #include "longlong.h"
23 #include "tests/tests.h"
24
25 #define MAX_SIZE 50
26
27 #define COUNT 200
28
29 static void
30 mpz_to_mpn (mp_ptr ap, mp_size_t an, const mpz_t b)
31 {
32 mp_size_t bn = mpz_size (b);
33 ASSERT_ALWAYS (bn <= an);
34 MPN_COPY_INCR (ap, mpz_limbs_read (b), bn);
35 MPN_ZERO (ap + bn, an - bn);
36 }
37
38 int
39 mpz_eq_mpn (mp_ptr ap, mp_size_t an, const mpz_t b)
40 {
41 mp_size_t bn = mpz_size (b);
42
43 return (bn >= 0 && bn <= an
44 && mpn_cmp (ap, mpz_limbs_read (b), bn) == 0
45 && (an == bn || mpn_zero_p (ap + bn, an - bn)));
46 }
47
48 static mp_bitcnt_t
49 bit_size (mp_srcptr xp, mp_size_t n)
50 {
51 MPN_NORMALIZE (xp, n);
52 return n > 0 ? mpn_sizeinbase (xp, n, 2) : 0;
53 }
54
55 int
56 main (int argc, char **argv)
57 {
58 gmp_randstate_ptr rands;
59 long count = COUNT;
60 mp_ptr mp;
61 mp_ptr ap;
62 mp_ptr tp;
63 mp_ptr scratch;
64 mpz_t m, a, r, g;
65 int test;
66 mp_limb_t ran;
67 mp_size_t itch;
68 TMP_DECL;
69
70 tests_start ();
71 rands = RANDS;
72
73
74 TMP_MARK;
75 mpz_init (m);
76 mpz_init (a);
77 mpz_init (r);
78 mpz_init (g);
79
80 TESTS_REPS (count, argv, argc);
81
82 mp = TMP_ALLOC_LIMBS (MAX_SIZE);
83 ap = TMP_ALLOC_LIMBS (MAX_SIZE);
84 tp = TMP_ALLOC_LIMBS (MAX_SIZE);
85 scratch = TMP_ALLOC_LIMBS (mpn_sec_invert_itch (MAX_SIZE) + 1);
86
87 for (test = 0; test < count; test++)
88 {
89 mp_bitcnt_t bits;
90 int rres, tres;
91 mp_size_t n;
92
93 bits = urandom () % (GMP_NUMB_BITS * MAX_SIZE) + 1;
94
95 if (test & 1)
96 mpz_rrandomb (m, rands, bits);
97 else
98 mpz_urandomb (m, rands, bits);
99 if (test & 2)
100 mpz_rrandomb (a, rands, bits);
101 else
102 mpz_urandomb (a, rands, bits);
103
104 mpz_setbit (m, 0);
105 if (test & 4)
106 {
107 /* Ensure it really is invertible */
108 if (mpz_sgn (a) == 0)
109 mpz_set_ui (a, 1);
110 else
111 for (;;)
112 {
113 mpz_gcd (g, a, m);
114 if (mpz_cmp_ui (g, 1) == 0)
115 break;
116 mpz_remove (a, a, g);
117 }
118 }
119
120 rres = mpz_invert (r, a, m);
121 if ( (test & 4) && !rres)
122 {
123 gmp_fprintf (stderr, "test %d: Not invertible!\n"
124 "m = %Zd\n"
125 "a = %Zd\n", test, m, a);
126 abort ();
127 }
128 ASSERT_ALWAYS (! (test & 4) || rres);
129
130 n = (bits + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS;
131 ASSERT_ALWAYS (n <= MAX_SIZE);
132 itch = mpn_sec_invert_itch (n);
133 scratch[itch] = ran = urandom ();
134
135 mpz_to_mpn (ap, n, a);
136 mpz_to_mpn (mp, n, m);
137 tres = mpn_sec_invert (tp, ap, mp, n,
138 bit_size (ap, n) + bit_size (mp, n),
139 scratch);
140
141 if (rres != tres || (rres == 1 && !mpz_eq_mpn (tp, n, r)) || ran != scratch[itch])
142 {
143 gmp_fprintf (stderr, "Test %d failed.\n"
144 "m = %Zd\n"
145 "a = %Zd\n", test, m, a);
146 fprintf (stderr, "ref ret: %d\n"
147 "got ret: %d\n", rres, tres);
148 if (rres)
149 gmp_fprintf (stderr, "ref: %Zd\n", r);
150 if (tres)
151 gmp_fprintf (stderr, "got: %Nd\n", tp, n);
152 if (ran != scratch[itch])
153 fprintf (stderr, "scratch[itch] changed.\n");
154 abort ();
155 }
156 }
157
158 TMP_FREE;
159
160 mpz_clear (m);
161 mpz_clear (a);
162 mpz_clear (r);
163 mpz_clear (g);
164
165 tests_end ();
166 return 0;
167 }