Протокол Диффи-Хеллмана не работает при некоторых значениях

Во-первых, в криптографических алгоритмах нужны точные целочисленные вычисления. Вы же используете приближенные вычисления с плавающей точкой. Ни о каком точном вычислении 5116 в вашем варианте речи идти не будет - это слишком большое число.

Во-вторых, ваша последовательность действий описывает процесс формирования общего ключа после выбора секретных ключей a и b. В протоколе Диффи-Хеллмана секретные ключи a и b выбираются из мультипликативной группы по модулю p, то есть в вашем примере для p = 23 это должны быть значения в диапазоне [1, 22]. При чем здесь ваше 116, откуда вы его взяли и чего от него ожидали - не ясно.

(Как правильно заметил @Zergatul в комментариях, при p = 23 протокол будет правильно работать и для a = 116. Но нет никакого смысла в том, чтобы выбирать число за пределами диапазона [1, 22]. В вашем случае это лишь привело к потере точности.)

Никто так не считает остаток от деления после возведения в степень. Самая простая оптимизация выглядит так:

int modpow(int a, int b, int m) // a^b % m
{
    int result = 1;
    // 31 - для упрощения кода, на самом деле нужно брать длину числа в битах
    for (int i = 31; i >= 0; i--)
    {
        result = result * result % m;
        if (b & (1 << i))
            result = result * a % m;
    }
    return result;
}

В реальных библиотеках для длинных чисел и криптографии дополнительно используют алгоритм Монтгомери.