1 #include "tommath_private.h"
2 #ifdef BN_MP_MONTGOMERY_REDUCE_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 /* SPDX-License-Identifier: Unlicense */
5
6 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
mp_montgomery_reduce(mp_int * x,const mp_int * n,mp_digit rho)7 mp_err mp_montgomery_reduce(mp_int *x, const mp_int *n, mp_digit rho)
8 {
9 int ix, digs;
10 mp_err err;
11 mp_digit mu;
12
13 /* can the fast reduction [comba] method be used?
14 *
15 * Note that unlike in mul you're safely allowed *less*
16 * than the available columns [255 per default] since carries
17 * are fixed up in the inner loop.
18 */
19 digs = (n->used * 2) + 1;
20 if ((digs < MP_WARRAY) &&
21 (x->used <= MP_WARRAY) &&
22 (n->used < MP_MAXFAST)) {
23 return s_mp_montgomery_reduce_fast(x, n, rho);
24 }
25
26 /* grow the input as required */
27 if (x->alloc < digs) {
28 if ((err = mp_grow(x, digs)) != MP_OKAY) {
29 return err;
30 }
31 }
32 x->used = digs;
33
34 for (ix = 0; ix < n->used; ix++) {
35 /* mu = ai * rho mod b
36 *
37 * The value of rho must be precalculated via
38 * montgomery_setup() such that
39 * it equals -1/n0 mod b this allows the
40 * following inner loop to reduce the
41 * input one digit at a time
42 */
43 mu = (mp_digit)(((mp_word)x->dp[ix] * (mp_word)rho) & MP_MASK);
44
45 /* a = a + mu * m * b**i */
46 {
47 int iy;
48 mp_digit *tmpn, *tmpx, u;
49 mp_word r;
50
51 /* alias for digits of the modulus */
52 tmpn = n->dp;
53
54 /* alias for the digits of x [the input] */
55 tmpx = x->dp + ix;
56
57 /* set the carry to zero */
58 u = 0;
59
60 /* Multiply and add in place */
61 for (iy = 0; iy < n->used; iy++) {
62 /* compute product and sum */
63 r = ((mp_word)mu * (mp_word)*tmpn++) +
64 (mp_word)u + (mp_word)*tmpx;
65
66 /* get carry */
67 u = (mp_digit)(r >> (mp_word)MP_DIGIT_BIT);
68
69 /* fix digit */
70 *tmpx++ = (mp_digit)(r & (mp_word)MP_MASK);
71 }
72 /* At this point the ix'th digit of x should be zero */
73
74
75 /* propagate carries upwards as required*/
76 while (u != 0u) {
77 *tmpx += u;
78 u = *tmpx >> MP_DIGIT_BIT;
79 *tmpx++ &= MP_MASK;
80 }
81 }
82 }
83
84 /* at this point the n.used'th least
85 * significant digits of x are all zero
86 * which means we can shift x to the
87 * right by n.used digits and the
88 * residue is unchanged.
89 */
90
91 /* x = x/b**n.used */
92 mp_clamp(x);
93 mp_rshd(x, n->used);
94
95 /* if x >= n then x = x - n */
96 if (mp_cmp_mag(x, n) != MP_LT) {
97 return s_mp_sub(x, n, x);
98 }
99
100 return MP_OKAY;
101 }
102 #endif
103