Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

89 lines (77 sloc) 2.306 kb
/* LibTomMath, multiple-precision integer library -- Tom St Denis
*
* LibTomMath is a library that provides multiple-precision
* integer arithmetic as well as number theoretic functionality.
*
* The library was designed directly after the MPI library by
* Michael Fromberger but has been written from scratch with
* additional optimizations in place.
*
* The library is free for all purposes without any express
* guarantee it works.
*
* Tom St Denis, tomstdenis@iahu.ca, http://math.libtomcrypt.org
*/
#include <tommath.h>
/* computes xR**-1 == x (mod N) via Montgomery Reduction */
int
mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
{
int ix, res, digs;
mp_digit mu;
/* can the fast reduction [comba] method be used?
*
* Note that unlike in mp_mul you're safely allowed *less*
* than the available columns [255 per default] since carries
* are fixed up in the inner loop.
*/
digs = n->used * 2 + 1;
if ((digs < MP_WARRAY) &&
n->used <
(1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
return fast_mp_montgomery_reduce (x, n, rho);
}
/* grow the input as required */
if (x->alloc < digs) {
if ((res = mp_grow (x, digs)) != MP_OKAY) {
return res;
}
}
x->used = digs;
for (ix = 0; ix < n->used; ix++) {
/* mu = ai * m' mod b */
mu = ((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK;
/* a = a + mu * m * b**i */
{
register int iy;
register mp_digit *tmpn, *tmpx, u;
register mp_word r;
/* aliases */
tmpn = n->dp;
tmpx = x->dp + ix;
/* set the carry to zero */
u = 0;
/* Multiply and add in place */
for (iy = 0; iy < n->used; iy++) {
r = ((mp_word)mu) * ((mp_word)*tmpn++) +
((mp_word) u) + ((mp_word) * tmpx);
u = (mp_digit)(r >> ((mp_word) DIGIT_BIT));
*tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK));
}
/* propagate carries */
while (u) {
*tmpx += u;
u = *tmpx >> DIGIT_BIT;
*tmpx++ &= MP_MASK;
}
}
}
/* x = x/b**n.used */
mp_clamp(x);
mp_rshd (x, n->used);
/* if A >= m then A = A - m */
if (mp_cmp_mag (x, n) != MP_LT) {
return s_mp_sub (x, n, x);
}
return MP_OKAY;
}
Jump to Line
Something went wrong with that request. Please try again.