c++ - 快速功率算法实现

Question

我需要计算二次余数。质数 p 是 3 mod 4，是一个非常大的数，大约 1e38 (constexpr)。我只找到了 Lagrange x = +- a^((p + 1)/4) mod p 的公式。

我需要计算大数的幂 (a ^ 1e38)。我试图使用 boost::multiprecision::cpp_int，但似乎没有任何意义。对于这样的计算或替代算法，可能有人知道一个很好的实现。

Answer 1

通常，当顶部小于底部时，通过二次互易调用​​来翻转 Jacobi 符号(或 Kronecker 符号)，通过欧几里德算法式计算来测试某物是否为二次余数。

---

此外，您几乎不应该计算指数然后减少模p:您的求幂算法(例如平方和乘法)应该减少模p 在每一步左右的计算之后。关键词:“模幂”。