1/* $NetBSD$ */ 2 3#include <tommath.h> 4#ifdef BN_MP_REDUCE_2K_L_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/* reduces a modulo n where n is of the form 2**p - d 21 This differs from reduce_2k since "d" can be larger 22 than a single digit. 23*/ 24int mp_reduce_2k_l(mp_int *a, mp_int *n, mp_int *d) 25{ 26 mp_int q; 27 int p, res; 28 29 if ((res = mp_init(&q)) != MP_OKAY) { 30 return res; 31 } 32 33 p = mp_count_bits(n); 34top: 35 /* q = a/2**p, a = a mod 2**p */ 36 if ((res = mp_div_2d(a, p, &q, a)) != MP_OKAY) { 37 goto ERR; 38 } 39 40 /* q = q * d */ 41 if ((res = mp_mul(&q, d, &q)) != MP_OKAY) { 42 goto ERR; 43 } 44 45 /* a = a + q */ 46 if ((res = s_mp_add(a, &q, a)) != MP_OKAY) { 47 goto ERR; 48 } 49 50 if (mp_cmp_mag(a, n) != MP_LT) { 51 s_mp_sub(a, n, a); 52 goto top; 53 } 54 55ERR: 56 mp_clear(&q); 57 return res; 58} 59 60#endif 61 62/* Source: /cvs/libtom/libtommath/bn_mp_reduce_2k_l.c,v */ 63/* Revision: 1.4 */ 64/* Date: 2006/12/28 01:25:13 */ 65