C和C++中的模运算在数学上并不正确,因为在执行负数的模运算时,它会返回负结果。positive modulo(int i, int n) return ( ( (i % n) + n ) % n );考虑到模数的计算成本很高,有没有更有效的方法来计算任意数的正模(我已经看到了2的幂的解决方案,但我需要一些通用的东西)?
我的问题是在JavaScript中快速计算(g^x) mod p,其中^是取幂,mod是模运算。所有输入都是非负整数,x大约有256位,p是2048位的质数,g最多可以有2048位。使用平方和乘法(通过平方求幂,)的明显想法对于2048位数字来说太慢了:它需要多达4096次乘法。
升级浏览器不是一个选项。使用另一种编程语言不是一种选择。将号码发送到web服务不是一种选择。更新:通过做一些额外的准备(即预计算几百次幂),正如下面outis的答案中提到的文章所建议的那样,可以使用最多354次