所有 64 位参数的高效模幂运算

Question

我正在尝试提高我编写的以下模幂函数的性能。我觉得可能有某种方法可以利用它多次计算 128 位无符号整数的相同 64 位模 n 的事实，最多可达 128 次！我不介意牺牲一些可移植性并使用 128 位整数类型，并且我的目标是 x86_64。在一般情况下，还有比平方求幂更快的方法吗？

uint64_t modpowu64(uint64_t a, uint64_t e, uint64_t n) {
// Returns a^e mod n
  if (n == 0) return 0;
  if (a < 2) return a;
  unsigned __int128 res = 1;
  unsigned __int128 sq = a % n;
  while (e) {
    if (e & 1ULL) res = (res * sq) % n;
    sq = (sq*sq) % n;
    e >>= 1;
  }
  return res;
}

上面的功能有效，所以也许这不是正确的论坛。这应该放在代码审查中吗？

Answer 1

候选人的进步：

帮助编译器了解

res

和

sq

是 64 位。 这些对象不需要是128位，只有乘法需要是128位。 一个好的编译器可以看到

(unsigned __int128) res * sq

是 64bit*64bit --> 128bit，而原始代码可能看不到。

  uint64_t res = 1 % n;  // Or he like to insure a mod by 1 is 0 for `res`.
  uint64_t sq = a % n;
  while (e) {
    if (e & 1U) res = ((unsigned __int128) res * sq) % n;
    sq = ((unsigned __int128) sq * sq) % n;
    e >>= 1;
  }