java实现素数检测的问题如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m -
来源:学生作业帮助网 编辑:六六作业网 时间:2024/11/26 17:09:02
java实现素数检测的问题如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m -
java实现素数检测的问题
如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:
如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m - 1次循环,而m可能是一个500位长的数,这么多次循环是不可能的,是我理解错算法了么?
如果可以转化为模乘运算,那么用BigIntegr如何实现?
java实现素数检测的问题如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m -
你要计算203^256需要计算255次乘法吗
你不可以先算出a=203^128,再计算a^2不就计算出203^256了吗,一共只需要8次乘法即可
比如计算203^290,可以算出a1=203^256,a2=203^32,a3=203^2,最后a1*a2*a3即为最终结果
假设数的位数为n(500),高精度乘除法运算简单写复杂度为n^2,那么乘方的复杂度就是n^3
实际上500位10进制数只需要50个int即可,一次乘除法2500,二进制位大概2000,再乘以常数总运算量在千万左右,个人电脑完全可以0.01-0.1s内完成
专门优化过的高精度运算更可以提速10-100倍,所以判断是否是素数很容易,现在最大已判断出的素数都好多亿位了