Put the first stage of my bignum debugging adventures into CVS. This code
[openssl.git] / crypto / bn / bn_kron.c
1 /* crypto/bn/bn_kron.c */
2 /* ====================================================================
3  * Copyright (c) 1998-2000 The OpenSSL Project.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer. 
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in
14  *    the documentation and/or other materials provided with the
15  *    distribution.
16  *
17  * 3. All advertising materials mentioning features or use of this
18  *    software must display the following acknowledgment:
19  *    "This product includes software developed by the OpenSSL Project
20  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21  *
22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23  *    endorse or promote products derived from this software without
24  *    prior written permission. For written permission, please contact
25  *    openssl-core@openssl.org.
26  *
27  * 5. Products derived from this software may not be called "OpenSSL"
28  *    nor may "OpenSSL" appear in their names without prior written
29  *    permission of the OpenSSL Project.
30  *
31  * 6. Redistributions of any form whatsoever must retain the following
32  *    acknowledgment:
33  *    "This product includes software developed by the OpenSSL Project
34  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35  *
36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47  * OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This product includes cryptographic software written by Eric Young
51  * (eay@cryptsoft.com).  This product includes software written by Tim
52  * Hudson (tjh@cryptsoft.com).
53  *
54  */
55
56 #include "bn_lcl.h"
57
58
59 /* least significant word */
60 #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0])
61
62 /* Returns -2 for errors because both -1 and 0 are valid results. */
63 int BN_kronecker(const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
64         {
65         int i;
66         int ret = -2; /* avoid 'uninitialized' warning */
67         int err = 0;
68         BIGNUM *A, *B, *tmp;
69         /* In 'tab', only odd-indexed entries are relevant:
70          * For any odd BIGNUM n,
71          *     tab[BN_lsw(n) & 7]
72          * is $(-1)^{(n^2-1)/8}$ (using TeX notation).
73          * Note that the sign of n does not matter.
74          */
75         static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
76
77         BN_CTX_start(ctx);
78         A = BN_CTX_get(ctx);
79         B = BN_CTX_get(ctx);
80         if (B == NULL) goto end;
81         
82         err = !BN_copy(A, a);
83         if (err) goto end;
84         err = !BN_copy(B, b);
85         if (err) goto end;
86
87         /*
88          * Kronecker symbol, imlemented according to Henri Cohen,
89          * "A Course in Computational Algebraic Number Theory"
90          * (algorithm 1.4.10).
91          */
92
93         /* Cohen's step 1: */
94
95         if (BN_is_zero(B))
96                 {
97                 ret = BN_abs_is_word(A, 1);
98                 goto end;
99                 }
100         
101         /* Cohen's step 2: */
102
103         if (!BN_is_odd(A) && !BN_is_odd(B))
104                 {
105                 ret = 0;
106                 goto end;
107                 }
108
109         /* now  B  is non-zero */
110         i = 0;
111         while (!BN_is_bit_set(B, i))
112                 i++;
113         err = !BN_rshift(B, B, i);
114         if (err) goto end;
115         if (i & 1)
116                 {
117                 /* i is odd */
118                 /* (thus  B  was even, thus  A  must be odd!)  */
119
120                 /* set 'ret' to $(-1)^{(A^2-1)/8}$ */
121                 ret = tab[BN_lsw(A) & 7];
122                 }
123         else
124                 {
125                 /* i is even */
126                 ret = 1;
127                 }
128         
129         if (B->neg)
130                 {
131                 B->neg = 0;
132                 if (A->neg)
133                         ret = -ret;
134                 }
135
136         /* now  B  is positive and odd, so what remains to be done is
137          * to compute the Jacobi symbol  (A/B)  and multiply it by 'ret' */
138
139         while (1)
140                 {
141                 /* Cohen's step 3: */
142
143                 /*  B  is positive and odd */
144
145                 if (BN_is_zero(A))
146                         {
147                         ret = BN_is_one(B) ? ret : 0;
148                         goto end;
149                         }
150
151                 /* now  A  is non-zero */
152                 i = 0;
153                 while (!BN_is_bit_set(A, i))
154                         i++;
155                 err = !BN_rshift(A, A, i);
156                 if (err) goto end;
157                 if (i & 1)
158                         {
159                         /* i is odd */
160                         /* multiply 'ret' by  $(-1)^{(B^2-1)/8}$ */
161                         ret = ret * tab[BN_lsw(B) & 7];
162                         }
163         
164                 /* Cohen's step 4: */
165                 /* multiply 'ret' by  $(-1)^{(A-1)(B-1)/4}$ */
166                 if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
167                         ret = -ret;
168                 
169                 /* (A, B) := (B mod |A|, |A|) */
170                 err = !BN_nnmod(B, B, A, ctx);
171                 if (err) goto end;
172                 tmp = A; A = B; B = tmp;
173                 tmp->neg = 0;
174                 }
175         
176  end:
177         BN_CTX_end(ctx);
178         if (err)
179                 return -2;
180         else
181                 return ret;
182         }