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