Быстрое умножение 64-битного целого числа по модулю с использованием 64-битного целого числа без переполнения

Question

Я хочу быстрое умножение 64-битного целого числа по модулю с использованием 64-битного целого числа без переполнения. Я знаю два способа вычисления умножения 64-битного целого числа по модулю.

1. Использовать BigInteger

2. Рассчитать как

long mul(long a, long b){
  if(a==1)return b;
  else if(a%2==0)return 2*mul(a/2,b)%mod;
  else return (mul(a-1,b)+b)%mod;
}

Однако оба способа медленнее по сравнению с C ++ __int128_t.

Моя идея состоит в том, чтобы разделить a и b на 32-разрядное целое число и вычислить их. Например, умножение равно

(a_0 + a_1 2 ^ {32}) (b_0 + b_1 2 ^ {32}) = a_0 b_0 + (a_0 b_1 + a_1 b_0) 2 ^ {32} + a_1 b_1 2 ^ {64}

. Но я не знаю, как быстро по модулю.

Если у вас есть хорошая идея, пожалуйста, помогите мне.