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 rands;
  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 (rands);
  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
  53       for (j = 0; j < COUNT; j++)
  54         {
  55           if (j & 1)
  56             mpz_rrandomb (r, rands, 2*ecc->p.size * GMP_NUMB_BITS);
  57           else
  58             mpz_urandomb (r, rands, 2*ecc->p.size * GMP_NUMB_BITS);
  59
  60           mpz_limbs_copy (a, r, 2*ecc->p.size);
  61
  62           ref_redc (ref, a, ecc->p.m, ecc->p.size);
  63
  64           if (ecc->p.reduce != ecc->p.mod)
  65             {
  66               mpn_copyi (m, a, 2*ecc->p.size);
  67               ecc->p.reduce (&ecc->p, m);
  68               if (mpn_cmp (m, ecc->p.m, ecc->p.size) >= 0)
  69                 mpn_sub_n (m, m, ecc->p.m, ecc->p.size);
  70
  71               if (mpn_cmp (m, ref, ecc->p.size))
  72                 {
  73                   fprintf (stderr, "ecc->p.reduce failed: bit_size = %u\n",
  74                            ecc->p.bit_size);
  75                   fprintf (stderr, "a   = ");
  76                   mpn_out_str (stderr, 16, a, 2*ecc->p.size);
  77                   fprintf (stderr, "\nm   = ");
  78                   mpn_out_str (stderr, 16, m, ecc->p.size);
  79                   fprintf (stderr, " (bad)\nref   = ");
  80                   mpn_out_str (stderr, 16, ref, ecc->p.size);
  81                   fprintf (stderr, "\n");
  82                   abort ();
  83                 }
  84             }
  85           if (ecc->p.redc_size != 0)
  86             {
  87               mpn_copyi (m, a, 2*ecc->p.size);
  88               if (ecc->p.m[0] == 1)
  89                 ecc_pm1_redc (&ecc->p, m);
  90               else
  91                 ecc_pp1_redc (&ecc->p, m);
  92
  93               if (mpn_cmp (m, ecc->p.m, ecc->p.size) >= 0)
  94                 mpn_sub_n (m, m, ecc->p.m, ecc->p.size);
  95
  96               if (mpn_cmp (m, ref, ecc->p.size))
  97                 {
  98                   fprintf (stderr, "ecc_p%c1_redc failed: bit_size = %u\n",
  99                            (ecc->p.m[0] == 1) ? 'm' : 'p', ecc->p.bit_size);
 100                   fprintf (stderr, "a   = ");
 101                   mpn_out_str (stderr, 16, a, 2*ecc->p.size);
 102                   fprintf (stderr, "\nm   = ");
 103                   mpn_out_str (stderr, 16, m, ecc->p.size);
 104                   fprintf (stderr, " (bad)\nref = ");
 105                   mpn_out_str (stderr, 16, ref, ecc->p.size);
 106                   fprintf (stderr, "\n");
 107                   abort ();
 108                 }
 109             }
 110         }
 111     }
 112
 113   mpz_clear (r);
 114   gmp_randclear (rands);
 115 }