Le Blog De La L'Ernestas && Vampyro fermerio Ernesto blogis

My fix is connected with fact that is not always necessary to perform a modulo operation.

For example: we have number a = 3, b = 4, modulus = 10. So, the operation would look something like that: (a + b) mod modulus = (3 + 4) mod 10 = 7 mod 10. Because 7 is lower than 10, we do not need the modulus operation.

The structure:

typedef size_t digit_t;

typedef struct {
int neg;         /* if TRUE, then negative number */
int sig_digits;  /* amount of significant (non-zero) digits */
int all_digits;  /* amount of overall digits in array */
digit_t *digits; /* pointer to first limb */
} bignum_t;

The code would look something like that:

/* (x + y) mod base */
void mpa_mod_add(bignum_t *res, const bignum_t *a, const bignum_t *b, const bignum_t *base) {
int i = 0, c = 0;
for (i = 0; i < a->all_digits; i++) {
res->digits[i] = a->digits[i] + b->digits[i];
if (res->digits[i] >= base->digits[i])
res->digits[i] = res->digits[i] – base->digits[i];
}
res->digits[res->all_digits] = c;
}

I was browsing (ok, lets be honest – Goooogling) the web in order to find some Multiple-Precision Modular Arithmetics algorithms. Our lecturer recomended a very good book – “Handbook of Applied Cryptography“. So, I used this book in order to code my algorithms (modular addition, subraction and multiplication)

So, here is my modular addition algorithm implementation in the C programming language.

// Name: int MultiplePrecisionAddition()
// Input:        x        – first integer, size n
//                y        – second integer, size n
//                n        – number of digits in x, y, w
//                base    – modulus
// Output:        w        – result, size n, w[n - 1]…w[0]
// Description: Calculates (x + y mod base)
int MultiplePrecisionAddition(int x[], int y[], int w[], int n, int base) {
int i = 0, c = 0, result = 0, temp = 0;
for (i = 0; i < n – 1; ++i) {
result = x[i] + y[i] + c;
w[i] = result % base;
result < base ?    c = 0 : c = 1;
}
w[n - 1] = c;

// Converts from w[0]w[1]…w[n - 1] to w[n - 1]…w[0]
for (i = 0; i < n / 2; ++i) {
temp = w[i];
w[i] = w[n - 1 - i];
w[n - 1 - i] = temp;
}
return 0;
}

Any suggestions how to improve my code?