Получить по модулю из двух целочисленных массивов 4x64 бит

Вот простой (и довольно эффективный) алгоритм, который вычисляет a % b, используя только вычитание, умножение на 2, деление на 2 и сравнение (все это легко реализовать для вашего uint256).

uint256 modulo(uint256 a, uint256 b) {
  int i = 0;
  while (b <= a) {
    b = b * 2; // watch out for overflow!
    i++;
  }
  while (i--) {
    b = b / 2;
    if (b <= a) {
      a = a - b;
    }
  }
  return a;
}

Вот пример:

start: a = 40, b = 7
i = 1, a = 40, b = 14
i = 2, a = 40, b = 28
i = 3, a = 40, b = 56

i = 3, b = 28, a = 40 - 28 = 12
i = 2, b = 14, a = 12 (b > a so nothing happens)
i = 1, b = 7, a = 12 - 7 = 5
i = 0, so we stop and return a = 5

РЕДАКТИРОВАТЬ: Почему это работает? Наивный способ вычисления остатка по модулю, если следующее:

int modulo(int a, int b) {
  while (a >= b) {
    a -= b;
  }
  return a;
}

Предлагаемое решение использует ту же идею, но более эффективным способом. Мы знаем, что в итоге мы вычтем b из a ровно k раз. Мы не знаем значение k. k может быть представлено в двоичном виде как 2^0 * k_0 + 2^1 * k_1 + 2^2 * k_2 + .... Алгоритм исходит из самых больших значений 2^i и пытается вычесть 2^i * b. Благодаря этому мы достигаем логарифмической временной сложности вместо линейной.

Отказ от ответственности: я бы не стал использовать эту реализацию как настоящую криптографическую реализацию, поскольку она подвержена атакам по сторонним каналам (разное время выполнения в зависимости от ввода).