1  /* Test mpz_invert.
       2  
       3  Copyright 1991, 1993, 1994, 1996, 1997, 2000-2005, 2008, 2009, 2012, 2014 Free
       4  Software Foundation, Inc.
       5  
       6  This file is part of the GNU MP Library test suite.
       7  
       8  The GNU MP Library test suite is free software; you can redistribute it
       9  and/or modify it under the terms of the GNU General Public License as
      10  published by the Free Software Foundation; either version 3 of the License,
      11  or (at your option) any later version.
      12  
      13  The GNU MP Library test suite is distributed in the hope that it will be
      14  useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
      15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General
      16  Public License for more details.
      17  
      18  You should have received a copy of the GNU General Public License along with
      19  the GNU MP Library test suite.  If not, see https://www.gnu.org/licenses/.  */
      20  
      21  #include <stdio.h>
      22  #include <stdlib.h>
      23  
      24  #include "gmp-impl.h"
      25  #include "tests.h"
      26  
      27  int
      28  main (int argc, char **argv)
      29  {
      30    mpz_t a, m, ainv, t;
      31    int test, r;
      32    gmp_randstate_ptr rands;
      33    mpz_t bs;
      34    unsigned long bsi, size_range;
      35    int reps = 1000;
      36  
      37    tests_start ();
      38    TESTS_REPS (reps, argv, argc);
      39  
      40    rands = RANDS;
      41  
      42    mpz_init (bs);
      43    mpz_init (a);
      44    mpz_init (m);
      45    mpz_init (ainv);
      46    mpz_init (t);
      47  
      48    for (test = 0; test < reps; test++)
      49      {
      50        mpz_urandomb (bs, rands, 32);
      51        size_range = mpz_get_ui (bs) % 16 + 2;
      52  
      53        mpz_urandomb (bs, rands, size_range);
      54        mpz_rrandomb (a, rands, mpz_get_ui (bs));
      55        do {
      56  	mpz_urandomb (bs, rands, size_range);
      57  	mpz_rrandomb (m, rands, mpz_get_ui (bs));
      58        } while (mpz_sgn (m) == 0);
      59  
      60        mpz_urandomb (bs, rands, 8);
      61        bsi = mpz_get_ui (bs);
      62  
      63        if ((bsi & 1) != 0)
      64  	mpz_neg (a, a);
      65        if ((bsi & 2) != 0)
      66  	mpz_neg (m, m);
      67  
      68        r = mpz_invert (ainv, a, m);
      69        if (r != 0)
      70  	{
      71  	  MPZ_CHECK_FORMAT (ainv);
      72  
      73  	  if (mpz_cmp_ui (ainv, 0) < 0 || mpz_cmpabs (ainv, m) >= 0)
      74  	    {
      75  	      fprintf (stderr, "ERROR in test %d\n", test);
      76  	      gmp_fprintf (stderr, "Inverse out of range.\n");
      77  	      gmp_fprintf (stderr, "a = %Zx\n", a);
      78  	      gmp_fprintf (stderr, "1/a = %Zx\n", ainv);
      79  	      gmp_fprintf (stderr, "m = %Zx\n", m);
      80  	      abort ();
      81  	    }
      82  
      83  	  mpz_mul (t, ainv, a);
      84  	  mpz_mod (t, t, m);
      85  
      86  	  if (mpz_cmp_ui (t, mpz_cmpabs_ui (m, 1) != 0) != 0)
      87  	    {
      88  	      fprintf (stderr, "ERROR in test %d\n", test);
      89  	      gmp_fprintf (stderr, "a^(-1)*a != 1 (mod m)\n");
      90  	      gmp_fprintf (stderr, "a = %Zx\n", a);
      91  	      gmp_fprintf (stderr, "m = %Zx\n", m);
      92  	      abort ();
      93  	    }
      94  	}
      95        else /* Inverse deos not exist */
      96  	{
      97  	  mpz_gcd (t, a, m);
      98  	  if (mpz_cmp_ui (t, 1) == 0)
      99  	    {
     100  	      fprintf (stderr, "ERROR in test %d\n", test);
     101  	      gmp_fprintf (stderr, "Inverse exists, but was not found.\n");
     102  	      gmp_fprintf (stderr, "a = %Zx\n", a);
     103  	      gmp_fprintf (stderr, "m = %Zx\n", m);
     104  	      abort ();
     105  	    }
     106  	}
     107      }
     108  
     109    mpz_clear (bs);
     110    mpz_clear (a);
     111    mpz_clear (m);
     112    mpz_clear (ainv);
     113    mpz_clear (t);
     114  
     115    tests_end ();
     116    exit (0);
     117  }