Home | History | Annotate | Line # | Download | only in mpn 
      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 }
    168