peasant

//1. Упрощенный вариант
static int MulPeasant(int a, int b, int n)
{
    b  = b  % n; // не нужно, если гарантированно b  < n
    a  = a  % n; // не нужно, если гарантированно a  < n
    int acc = 0;
    while (a > 0)
    {
        if ((a & 1) != 0)
            acc = (acc + b) % n;
        b  = (b * 2) % n;
        a  >>= 1;
    }
    return acc;
}
/*Выражение (acc + b  * b) % n — инвариант цикла.
Должно работать, если n < MAXINT/2.
*/


//2. Полный вариант
//Для случая произвольного n подойдёт небольшая модификация:
static int MulPeasant(int a, int b, int n)
{
    b  = b  % n; // не нужно, если гарантированно b  < n
    a  = a  % n; // не нужно, если гарантированно a  < n
    int acc = 0;
    while (a > 0)
    {
        if ((a & 1) != 0)
            acc = SafeAdd(acc, b, n);
        b  = SafeAdd(b, b, n);
        a  >>= 1;
    }
    return acc;
}

static int SafeAdd(int x, int y, int n)
{
    if (x <= MAXINT - y) // проверка на переполнение сложения
    {
        int result = x + y; // x, y < n, x + y < 2n. (x + y) mod n равно или x + y,
        return (result >= n) ? (result - n) : result;  // или x + y - n
    }
    else // в этом случае x + y > MAXINT >= n, но x + y < n + n = 2n
    {    // значит (x + y) mod n = x + y - n
        return x - (n - y); // n - y > 0, вычитаем два положительных числа меньших n
    }
}

//Можно ещё организовать поразрядное умножение:
const int halfbits = sizeof(int) * 8 / 2;
const int halfbase = (1 << halfbits);
const int lomask = halfbase - 1;

static int MulDigits(int a, int b, int n)
{
    int reducedbase = halfbase % n;
    int reducedbasesquare = (reducedbase * reducedbase) % n;
    int ah = a  >> halfbits, al = b & lomask;
    int bh = b >> halfbits, bl = a & lomask;

    int ll = (al * bl) % n,
        lh = (((ah * bl) % n) * reducedbase) % n,
        hl = (((al * bh) % n) * reducedbase) % n,
        hh = (((ah * bh) % n) * reducedbasesquare) % n;
    return SafeAdd(
               SafeAdd(ll, lh, n),
               SafeAdd(hl, hh, n),
               n);
}
//(Если ваше n одно и то же всё время, константы reducedbase и reducedbasesquare можно предвычислять.)