/src/relic/src/bn/relic_bn_mod.c

Source
/*
 * RELIC is an Efficient LIbrary for Cryptography
 * Copyright (c) 2009 RELIC Authors
 *
 * This file is part of RELIC. RELIC is legal property of its developers,
 * whose names are not listed here. Please refer to the COPYRIGHT file
 * for contact information.
 *
 * RELIC is free software; you can redistribute it and/or modify it under the
 * terms of the version 2.1 (or later) of the GNU Lesser General Public License
 * as published by the Free Software Foundation; or version 2.0 of the Apache
 * License as published by the Apache Software Foundation. See the LICENSE files
 * for more details.
 *
 * RELIC is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the LICENSE files for more details.
 *
 * You should have received a copy of the GNU Lesser General Public or the
 * Apache License along with RELIC. If not, see <https://www.gnu.org/licenses/>
 * or <https://www.apache.org/licenses/>.
 */

/**
 * @file
 *
 * Implementation of the multiple precision integer modular reduction
 * functions.
 *
 * @ingroup bn
 */

#include "relic_core.h"
#include "relic_bn_low.h"

/*============================================================================*/
/* Public definitions                                                         */
/*============================================================================*/

void bn_mod_2b(bn_t c, const bn_t a, int b) {
  int i, first, d;

  if (b <= 0) {
    bn_zero(c);
    return;
  }

  if (b >= (int)(a->used * RLC_DIG)) {
    bn_copy(c, a);
    return;
  }

  bn_copy(c, a);

  RLC_RIP(b, d, b);

  first = (d) + (b == 0 ? 0 : 1);
  for (i = first; i < c->used; i++) {
    c->dp[i] = 0;
  }

  c->dp[d] &= RLC_MASK(b);

  bn_trim(c);
}

void bn_mod_dig(dig_t *c, const bn_t a, dig_t b) {
  bn_div_rem_dig(NULL, c, a, b);
}

void bn_mod_basic(bn_t c, const bn_t a, const bn_t m) {
  bn_div_rem(NULL, c, a, m);
}

#if BN_MOD == BARRT || !defined(STRIP)

void bn_mod_pre_barrt(bn_t u, const bn_t m) {
  if (bn_is_zero(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_set_2b(u, m->used * 2 * RLC_DIG);
  bn_div(u, u, m);
}

void bn_mod_barrt(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
  bn_t q, t;
  int mu, neg;

  bn_null(q);
  bn_null(t);

  if (bn_is_zero(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  if (bn_cmp_abs(a, m) == RLC_LT) {
    bn_copy(c, a);
    return;
  }

  if (a->used > 2 * m->used) {
    bn_mod(c, a, m);
    return;
  }

  RLC_TRY {
    bn_new(q);
    bn_new(t);
    bn_zero(t);

    neg = (bn_sign(a) == RLC_NEG);
    bn_abs(c, a);

    bn_rsh(q, c, (m->used - 1) * RLC_DIG);

    if (m->used > ((dig_t)1) << (RLC_DIG - 1)) {
      bn_mul(t, q, u);
    } else {
      bn_grow(t, q->used + u->used);
      t->used = q->used + u->used;
      mu = u->used - q->used;
      if (q->used > u->used) {
        bn_muld_low(t->dp, q->dp, q->used, u->dp, u->used, mu, t->used);
      } else {
        mu = (mu > u->used - q->used ? mu - (u->used - q->used) : 0);
        bn_muld_low(t->dp, u->dp, u->used, q->dp, q->used, mu, t->used);
      }
      bn_trim(t);
    }

    bn_rsh(q, t, (m->used + 1) * RLC_DIG);

    if (q->used > m->used) {
      bn_muld_low(t->dp, q->dp, q->used, m->dp, m->used, 0, q->used + 1);
    } else {
      bn_muld_low(t->dp, m->dp, m->used, q->dp, q->used, 0, m->used + 1);
    }
    t->used = m->used + 1;
    bn_trim(t);

    bn_mod_2b(q, t, RLC_DIG * (m->used + 1));
    bn_mod_2b(t, c, RLC_DIG * (m->used + 1));
    bn_sub(t, t, q);

    if (bn_sign(t) == RLC_NEG) {
      bn_set_dig(q, (dig_t)1);
      bn_lsh(q, q, (m->used + 1) * RLC_DIG);
      bn_add(t, t, q);
    }

    while (bn_cmp(t, m) != RLC_LT) {
      bn_sub(t, t, m);
    }

    bn_copy(c, t);
    if (neg) {
      bn_sub(c, m, c);
    }
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    bn_free(q);
    bn_free(t);
  }
}

#endif /* BN_MOD == BARRT || !defined(STRIP) */

#if BN_MOD == MONTY || (defined(WITH_FP) && FP_RDC == MONTY) || !defined(STRIP)

void bn_mod_pre_monty(bn_t u, const bn_t m) {
  dig_t x, b = m->dp[0];

  if (bn_is_even(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  x = (((b + 2) & 4) << 1) + b;       /* here x*a==1 mod 2**4 */
  x *= (dig_t)2 - b * x;            /* here x*a==1 mod 2**8 */
#if WSIZE > 8
  x *= (dig_t)2 - b * x;            /* here x*a==1 mod 2**16 */
#endif
#if WSIZE > 16
  x *= (dig_t)2 - b * x;            /* here x*a==1 mod 2**32 */
#endif
#if WSIZE > 32
  x *= (dig_t)2 - b * x;            /* here x*a==1 mod 2**64 */
#endif
  /* u = -1/m0 (mod 2^RLC_DIG) */
  bn_set_dig(u, -x);
}

void bn_mod_monty_conv(bn_t c, const bn_t a, const bn_t m) {
  if (bn_is_even(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_mod(c, a, m);
  bn_lsh(c, c, m->used * RLC_DIG);
  bn_mod(c, c, m);
}

void bn_mod_monty_back(bn_t c, const bn_t a, const bn_t m) {
  bn_t u;

  bn_null(u);

  if (bn_is_even(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  RLC_TRY {
    bn_new(u);
    bn_mod_pre_monty(u, m);
    bn_mod_monty(c, a, m, u);
  } RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  } RLC_FINALLY {
    bn_free(u);
  }
}

#if BN_MUL == BASIC || !defined(STRIP)

void bn_mod_monty_basic(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
  int digits, i;
  dig_t r, u0, *tmp;
  bn_t t;

  if (bn_is_even(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_null(t);
  digits = 2 * m->used;

  RLC_TRY {
    bn_new_size(t, digits);
    bn_zero(t);
    bn_copy(t, a);

    u0 = u->dp[0];
    tmp = t->dp;

    for (i = 0; i < m->used; i++, tmp++) {
      r = (dig_t)(*tmp * u0);
      *tmp = bn_mula_low(tmp, m->dp, r, m->used);
    }
    if (bn_addn_low(t->dp, t->dp, tmp, m->used)) {
      bn_subn_low(t->dp, t->dp, m->dp, m->used);
    }
    t->used = m->used;
    bn_trim(t);

    if (bn_cmp_abs(t, m) != RLC_LT) {
      bn_sub(t, t, m);
    }

    bn_copy(c, t);
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    bn_free(t);
  }
}

#endif /* BN_MUL == BASIC || !defined(STRIP) */

#if BN_MUL == COMBA || !defined(STRIP)

void bn_mod_monty_comba(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
  int digits;
  bn_t t;

  if (bn_is_even(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_null(t);
  digits = 2 * m->used;

  RLC_TRY {
    bn_new_size(t, digits);
    bn_zero(t);

    bn_modn_low(t->dp, a->dp, a->used, m->dp, m->used, u->dp[0]);
    t->used = m->used;

    bn_trim(t);
    if (bn_cmp_abs(t, m) != RLC_LT) {
      bn_sub(t, t, m);
    }
    bn_copy(c, t);
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    bn_free(t);
  }
}

#endif /* BN_MUL == COMBA || !defined(STRIP) */

#endif /* BN_MOD == MONTY || (WITH_FP && FP_RDC == MONTY) || !defined(STRIP) */

#if BN_MOD == PMERS || !defined(STRIP)

void bn_mod_pre_pmers(bn_t u, const bn_t m) {
  if (bn_is_zero(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_set_2b(u, bn_bits(m));
  bn_sub(u, u, m);
}

void bn_mod_pmers(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
  bn_t q, t;
  int neg = 0, bits = bn_bits(m);

  if (bn_is_zero(m) || bn_sign(m) != RLC_POS) {
    RLC_THROW(ERR_NO_VALID);
    return;
  }

  bn_null(q);
  bn_null(t);

  RLC_TRY {
    /* Implement algorithm 10.25 from HEHC. */

    bn_new(q);
    bn_new(t);

    bn_copy(c, a);
    if (bn_sign(c) == RLC_NEG) {
      neg = 1;
      bn_sub(c, m, c);
    }

    bn_rsh(q, c, bits);
    bn_mod_2b(c, c, bits);

    while (bits > 0 && !bn_is_zero(q)) {
      if (u -> used == 1) {
        bn_mul_dig(t, q, u->dp[0]);
      } else {
        bn_mul(t, q, u);
      }
      bn_rsh(q, t, bits);
      bn_mod_2b(t, t, bits);

      bn_add(c, c, t);
    }
    while (bits > 0 && bn_cmp_abs(c, m) != RLC_LT) {
      bn_sub(c, c, m);
    }

    if (neg) {
      bn_sub(c, m, c);
    }
  }
  RLC_CATCH_ANY {
    RLC_THROW(ERR_CAUGHT);
  }
  RLC_FINALLY {
    bn_free(t);
    bn_free(q);
  }
}

#endif /* BN_MOD == PMERS || !defined(STRIP) */

Coverage Report

Created: 2026-06-07 07:04

Line	Count	Source
1		/*
2		* RELIC is an Efficient LIbrary for Cryptography
3		* Copyright (c) 2009 RELIC Authors
4		*
5		* This file is part of RELIC. RELIC is legal property of its developers,
6		* whose names are not listed here. Please refer to the COPYRIGHT file
7		* for contact information.
8		*
9		* RELIC is free software; you can redistribute it and/or modify it under the
10		* terms of the version 2.1 (or later) of the GNU Lesser General Public License
11		* as published by the Free Software Foundation; or version 2.0 of the Apache
12		* License as published by the Apache Software Foundation. See the LICENSE files
13		* for more details.
14		*
15		* RELIC is distributed in the hope that it will be useful, but WITHOUT ANY
16		* WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
17		* A PARTICULAR PURPOSE. See the LICENSE files for more details.
18		*
19		* You should have received a copy of the GNU Lesser General Public or the
20		* Apache License along with RELIC. If not, see <https://www.gnu.org/licenses/>
21		* or <https://www.apache.org/licenses/>.
22		*/
23
24		/**
25		* @file
26		*
27		* Implementation of the multiple precision integer modular reduction
28		* functions.
29		*
30		* @ingroup bn
31		*/
32
33		#include "relic_core.h"
34		#include "relic_bn_low.h"
35
36		/============================================================================/
37		/* Public definitions */
38		/============================================================================/
39
40	9.72k	void bn_mod_2b(bn_t c, const bn_t a, int b) {
41	9.72k	int i, first, d;
42
43	9.72k	if (b <= 0) {
44	0	bn_zero(c);
45	0	return;
46	0	}
47
48	9.72k	if (b >= (int)(a->used * RLC_DIG)) {
49	56	bn_copy(c, a);
50	56	return;
51	56	}
52
53	9.66k	bn_copy(c, a);
54
55	9.66k	RLC_RIP(b, d, b);
56
57	9.66k	first = (d) + (b == 0 ? 0 : 1);
58	175k	for (i = first; i < c->used; i++) {
59	165k	c->dp[i] = 0;
60	165k	}
61
62	9.66k	c->dp[d] &= RLC_MASK(b);
63
64	9.66k	bn_trim(c);
65	9.66k	}
66
67	19.2k	void bn_mod_dig(dig_t *c, const bn_t a, dig_t b) {
68	19.2k	bn_div_rem_dig(NULL, c, a, b);
69	19.2k	}
70
71	482k	void bn_mod_basic(bn_t c, const bn_t a, const bn_t m) {
72	482k	bn_div_rem(NULL, c, a, m);
73	482k	}
74
75		#if BN_MOD == BARRT \|\| !defined(STRIP)
76
77	67	void bn_mod_pre_barrt(bn_t u, const bn_t m) {
78	67	if (bn_is_zero(m) \|\| bn_sign(m) != RLC_POS) {
79	8	RLC_THROW(ERR_NO_VALID);
80	8	return;
81	8	}
82
83	59	bn_set_2b(u, m->used * 2 * RLC_DIG);
84	59	bn_div(u, u, m);
85	59	}
86
87	46	void bn_mod_barrt(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
88	46	bn_t q, t;
89	46	int mu, neg;
90
91	46	bn_null(q);
92	46	bn_null(t);
93
94	46	if (bn_is_zero(m) \|\| bn_sign(m) != RLC_POS) {
95	0	RLC_THROW(ERR_NO_VALID);
96	0	return;
97	0	}
98
99	46	if (bn_cmp_abs(a, m) == RLC_LT) {
100	8	bn_copy(c, a);
101	8	return;
102	8	}
103
104	38	if (a->used > 2 * m->used) {
105	7	bn_mod(c, a, m);
106	7	return;
107	7	}
108
109	31	RLC_TRY {
110	31	bn_new(q);
111	31	bn_new(t);
112	31	bn_zero(t);
113
114	31	neg = (bn_sign(a) == RLC_NEG);
115	31	bn_abs(c, a);
116
117	31	bn_rsh(q, c, (m->used - 1) * RLC_DIG);
118
119	31	if (m->used > ((dig_t)1) << (RLC_DIG - 1)) {
120	0	bn_mul(t, q, u);
121	31	} else {
122	31	bn_grow(t, q->used + u->used);
123	31	t->used = q->used + u->used;
124	31	mu = u->used - q->used;
125	31	if (q->used > u->used) {
126	0	bn_muld_low(t->dp, q->dp, q->used, u->dp, u->used, mu, t->used);
127	31	} else {
128	31	mu = (mu > u->used - q->used ? mu - (u->used - q->used) : 0);
129	31	bn_muld_low(t->dp, u->dp, u->used, q->dp, q->used, mu, t->used);
130	31	}
131	31	bn_trim(t);
132	31	}
133
134	31	bn_rsh(q, t, (m->used + 1) * RLC_DIG);
135
136	31	if (q->used > m->used) {
137	3	bn_muld_low(t->dp, q->dp, q->used, m->dp, m->used, 0, q->used + 1);
138	28	} else {
139	28	bn_muld_low(t->dp, m->dp, m->used, q->dp, q->used, 0, m->used + 1);
140	28	}
141	31	t->used = m->used + 1;
142	31	bn_trim(t);
143
144	31	bn_mod_2b(q, t, RLC_DIG * (m->used + 1));
145	31	bn_mod_2b(t, c, RLC_DIG * (m->used + 1));
146	31	bn_sub(t, t, q);
147
148	31	if (bn_sign(t) == RLC_NEG) {
149	10	bn_set_dig(q, (dig_t)1);
150	10	bn_lsh(q, q, (m->used + 1) * RLC_DIG);
151	10	bn_add(t, t, q);
152	10	}
153
154	40	while (bn_cmp(t, m) != RLC_LT) {
155	9	bn_sub(t, t, m);
156	9	}
157
158	31	bn_copy(c, t);
159	31	if (neg) {
160	0	bn_sub(c, m, c);
161	0	}
162	31	}
163	62	RLC_CATCH_ANY {
164	0	RLC_THROW(ERR_CAUGHT);
165	0	}
166	62	RLC_FINALLY {
167	31	bn_free(q);
168	31	bn_free(t);
169	31	}
170	31	}
171
172		#endif /* BN_MOD == BARRT \|\| !defined(STRIP) */
173
174		#if BN_MOD == MONTY \|\| (defined(WITH_FP) && FP_RDC == MONTY) \|\| !defined(STRIP)
175
176	12.0k	void bn_mod_pre_monty(bn_t u, const bn_t m) {
177	12.0k	dig_t x, b = m->dp[0];
178
179	12.0k	if (bn_is_even(m) \|\| bn_sign(m) != RLC_POS) {
180	270	RLC_THROW(ERR_NO_VALID);
181	270	return;
182	270	}
183
184	11.7k	x = (((b + 2) & 4) << 1) + b; /* here xa==1 mod 24 /
185	11.7k	x = (dig_t)2 - b x; /* here xa==1 mod 28 /
186	11.7k	#if WSIZE > 8
187	11.7k	x = (dig_t)2 - b x; /* here xa==1 mod 216 /
188	11.7k	#endif
189	11.7k	#if WSIZE > 16
190	11.7k	x = (dig_t)2 - b x; /* here xa==1 mod 232 /
191	11.7k	#endif
192	11.7k	#if WSIZE > 32
193	11.7k	x = (dig_t)2 - b x; /* here xa==1 mod 264 /
194	11.7k	#endif
195		/* u = -1/m0 (mod 2^RLC_DIG) */
196	11.7k	bn_set_dig(u, -x);
197	11.7k	}
198
199	6.96k	void bn_mod_monty_conv(bn_t c, const bn_t a, const bn_t m) {
200	6.96k	if (bn_is_even(m) \|\| bn_sign(m) != RLC_POS) {
201	24	RLC_THROW(ERR_NO_VALID);
202	24	return;
203	24	}
204
205	6.96k	bn_mod(c, a, m);
206	6.93k	bn_lsh(c, c, m->used * RLC_DIG);
207	6.93k	bn_mod(c, c, m);
208	6.93k	}
209
210	3.46k	void bn_mod_monty_back(bn_t c, const bn_t a, const bn_t m) {
211	3.46k	bn_t u;
212
213	3.46k	bn_null(u);
214
215	3.46k	if (bn_is_even(m) \|\| bn_sign(m) != RLC_POS) {
216	0	RLC_THROW(ERR_NO_VALID);
217	0	return;
218	0	}
219
220	3.46k	RLC_TRY {
221	3.46k	bn_new(u);
222	3.46k	bn_mod_pre_monty(u, m);
223	3.46k	bn_mod_monty(c, a, m, u);
224	6.92k	} RLC_CATCH_ANY {
225	0	RLC_THROW(ERR_CAUGHT);
226	6.92k	} RLC_FINALLY {
227	3.46k	bn_free(u);
228	3.46k	}
229	3.46k	}
230
231		#if BN_MUL == BASIC \|\| !defined(STRIP)
232
233	49	void bn_mod_monty_basic(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
234	49	int digits, i;
235	49	dig_t r, u0, *tmp;
236	49	bn_t t;
237
238	49	if (bn_is_even(m) \|\| bn_sign(m) != RLC_POS) {
239	0	RLC_THROW(ERR_NO_VALID);
240	0	return;
241	0	}
242
243	49	bn_null(t);
244	49	digits = 2 * m->used;
245
246	49	RLC_TRY {
247	49	bn_new_size(t, digits);
248	49	bn_zero(t);
249	49	bn_copy(t, a);
250
251	49	u0 = u->dp[0];
252	49	tmp = t->dp;
253
254	950	for (i = 0; i < m->used; i++, tmp++) {
255	901	r = (dig_t)(tmp u0);
256	901	*tmp = bn_mula_low(tmp, m->dp, r, m->used);
257	901	}
258	49	if (bn_addn_low(t->dp, t->dp, tmp, m->used)) {
259	0	bn_subn_low(t->dp, t->dp, m->dp, m->used);
260	0	}
261	49	t->used = m->used;
262	49	bn_trim(t);
263
264	49	if (bn_cmp_abs(t, m) != RLC_LT) {
265	0	bn_sub(t, t, m);
266	0	}
267
268	49	bn_copy(c, t);
269	49	}
270	98	RLC_CATCH_ANY {
271	0	RLC_THROW(ERR_CAUGHT);
272	0	}
273	98	RLC_FINALLY {
274	49	bn_free(t);
275	49	}
276	49	}
277
278		#endif /* BN_MUL == BASIC \|\| !defined(STRIP) */
279
280		#if BN_MUL == COMBA \|\| !defined(STRIP)
281
282	1.23M	void bn_mod_monty_comba(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
283	1.23M	int digits;
284	1.23M	bn_t t;
285
286	1.23M	if (bn_is_even(m) \|\| bn_sign(m) != RLC_POS) {
287	0	RLC_THROW(ERR_NO_VALID);
288	0	return;
289	0	}
290
291	1.23M	bn_null(t);
292	1.23M	digits = 2 * m->used;
293
294	1.23M	RLC_TRY {
295	1.23M	bn_new_size(t, digits);
296	1.23M	bn_zero(t);
297
298	1.23M	bn_modn_low(t->dp, a->dp, a->used, m->dp, m->used, u->dp[0]);
299	1.23M	t->used = m->used;
300
301	1.23M	bn_trim(t);
302	1.23M	if (bn_cmp_abs(t, m) != RLC_LT) {
303	7.17k	bn_sub(t, t, m);
304	7.17k	}
305	1.23M	bn_copy(c, t);
306	1.23M	}
307	2.47M	RLC_CATCH_ANY {
308	0	RLC_THROW(ERR_CAUGHT);
309	0	}
310	2.47M	RLC_FINALLY {
311	1.23M	bn_free(t);
312	1.23M	}
313	1.23M	}
314
315		#endif /* BN_MUL == COMBA \|\| !defined(STRIP) */
316
317		#endif /* BN_MOD == MONTY \|\| (WITH_FP && FP_RDC == MONTY) \|\| !defined(STRIP) */
318
319		#if BN_MOD == PMERS \|\| !defined(STRIP)
320
321	64	void bn_mod_pre_pmers(bn_t u, const bn_t m) {
322	64	if (bn_is_zero(m) \|\| bn_sign(m) != RLC_POS) {
323	11	RLC_THROW(ERR_NO_VALID);
324	11	return;
325	11	}
326
327	53	bn_set_2b(u, bn_bits(m));
328	53	bn_sub(u, u, m);
329	53	}
330
331	52	void bn_mod_pmers(bn_t c, const bn_t a, const bn_t m, const bn_t u) {
332	52	bn_t q, t;
333	52	int neg = 0, bits = bn_bits(m);
334
335	52	if (bn_is_zero(m) \|\| bn_sign(m) != RLC_POS) {
336	0	RLC_THROW(ERR_NO_VALID);
337	0	return;
338	0	}
339
340	52	bn_null(q);
341	52	bn_null(t);
342
343	52	RLC_TRY {
344		/* Implement algorithm 10.25 from HEHC. */
345
346	52	bn_new(q);
347	52	bn_new(t);
348
349	52	bn_copy(c, a);
350	52	if (bn_sign(c) == RLC_NEG) {
351	0	neg = 1;
352	0	bn_sub(c, m, c);
353	0	}
354
355	52	bn_rsh(q, c, bits);
356	52	bn_mod_2b(c, c, bits);
357
358	9.66k	while (bits > 0 && !bn_is_zero(q)) {
359	9.60k	if (u -> used == 1) {
360	888	bn_mul_dig(t, q, u->dp[0]);
361	8.72k	} else {
362	8.72k	bn_mul(t, q, u);
363	8.72k	}
364	9.60k	bn_rsh(q, t, bits);
365	9.60k	bn_mod_2b(t, t, bits);
366
367	9.60k	bn_add(c, c, t);
368	9.60k	}
369	7.23k	while (bits > 0 && bn_cmp_abs(c, m) != RLC_LT) {
370	7.18k	bn_sub(c, c, m);
371	7.18k	}
372
373	52	if (neg) {
374	0	bn_sub(c, m, c);
375	0	}
376	52	}
377	104	RLC_CATCH_ANY {
378	0	RLC_THROW(ERR_CAUGHT);
379	0	}
380	104	RLC_FINALLY {
381	52	bn_free(t);
382		bn_free(q);
383	52	}
384	52	}
385
386		#endif /* BN_MOD == PMERS \|\| !defined(STRIP) */