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