Implement BN_kronecker test.

Modify "CHANGES" entry for BN_mod_inverse (it's not just avoiding BN_div
that increases performance, avoiding BN_mul also helps)

diff --git a/CHANGES b/CHANGES
index 7a5bac81d0ce94852349cb2547a92337b48ec275..a469186a2703c6f6f33e535bfc7e0e13eda2e080 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,9 +4,8 @@
  Changes between 0.9.6 and 0.9.7  [xx XXX 2000]
 
   *) Make BN_mod_inverse faster by explicitly handling small quotients
-     in the Euclid loop instead of always using BN_div.
-     (Speed gain about 20% for small moduli [256 or 512 bits], about
-     30% for larger ones [1024 or 2048 bits].)
+     in the Euclid loop. (Speed gain about 20% for small moduli [256 or
+     512 bits], about 30% for larger ones [1024 or 2048 bits].)
      [Bodo Moeller]
 
   *) Disable ssl2_peek and ssl3_peek (i.e., both implementations

diff --git a/crypto/bn/bntest.c b/crypto/bn/bntest.c
index 866ac1d0a09797b7455ce55cf966e283b405223e..84412f31f31a7f60d09fd74a3f5592508ac8b3f2 100644 (file)
--- a/crypto/bn/bntest.c
+++ b/crypto/bn/bntest.c
@@ -900,8 +900,32 @@ int test_exp(BIO *bp, BN_CTX *ctx)
        return(1);
        }
 
+static void genprime_cb(int p, int n, void *arg)
+       {
+       char c='*';
+
+       if (p == 0) c='.';
+       if (p == 1) c='+';
+       if (p == 2) c='*';
+       if (p == 3) c='\n';
+       putc(c, stderr);
+       fflush(stderr);
+       (void)n;
+       (void)arg;
+       }
+
 int test_kron(BIO *bp, BN_CTX *ctx)
        {
+       BIGNUM *a,*b,*r;
+       int i;
+       int legendre, kronecker;
+       int ret = 0;
+
+       a = BN_new();
+       b = BN_new();
+       r = BN_new();
+       if (a == NULL || b == NULL || r == NULL) goto err;
+       
        /* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
         * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
         * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
@@ -911,9 +935,61 @@ int test_kron(BIO *bp, BN_CTX *ctx)
         * don't want to test whether  b  is prime but whether BN_kronecker
         * works.) */
 
-       /* XXX */
+       if (!BN_generate_prime(b, 512, 0, NULL, NULL, genprime_cb, NULL)) goto err;
+       putc('\n', stderr);
+       if (1 != BN_is_prime(b, 10, NULL, ctx, NULL))
+               {
+               fprintf(stderr, "BN_is_prime failed\n");
+               goto err;
+               }
 
-       return(1);
+       for (i = 0; i < num0; i++)
+               {
+               if (!BN_rand(a, 512, 0, 0)) goto err;
+               if (!BN_nnmod(a, a, b, ctx)) goto err;
+               
+               /* r := (b-1)/2  (note that b is odd) */
+               if (!BN_copy(r, b)) goto err;
+               if (!BN_sub_word(r, 1)) goto err;
+               if (!BN_rshift1(r, r)) goto err;
+               /* r := a^r mod b */
+               if (!BN_mod_exp(r, a, r, b, ctx)) goto err;
+
+               if (BN_is_word(r, 1))
+                       legendre = 1;
+               else
+                       {
+                       if (!BN_add_word(r, 1)) goto err;
+                       if (0 != BN_cmp(r, b))
+                               {
+                               fprintf(stderr, "Legendre symbol computation failed\n");
+                               goto err;
+                               }
+                       legendre = -1;
+                       }
+
+               kronecker = BN_kronecker(a, b, ctx);
+               if (kronecker < -1) goto err;
+               
+               if (legendre != kronecker)
+                       {
+                       fprintf(stderr, "legendre != kronecker; a = ");
+                       BN_print_fp(stderr, a);
+                       fprintf(stderr, ", a = ");
+                       BN_print_fp(stderr, b);
+                       fprintf(stderr, "\n");
+                       goto err;
+                       }
+
+               fprintf(stderr, "ok\n");
+               }
+
+       ret = 1;
+ err:
+       if (a != NULL) BN_free(a);
+       if (b != NULL) BN_free(b);
+       if (r != NULL) BN_free(r);
+       return ret;
        }
 
 int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)