Mercurial > dropbear

comparison libtommath/bn_mp_kronecker.c @ 1692:1051e4eea25a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update LibTomMath to 1.2.0 (#84) * update C files * update other files * update headers * update makefiles * remove mp_set/get_double() * use ltm 1.2.0 API * update ltm_desc * use bundled tommath if system-tommath is too old * XMALLOC etc. were changed to MP_MALLOC etc.
author Steffen Jaeckel <s@jaeckel.eu>
date Tue, 26 May 2020 17:36:47 +0200
parents f52919ffd3b1
children
comparison
equal deleted inserted replaced
1691:2d3745d58843 1692:1051e4eea25a
1 #include "tommath_private.h" 1 #include "tommath_private.h"
2 #ifdef BN_MP_KRONECKER_C 2 #ifdef BN_MP_KRONECKER_C
3 3
4 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
5 * 5 /* SPDX-License-Identifier: Unlicense */
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 6
16 /* 7 /*
17 Kronecker symbol (a|p) 8 Kronecker symbol (a|p)
18 Straightforward implementation of algorithm 1.4.10 in 9 Straightforward implementation of algorithm 1.4.10 in
19 Henri Cohen: "A Course in Computational Algebraic Number Theory" 10 Henri Cohen: "A Course in Computational Algebraic Number Theory"
24 volume={138}, 15 volume={138},
25 year={2013}, 16 year={2013},
26 publisher={Springer Science \& Business Media} 17 publisher={Springer Science \& Business Media}
27 } 18 }
28 */ 19 */
29 int mp_kronecker(const mp_int *a, const mp_int *p, int *c) 20 mp_err mp_kronecker(const mp_int *a, const mp_int *p, int *c)
30 { 21 {
31 mp_int a1, p1, r; 22 mp_int a1, p1, r;
32 23 mp_err err;
33 int e = MP_OKAY;
34 int v, k; 24 int v, k;
35 25
36 static const int table[8] = {0, 1, 0, -1, 0, -1, 0, 1}; 26 static const int table[8] = {0, 1, 0, -1, 0, -1, 0, 1};
37 27
38 if (mp_iszero(p) != MP_NO) { 28 if (MP_IS_ZERO(p)) {
39 if ((a->used == 1) && (a->dp[0] == 1u)) { 29 if ((a->used == 1) && (a->dp[0] == 1u)) {
40 *c = 1; 30 *c = 1;
41 return e;
42 } else { 31 } else {
43 *c = 0; 32 *c = 0;
44 return e;
45 } 33 }
34 return MP_OKAY;
46 } 35 }
47 36
48 if ((mp_iseven(a) != MP_NO) && (mp_iseven(p) != MP_NO)) { 37 if (MP_IS_EVEN(a) && MP_IS_EVEN(p)) {
49 *c = 0; 38 *c = 0;
50 return e; 39 return MP_OKAY;
51 } 40 }
52 41
53 if ((e = mp_init_copy(&a1, a)) != MP_OKAY) { 42 if ((err = mp_init_copy(&a1, a)) != MP_OKAY) {
54 return e; 43 return err;
55 } 44 }
56 if ((e = mp_init_copy(&p1, p)) != MP_OKAY) { 45 if ((err = mp_init_copy(&p1, p)) != MP_OKAY) {
57 goto LBL_KRON_0; 46 goto LBL_KRON_0;
58 } 47 }
59 48
60 v = mp_cnt_lsb(&p1); 49 v = mp_cnt_lsb(&p1);
61 if ((e = mp_div_2d(&p1, v, &p1, NULL)) != MP_OKAY) { 50 if ((err = mp_div_2d(&p1, v, &p1, NULL)) != MP_OKAY) {
62 goto LBL_KRON_1; 51 goto LBL_KRON_1;
63 } 52 }
64 53
65 if ((v & 0x1) == 0) { 54 if ((v & 1) == 0) {
66 k = 1; 55 k = 1;
67 } else { 56 } else {
68 k = table[a->dp[0] & 7u]; 57 k = table[a->dp[0] & 7u];
69 } 58 }
70 59
73 if (a1.sign == MP_NEG) { 62 if (a1.sign == MP_NEG) {
74 k = -k; 63 k = -k;
75 } 64 }
76 } 65 }
77 66
78 if ((e = mp_init(&r)) != MP_OKAY) { 67 if ((err = mp_init(&r)) != MP_OKAY) {
79 goto LBL_KRON_1; 68 goto LBL_KRON_1;
80 } 69 }
81 70
82 for (;;) { 71 for (;;) {
83 if (mp_iszero(&a1) != MP_NO) { 72 if (MP_IS_ZERO(&a1)) {
84 if (mp_cmp_d(&p1, 1uL) == MP_EQ) { 73 if (mp_cmp_d(&p1, 1uL) == MP_EQ) {
85 *c = k; 74 *c = k;
86 goto LBL_KRON; 75 goto LBL_KRON;
87 } else { 76 } else {
88 *c = 0; 77 *c = 0;
89 goto LBL_KRON; 78 goto LBL_KRON;
90 } 79 }
91 } 80 }
92 81
93 v = mp_cnt_lsb(&a1); 82 v = mp_cnt_lsb(&a1);
94 if ((e = mp_div_2d(&a1, v, &a1, NULL)) != MP_OKAY) { 83 if ((err = mp_div_2d(&a1, v, &a1, NULL)) != MP_OKAY) {
95 goto LBL_KRON; 84 goto LBL_KRON;
96 } 85 }
97 86
98 if ((v & 0x1) == 1) { 87 if ((v & 1) == 1) {
99 k = k * table[p1.dp[0] & 7u]; 88 k = k * table[p1.dp[0] & 7u];
100 } 89 }
101 90
102 if (a1.sign == MP_NEG) { 91 if (a1.sign == MP_NEG) {
103 /* 92 /*
113 if ((a1.dp[0] & p1.dp[0] & 2u) != 0u) { 102 if ((a1.dp[0] & p1.dp[0] & 2u) != 0u) {
114 k = -k; 103 k = -k;
115 } 104 }
116 } 105 }
117 106
118 if ((e = mp_copy(&a1, &r)) != MP_OKAY) { 107 if ((err = mp_copy(&a1, &r)) != MP_OKAY) {
119 goto LBL_KRON; 108 goto LBL_KRON;
120 } 109 }
121 r.sign = MP_ZPOS; 110 r.sign = MP_ZPOS;
122 if ((e = mp_mod(&p1, &r, &a1)) != MP_OKAY) { 111 if ((err = mp_mod(&p1, &r, &a1)) != MP_OKAY) {
123 goto LBL_KRON; 112 goto LBL_KRON;
124 } 113 }
125 if ((e = mp_copy(&r, &p1)) != MP_OKAY) { 114 if ((err = mp_copy(&r, &p1)) != MP_OKAY) {
126 goto LBL_KRON; 115 goto LBL_KRON;
127 } 116 }
128 } 117 }
129 118
130 LBL_KRON: 119 LBL_KRON:
132 LBL_KRON_1: 121 LBL_KRON_1:
133 mp_clear(&p1); 122 mp_clear(&p1);
134 LBL_KRON_0: 123 LBL_KRON_0:
135 mp_clear(&a1); 124 mp_clear(&a1);
136 125
137 return e; 126 return err;
138 } 127 }
139 128
140 #endif 129 #endif
141
142 /* ref: HEAD -> master, tag: v1.1.0 */
143 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
144 /* commit time: 2019-01-28 20:32:32 +0100 */