testsuite/ecc-redc-test.c

   1 #include "testutils.h"
   2
   3 static void
   4 ref_redc (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
   5 {
   6   mpz_t t;
   7   mpz_t m, a;
   8   mp_size_t an;
   9
  10   mpz_init (t);
  11   mpz_setbit (t, mn * GMP_NUMB_BITS);
  12
  13   mpz_roinit_n (m, mp, mn);
  14
  15   an = 2*mn;
  16   while (an > 0 && ap[an-1] == 0)
  17     an--;
  18
  19   mpz_roinit_n (a, ap, an);
  20
  21   mpz_invert (t, t, m);
  22   mpz_mul (t, t, a);
  23   mpz_mod (t, t, m);
  24
  25   mpz_limbs_copy (rp, t, mn);
  26
  27   mpz_clear (t);
  28 }
  29
  30 #define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
  31 #define MAX_SIZE (2*MAX_ECC_SIZE)
  32 #define COUNT 50000
  33
  34 void
  35 test_main (void)
  36 {
  37   gmp_randstate_t state;
  38   mp_limb_t a[MAX_SIZE];
  39   mp_limb_t m[MAX_SIZE];
  40   mp_limb_t ref[MAX_SIZE];
  41   unsigned i;
  42   mpz_t r;
  43
  44   gmp_randinit_default (state);
  45
  46   mpz_init (r);
  47
  48   for (i = 0; ecc_curves[i]; i++)
  49     {
  50       const struct ecc_curve *ecc = ecc_curves[i];
  51       unsigned j;
  52       if (!ecc->redc)
  53         continue;
  54
  55       for (j = 0; j < COUNT; j++)
  56         {
  57           if (j & 1)
  58             mpz_rrandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
  59           else
  60             mpz_urandomb (r, state, 2*ecc->size * GMP_NUMB_BITS);
  61
  62           mpz_limbs_copy (a, r, 2*ecc->size);
  63
  64           ref_redc (ref, a, ecc->p, ecc->size);
  65
  66           mpn_copyi (m, a, 2*ecc->size);
  67           ecc->redc (ecc, m);
  68           if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
  69             mpn_sub_n (m, m, ecc->p, ecc->size);
  70
  71           if (mpn_cmp (m, ref, ecc->size))
  72             {
  73               fprintf (stderr, "ecc->redc failed: bit_size = %u\n",
  74                        ecc->bit_size);
  75               gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
  76               gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
  77               gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
  78               abort ();
  79             }
  80
  81           mpn_copyi (m, a, 2*ecc->size);
  82           ecc_generic_redc (ecc, m);
  83           if (mpn_cmp (m, ecc->p, ecc->size) >= 0)
  84             mpn_sub_n (m, m, ecc->p, ecc->size);
  85
  86           if (mpn_cmp (m, ref, ecc->size))
  87             {
  88               fprintf (stderr, "ecc_generic_redc failed: bit_size = %u\n",
  89                        ecc->bit_size);
  90               gmp_fprintf (stderr, "a   = %Nx\n", a, 2*ecc->size);
  91               gmp_fprintf (stderr, "m   = %Nx (bad)\n", m, ecc->size);
  92               gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size);
  93               abort ();
  94             }
  95         }
  96     }
  97
  98   mpz_clear (r);
  99   gmp_randclear (state);
 100 }