summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn_kron.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn_kron.c')
-rw-r--r--src/lib/libcrypto/bn/bn_kron.c195
1 files changed, 0 insertions, 195 deletions
diff --git a/src/lib/libcrypto/bn/bn_kron.c b/src/lib/libcrypto/bn/bn_kron.c
deleted file mode 100644
index a170d688e9..0000000000
--- a/src/lib/libcrypto/bn/bn_kron.c
+++ /dev/null
@@ -1,195 +0,0 @@
1/* $OpenBSD: bn_kron.c,v 1.15 2023/07/08 12:21:58 beck Exp $ */
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_local.h"
57
58/*
59 * Kronecker symbol, implemented according to Henri Cohen, "A Course in
60 * Computational Algebraic Number Theory", Algorithm 1.4.10.
61 *
62 * Returns -1, 0, or 1 on success and -2 on error.
63 */
64
65int
66BN_kronecker(const BIGNUM *A, const BIGNUM *B, BN_CTX *ctx)
67{
68 /* tab[BN_lsw(n) & 7] = (-1)^((n^2 - 1)) / 8) for odd values of n. */
69 static const int tab[8] = {0, 1, 0, -1, 0, -1, 0, 1};
70 BIGNUM *a, *b, *tmp;
71 int k, v;
72 int ret = -2;
73
74 BN_CTX_start(ctx);
75
76 if ((a = BN_CTX_get(ctx)) == NULL)
77 goto end;
78 if ((b = BN_CTX_get(ctx)) == NULL)
79 goto end;
80
81 if (!bn_copy(a, A))
82 goto end;
83 if (!bn_copy(b, B))
84 goto end;
85
86 /*
87 * Cohen's step 1:
88 */
89
90 /* If b is zero, output 1 if |a| is 1, otherwise output 0. */
91 if (BN_is_zero(b)) {
92 ret = BN_abs_is_word(a, 1);
93 goto end;
94 }
95
96 /*
97 * Cohen's step 2:
98 */
99
100 /* If both are even, they have a factor in common, so output 0. */
101 if (!BN_is_odd(a) && !BN_is_odd(b)) {
102 ret = 0;
103 goto end;
104 }
105
106 /* Factorize b = 2^v * u with odd u and replace b with u. */
107 v = 0;
108 while (!BN_is_bit_set(b, v))
109 v++;
110 if (!BN_rshift(b, b, v))
111 goto end;
112
113 /* If v is even set k = 1, otherwise set it to (-1)^((a^2 - 1) / 8). */
114 k = 1;
115 if (v % 2 != 0)
116 k = tab[BN_lsw(a) & 7];
117
118 /*
119 * If b is negative, replace it with -b and if a is also negative
120 * replace k with -k.
121 */
122 if (BN_is_negative(b)) {
123 BN_set_negative(b, 0);
124
125 if (BN_is_negative(a))
126 k = -k;
127 }
128
129 /*
130 * Now b is positive and odd, so compute the Jacobi symbol (a/b)
131 * and multiply it by k.
132 */
133
134 while (1) {
135 /*
136 * Cohen's step 3:
137 */
138
139 /* b is positive and odd. */
140
141 /* If a is zero output k if b is one, otherwise output 0. */
142 if (BN_is_zero(a)) {
143 ret = BN_is_one(b) ? k : 0;
144 goto end;
145 }
146
147 /* Factorize a = 2^v * u with odd u and replace a with u. */
148 v = 0;
149 while (!BN_is_bit_set(a, v))
150 v++;
151 if (!BN_rshift(a, a, v))
152 goto end;
153
154 /* If v is odd, multiply k with (-1)^((b^2 - 1) / 8). */
155 if (v % 2 != 0)
156 k *= tab[BN_lsw(b) & 7];
157
158 /*
159 * Cohen's step 4:
160 */
161
162 /*
163 * Apply the reciprocity law: multiply k by (-1)^((a-1)(b-1)/4).
164 *
165 * This expression is -1 if and only if a and b are 3 (mod 4).
166 * In turn, this is the case if and only if their two's
167 * complement representations have the second bit set.
168 * a could be negative in the first iteration, b is positive.
169 */
170 if ((BN_is_negative(a) ? ~BN_lsw(a) : BN_lsw(a)) & BN_lsw(b) & 2)
171 k = -k;
172
173 /*
174 * (a, b) := (b mod |a|, |a|)
175 *
176 * Once this is done, we know that 0 < a < b at the start of the
177 * loop. Since b is strictly decreasing, the loop terminates.
178 */
179
180 if (!BN_nnmod(b, b, a, ctx))
181 goto end;
182
183 tmp = a;
184 a = b;
185 b = tmp;
186
187 BN_set_negative(b, 0);
188 }
189
190 end:
191 BN_CTX_end(ctx);
192
193 return ret;
194}
195LCRYPTO_ALIAS(BN_kronecker);
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-12-23 13:57:42 +0000