Mercurial > dropbear

comparison libtommath/bn_mp_kronecker.c @ 1655:f52919ffd3b1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update ltm to 1.1.0 and enable FIPS 186.4 compliant key-generation (#79) * make key-generation compliant to FIPS 186.4 * fix includes in tommath_class.h * update fuzzcorpus instead of error-out * fixup fuzzing make-targets * update Makefile.in * apply necessary patches to ltm sources * clean-up not required ltm files * update to vanilla ltm 1.1.0 this already only contains the required files * remove set/get double
author Steffen Jaeckel <s_jaeckel@gmx.de>
date Mon, 16 Sep 2019 15:50:38 +0200
parents
children 1051e4eea25a
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include "tommath_private.h"
2 #ifdef BN_MP_KRONECKER_C
3
4 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5 *
6 * LibTomMath is a library that provides multiple-precision
7 * integer arithmetic as well as number theoretic functionality.
8 *
9 * The library was designed directly after the MPI library by
10 * Michael Fromberger but has been written from scratch with
11 * additional optimizations in place.
12 *
13 * SPDX-License-Identifier: Unlicense
14 */
15
16 /*
17 Kronecker symbol (a|p)
18 Straightforward implementation of algorithm 1.4.10 in
19 Henri Cohen: "A Course in Computational Algebraic Number Theory"
20
21 @book{cohen2013course,
22 title={A course in computational algebraic number theory},
23 author={Cohen, Henri},
24 volume={138},
25 year={2013},
26 publisher={Springer Science \& Business Media}
27 }
28 */
29 int mp_kronecker(const mp_int *a, const mp_int *p, int *c)
30 {
31 mp_int a1, p1, r;
32
33 int e = MP_OKAY;
34 int v, k;
35
36 static const int table[8] = {0, 1, 0, -1, 0, -1, 0, 1};
37
38 if (mp_iszero(p) != MP_NO) {
39 if ((a->used == 1) && (a->dp[0] == 1u)) {
40 *c = 1;
41 return e;
42 } else {
43 *c = 0;
44 return e;
45 }
46 }
47
48 if ((mp_iseven(a) != MP_NO) && (mp_iseven(p) != MP_NO)) {
49 *c = 0;
50 return e;
51 }
52
53 if ((e = mp_init_copy(&a1, a)) != MP_OKAY) {
54 return e;
55 }
56 if ((e = mp_init_copy(&p1, p)) != MP_OKAY) {
57 goto LBL_KRON_0;
58 }
59
60 v = mp_cnt_lsb(&p1);
61 if ((e = mp_div_2d(&p1, v, &p1, NULL)) != MP_OKAY) {
62 goto LBL_KRON_1;
63 }
64
65 if ((v & 0x1) == 0) {
66 k = 1;
67 } else {
68 k = table[a->dp[0] & 7u];
69 }
70
71 if (p1.sign == MP_NEG) {
72 p1.sign = MP_ZPOS;
73 if (a1.sign == MP_NEG) {
74 k = -k;
75 }
76 }
77
78 if ((e = mp_init(&r)) != MP_OKAY) {
79 goto LBL_KRON_1;
80 }
81
82 for (;;) {
83 if (mp_iszero(&a1) != MP_NO) {
84 if (mp_cmp_d(&p1, 1uL) == MP_EQ) {
85 *c = k;
86 goto LBL_KRON;
87 } else {
88 *c = 0;
89 goto LBL_KRON;
90 }
91 }
92
93 v = mp_cnt_lsb(&a1);
94 if ((e = mp_div_2d(&a1, v, &a1, NULL)) != MP_OKAY) {
95 goto LBL_KRON;
96 }
97
98 if ((v & 0x1) == 1) {
99 k = k * table[p1.dp[0] & 7u];
100 }
101
102 if (a1.sign == MP_NEG) {
103 /*
104 * Compute k = (-1)^((a1)*(p1-1)/4) * k
105 * a1.dp[0] + 1 cannot overflow because the MSB
106 * of the type mp_digit is not set by definition
107 */
108 if (((a1.dp[0] + 1u) & p1.dp[0] & 2u) != 0u) {
109 k = -k;
110 }
111 } else {
112 /* compute k = (-1)^((a1-1)*(p1-1)/4) * k */
113 if ((a1.dp[0] & p1.dp[0] & 2u) != 0u) {
114 k = -k;
115 }
116 }
117
118 if ((e = mp_copy(&a1, &r)) != MP_OKAY) {
119 goto LBL_KRON;
120 }
121 r.sign = MP_ZPOS;
122 if ((e = mp_mod(&p1, &r, &a1)) != MP_OKAY) {
123 goto LBL_KRON;
124 }
125 if ((e = mp_copy(&r, &p1)) != MP_OKAY) {
126 goto LBL_KRON;
127 }
128 }
129
130 LBL_KRON:
131 mp_clear(&r);
132 LBL_KRON_1:
133 mp_clear(&p1);
134 LBL_KRON_0:
135 mp_clear(&a1);
136
137 return e;
138 }
139
140 #endif
141
142 /* ref: HEAD -> master, tag: v1.1.0 */
143 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
144 /* commit time: 2019-01-28 20:32:32 +0100 */