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

70 lines (59 sloc) 1.88 kb
/* LibTomMath, multiple-precision integer library -- Tom St Denis
*
* LibTomMath is library that provides for multiple-precision
* integer arithmetic as well as number theoretic functionality.
*
* The library is 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://libtommath.iahu.ca
*/
#include <tommath.h>
/* multiplies |a| * |b| and only computes upto digs digits of result
* HAC pp. 595, Algorithm 14.12 Modified so you can control how many digits of
* output are created.
*/
int
s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
{
mp_int t;
int res, pa, pb, ix, iy;
mp_digit u;
mp_word r;
mp_digit tmpx, *tmpt, *tmpy;
if ((res = mp_init_size (&t, digs)) != MP_OKAY) {
return res;
}
t.used = digs;
/* compute the digits of the product directly */
pa = a->used;
for (ix = 0; ix < pa; ix++) {
/* set the carry to zero */
u = 0;
/* limit ourselves to making digs digits of output */
pb = MIN (b->used, digs - ix);
/* setup some aliases */
tmpx = a->dp[ix];
tmpt = &(t.dp[ix]);
tmpy = b->dp;
/* compute the columns of the output and propagate the carry */
for (iy = 0; iy < pb; iy++) {
/* compute the column as a mp_word */
r = ((mp_word) * tmpt) + ((mp_word) tmpx) * ((mp_word) * tmpy++) + ((mp_word) u);
/* the new column is the lower part of the result */
*tmpt++ = (mp_digit) (r & ((mp_word) MP_MASK));
/* get the carry word from the result */
u = (mp_digit) (r >> ((mp_word) DIGIT_BIT));
}
if (ix + iy < digs)
*tmpt = u;
}
mp_clamp (&t);
mp_exch (&t, c);
mp_clear (&t);
return MP_OKAY;
}
Jump to Line
Something went wrong with that request. Please try again.