Mercurial > dropbear

comparison libtommath/bn_mp_jacobi.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 8bba51a55704
children
comparison
equal deleted inserted replaced
1654:cc0fc5131c5c 1655:f52919ffd3b1
1 #include <tommath_private.h> 1 #include "tommath_private.h"
2 #ifdef BN_MP_JACOBI_C 2 #ifdef BN_MP_JACOBI_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 * 4 *
5 * LibTomMath is a library that provides multiple-precision 5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality. 6 * integer arithmetic as well as number theoretic functionality.
7 * 7 *
8 * The library was designed directly after the MPI library by 8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with 9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place. 10 * additional optimizations in place.
11 * 11 *
12 * The library is free for all purposes without any express 12 * SPDX-License-Identifier: Unlicense
13 * guarantee it works.
14 *
15 * Tom St Denis, [email protected], http://libtom.org
16 */ 13 */
17 14
18 /* computes the jacobi c = (a | n) (or Legendre if n is prime) 15 /* computes the jacobi c = (a | n) (or Legendre if n is prime)
19 * HAC pp. 73 Algorithm 2.149 16 * Kept for legacy reasons, please use mp_kronecker() instead
20 * HAC is wrong here, as the special case of (0 | 1) is not
21 * handled correctly.
22 */ 17 */
23 int mp_jacobi (mp_int * a, mp_int * n, int *c) 18 int mp_jacobi(const mp_int *a, const mp_int *n, int *c)
24 { 19 {
25 mp_int a1, p1; 20 /* if a < 0 return MP_VAL */
26 int k, s, r, res; 21 if (mp_isneg(a) == MP_YES) {
27 mp_digit residue; 22 return MP_VAL;
23 }
28 24
29 /* if a < 0 return MP_VAL */ 25 /* if n <= 0 return MP_VAL */
30 if (mp_isneg(a) == MP_YES) { 26 if (mp_cmp_d(n, 0uL) != MP_GT) {
31 return MP_VAL; 27 return MP_VAL;
32 } 28 }
33 29
34 /* if n <= 0 return MP_VAL */ 30 return mp_kronecker(a, n, c);
35 if (mp_cmp_d(n, 0) != MP_GT) {
36 return MP_VAL;
37 }
38
39 /* step 1. handle case of a == 0 */
40 if (mp_iszero (a) == MP_YES) {
41 /* special case of a == 0 and n == 1 */
42 if (mp_cmp_d (n, 1) == MP_EQ) {
43 *c = 1;
44 } else {
45 *c = 0;
46 }
47 return MP_OKAY;
48 }
49
50 /* step 2. if a == 1, return 1 */
51 if (mp_cmp_d (a, 1) == MP_EQ) {
52 *c = 1;
53 return MP_OKAY;
54 }
55
56 /* default */
57 s = 0;
58
59 /* step 3. write a = a1 * 2**k */
60 if ((res = mp_init_copy (&a1, a)) != MP_OKAY) {
61 return res;
62 }
63
64 if ((res = mp_init (&p1)) != MP_OKAY) {
65 goto LBL_A1;
66 }
67
68 /* divide out larger power of two */
69 k = mp_cnt_lsb(&a1);
70 if ((res = mp_div_2d(&a1, k, &a1, NULL)) != MP_OKAY) {
71 goto LBL_P1;
72 }
73
74 /* step 4. if e is even set s=1 */
75 if ((k & 1) == 0) {
76 s = 1;
77 } else {
78 /* else set s=1 if p = 1/7 (mod 8) or s=-1 if p = 3/5 (mod 8) */
79 residue = n->dp[0] & 7;
80
81 if ((residue == 1) || (residue == 7)) {
82 s = 1;
83 } else if ((residue == 3) || (residue == 5)) {
84 s = -1;
85 }
86 }
87
88 /* step 5. if p == 3 (mod 4) *and* a1 == 3 (mod 4) then s = -s */
89 if ( ((n->dp[0] & 3) == 3) && ((a1.dp[0] & 3) == 3)) {
90 s = -s;
91 }
92
93 /* if a1 == 1 we're done */
94 if (mp_cmp_d (&a1, 1) == MP_EQ) {
95 *c = s;
96 } else {
97 /* n1 = n mod a1 */
98 if ((res = mp_mod (n, &a1, &p1)) != MP_OKAY) {
99 goto LBL_P1;
100 }
101 if ((res = mp_jacobi (&p1, &a1, &r)) != MP_OKAY) {
102 goto LBL_P1;
103 }
104 *c = s * r;
105 }
106
107 /* done */
108 res = MP_OKAY;
109 LBL_P1:mp_clear (&p1);
110 LBL_A1:mp_clear (&a1);
111 return res;
112 } 31 }
113 #endif 32 #endif
114 33
115 /* ref: $Format:%D$ */ 34 /* ref: HEAD -> master, tag: v1.1.0 */
116 /* git commit: $Format:%H$ */ 35 /* git commit: 08549ad6bc8b0cede0b357a9c341c5c6473a9c55 */
117 /* commit time: $Format:%ai$ */ 36 /* commit time: 2019-01-28 20:32:32 +0100 */