crypto/bn/bn_exp.c: SPARC portability fix.
[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 "cryptlib.h"
57 #include "bn_lcl.h"
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_check_top(a);
78         bn_check_top(b);
79
80         BN_CTX_start(ctx);
81         A = BN_CTX_get(ctx);
82         B = BN_CTX_get(ctx);
83         if (B == NULL) goto end;
84         
85         err = !BN_copy(A, a);
86         if (err) goto end;
87         err = !BN_copy(B, b);
88         if (err) goto end;
89
90         /*
91          * Kronecker symbol, imlemented according to Henri Cohen,
92          * "A Course in Computational Algebraic Number Theory"
93          * (algorithm 1.4.10).
94          */
95
96         /* Cohen's step 1: */
97
98         if (BN_is_zero(B))
99                 {
100                 ret = BN_abs_is_word(A, 1);
101                 goto end;
102                 }
103         
104         /* Cohen's step 2: */
105
106         if (!BN_is_odd(A) && !BN_is_odd(B))
107                 {
108                 ret = 0;
109                 goto end;
110                 }
111
112         /* now  B  is non-zero */
113         i = 0;
114         while (!BN_is_bit_set(B, i))
115                 i++;
116         err = !BN_rshift(B, B, i);
117         if (err) goto end;
118         if (i & 1)
119                 {
120                 /* i is odd */
121                 /* (thus  B  was even, thus  A  must be odd!)  */
122
123                 /* set 'ret' to $(-1)^{(A^2-1)/8}$ */
124                 ret = tab[BN_lsw(A) & 7];
125                 }
126         else
127                 {
128                 /* i is even */
129                 ret = 1;
130                 }
131         
132         if (B->neg)
133                 {
134                 B->neg = 0;
135                 if (A->neg)
136                         ret = -ret;
137                 }
138
139         /* now  B  is positive and odd, so what remains to be done is
140          * to compute the Jacobi symbol  (A/B)  and multiply it by 'ret' */
141
142         while (1)
143                 {
144                 /* Cohen's step 3: */
145
146                 /*  B  is positive and odd */
147
148                 if (BN_is_zero(A))
149                         {
150                         ret = BN_is_one(B) ? ret : 0;
151                         goto end;
152                         }
153
154                 /* now  A  is non-zero */
155                 i = 0;
156                 while (!BN_is_bit_set(A, i))
157                         i++;
158                 err = !BN_rshift(A, A, i);
159                 if (err) goto end;
160                 if (i & 1)
161                         {
162                         /* i is odd */
163                         /* multiply 'ret' by  $(-1)^{(B^2-1)/8}$ */
164                         ret = ret * tab[BN_lsw(B) & 7];
165                         }
166         
167                 /* Cohen's step 4: */
168                 /* multiply 'ret' by  $(-1)^{(A-1)(B-1)/4}$ */
169                 if ((A->neg ? ~BN_lsw(A) : BN_lsw(A)) & BN_lsw(B) & 2)
170                         ret = -ret;
171                 
172                 /* (A, B) := (B mod |A|, |A|) */
173                 err = !BN_nnmod(B, B, A, ctx);
174                 if (err) goto end;
175                 tmp = A; A = B; B = tmp;
176                 tmp->neg = 0;
177                 }
178 end:
179         BN_CTX_end(ctx);
180         if (err)
181                 return -2;
182         else
183                 return ret;
184         }