1 #include "tommath_private.h"
2 #ifdef BN_MP_REDUCE_2K_L_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4 *
5 * LibTomMath is a library that provides multiple-precision
6 * integer arithmetic as well as number theoretic functionality.
7 *
8 * The library was designed directly after the MPI library by
9 * Michael Fromberger but has been written from scratch with
10 * additional optimizations in place.
11 *
12 * SPDX-License-Identifier: Unlicense
13 */
14
15 /* reduces a modulo n where n is of the form 2**p - d
16 This differs from reduce_2k since "d" can be larger
17 than a single digit.
18 */
mp_reduce_2k_l(mp_int * a,const mp_int * n,const mp_int * d)19 int mp_reduce_2k_l(mp_int *a, const mp_int *n, const mp_int *d)
20 {
21 mp_int q;
22 int p, res;
23
24 if ((res = mp_init(&q)) != MP_OKAY) {
25 return res;
26 }
27
28 p = mp_count_bits(n);
29 top:
30 /* q = a/2**p, a = a mod 2**p */
31 if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) {
32 goto LBL_ERR;
33 }
34
35 /* q = q * d */
36 if ((res = mp_mul(&q, d, &q)) != MP_OKAY) {
37 goto LBL_ERR;
38 }
39
40 /* a = a + q */
41 if ((res = s_mp_add(a, &q, a)) != MP_OKAY) {
42 goto LBL_ERR;
43 }
44
45 if (mp_cmp_mag(a, n) != MP_LT) {
46 if ((res = s_mp_sub(a, n, a)) != MP_OKAY) {
47 goto LBL_ERR;
48 }
49 goto top;
50 }
51
52 LBL_ERR:
53 mp_clear(&q);
54 return res;
55 }
56
57 #endif
58
59 /* ref: $Format:%D$ */
60 /* git commit: $Format:%H$ */
61 /* commit time: $Format:%ai$ */
62