1/* $NetBSD: bn_mp_montgomery_reduce.c,v 1.2 2017/01/28 21:31:47 christos Exp $ */ 2 3#include <tommath.h> 4#ifdef BN_MP_MONTGOMERY_REDUCE_C 5/* LibTomMath, multiple-precision integer library -- Tom St Denis 6 * 7 * LibTomMath is a library that provides multiple-precision 8 * integer arithmetic as well as number theoretic functionality. 9 * 10 * The library was designed directly after the MPI library by 11 * Michael Fromberger but has been written from scratch with 12 * additional optimizations in place. 13 * 14 * The library is free for all purposes without any express 15 * guarantee it works. 16 * 17 * Tom St Denis, tomstdenis@gmail.com, http://libtom.org 18 */ 19 20/* computes xR**-1 == x (mod N) via Montgomery Reduction */ 21int 22mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho) 23{ 24 int ix, res, digs; 25 mp_digit mu; 26 27 /* can the fast reduction [comba] method be used? 28 * 29 * Note that unlike in mul you're safely allowed *less* 30 * than the available columns [255 per default] since carries 31 * are fixed up in the inner loop. 32 */ 33 digs = n->used * 2 + 1; 34 if ((digs < MP_WARRAY) && 35 n->used < 36 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 37 return fast_mp_montgomery_reduce (x, n, rho); 38 } 39 40 /* grow the input as required */ 41 if (x->alloc < digs) { 42 if ((res = mp_grow (x, digs)) != MP_OKAY) { 43 return res; 44 } 45 } 46 x->used = digs; 47 48 for (ix = 0; ix < n->used; ix++) { 49 /* mu = ai * rho mod b 50 * 51 * The value of rho must be precalculated via 52 * montgomery_setup() such that 53 * it equals -1/n0 mod b this allows the 54 * following inner loop to reduce the 55 * input one digit at a time 56 */ 57 mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK); 58 59 /* a = a + mu * m * b**i */ 60 { 61 register int iy; 62 register mp_digit *tmpn, *tmpx, u; 63 register mp_word r; 64 65 /* alias for digits of the modulus */ 66 tmpn = n->dp; 67 68 /* alias for the digits of x [the input] */ 69 tmpx = x->dp + ix; 70 71 /* set the carry to zero */ 72 u = 0; 73 74 /* Multiply and add in place */ 75 for (iy = 0; iy < n->used; iy++) { 76 /* compute product and sum */ 77 r = ((mp_word)mu) * ((mp_word)*tmpn++) + 78 ((mp_word) u) + ((mp_word) * tmpx); 79 80 /* get carry */ 81 u = (mp_digit)(r >> ((mp_word) DIGIT_BIT)); 82 83 /* fix digit */ 84 *tmpx++ = (mp_digit)(r & ((mp_word) MP_MASK)); 85 } 86 /* At this point the ix'th digit of x should be zero */ 87 88 89 /* propagate carries upwards as required*/ 90 while (u) { 91 *tmpx += u; 92 u = *tmpx >> DIGIT_BIT; 93 *tmpx++ &= MP_MASK; 94 } 95 } 96 } 97 98 /* at this point the n.used'th least 99 * significant digits of x are all zero 100 * which means we can shift x to the 101 * right by n.used digits and the 102 * residue is unchanged. 103 */ 104 105 /* x = x/b**n.used */ 106 mp_clamp(x); 107 mp_rshd (x, n->used); 108 109 /* if x >= n then x = x - n */ 110 if (mp_cmp_mag (x, n) != MP_LT) { 111 return s_mp_sub (x, n, x); 112 } 113 114 return MP_OKAY; 115} 116#endif 117 118/* Source: /cvs/libtom/libtommath/bn_mp_montgomery_reduce.c,v */ 119/* Revision: 1.4 */ 120/* Date: 2006/12/28 01:25:13 */ 121