crypto/bn/bn_kron.c

   1 /*
   2  * Copyright 2000-2016 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include "internal/cryptlib.h"
  11 #include "bn_lcl.h"
  12
  13 /* least significant word */
  14 #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
  15
  16 /* Returns -2 for errors because both -1 and 0 are valid results. */
  17 int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
  18 {
  19     int i;
  20     int ret = -2;               /* avoid 'uninitialized' warning */
  21     int err = 0;
  22     BIGNUM *A, *B, *tmp;
  23     /*-
  24      * In 'tab', only odd-indexed entries are relevant:
  25      * For any odd BIGNUM n,
  26      *     tab[BN_lsw(n) & 7]
  27      * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
  28      * Note that the sign of n does not matter.
  29      */
  30     static const int tab[8] = { 0, 1, 0, -1, 0, -1, 0, 1 };
  31
  32     bn_check_top(a);
  33     bn_check_top(b);
  34
  35     BN_CTX_start(ctx);
  36     A = BN_CTX_get(ctx);
  37     B = BN_CTX_get(ctx);
  38     if (B == NULL)
  39         goto end;
  40
  41     err = !BN_copy(A, a);
  42     if (err)
  43         goto end;
  44     err = !BN_copy(B, b);
  45     if (err)
  46         goto end;
  47
  48     /*
  49      * Kronecker symbol, implemented according to Henri Cohen,
  50      * "A Course in Computational Algebraic Number Theory"
  51      * (algorithm 1.4.10).
  52      */
  53
  54     /* Cohen's step 1: */
  55
  56     if (BN_is_zero(B)) {
  57         ret = BN_abs_is_word(A, 1);
  58         goto end;
  59     }
  60
  61     /* Cohen's step 2: */
  62
  63     if (!BN_is_odd(A) && !BN_is_odd(B)) {
  64         ret = 0;
  65         goto end;
  66     }
  67
  68     /* now  B  is non-zero */
  69     i = 0;
  70     while (!BN_is_bit_set(B, i))
  71         i++;
  72     err = !BN_rshift(B, B, i);
  73     if (err)
  74         goto end;
  75     if (i & 1) {
  76         /* i is odd */
  77         /* (thus  B  was even, thus  A  must be odd!)  */
  78
  79         /* set 'ret' to $(-1)^{(A^2-1)/8}$ */
  80         ret = tab[BN_lsw(A) & 7];
  81     } else {
  82         /* i is even */
  83         ret = 1;
  84     }
  85
  86     if (B->neg) {
  87         B->neg = 0;
  88         if (A->neg)
  89             ret = -ret;
  90     }
  91
  92     /*
  93      * now B is positive and odd, so what remains to be done is to compute
  94      * the Jacobi symbol (A/B) and multiply it by 'ret'
  95      */
  96
  97     while (1) {
  98         /* Cohen's step 3: */
  99
 100         /*  B  is positive and odd */
 101
 102         if (BN_is_zero(A)) {
 103             ret = BN_is_one(B) ? ret : 0;
 104             goto end;
 105         }
 106
 107         /* now  A  is non-zero */
 108         i = 0;
 109         while (!BN_is_bit_set(A, i))
 110             i++;
 111         err = !BN_rshift(A, A, i);
 112         if (err)
 113             goto end;
 114         if (i & 1) {
 115             /* i is odd */
 116             /* multiply 'ret' by  $(-1)^{(B^2-1)/8}$ */
 117             ret = ret * tab[BN_lsw(B) & 7];
 118         }
 119
 120         /* Cohen's step 4: */
 121         /* multiply 'ret' by  $(-1)^{(A-1)(B-1)/4}$ */
 122         if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
 123             ret = -ret;
 124
 125         /* (A, B) := (B mod |A|, |A|) */
 126         err = !BN_nnmod(B, B, A, ctx);
 127         if (err)
 128             goto end;
 129         tmp = A;
 130         A = B;
 131         B = tmp;
 132         tmp->neg = 0;
 133     }
 134  end:
 135     BN_CTX_end(ctx);
 136     if (err)
 137         return -2;
 138     else
 139         return ret;
 140 }