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