java实现素数检测的问题如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m -
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/21 20:20:23
![java实现素数检测的问题如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题:如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m -](/uploads/image/z/15028916-68-6.jpg?t=java%E5%AE%9E%E7%8E%B0%E7%B4%A0%E6%95%B0%E6%A3%80%E6%B5%8B%E7%9A%84%E9%97%AE%E9%A2%98%E5%A6%82%E4%B8%8A%E5%9B%BE%2C%E5%85%B6%E4%B8%AD%E6%A8%A1%E5%B9%82%E8%BF%90%E7%AE%97%E9%82%A3%E4%B8%80%E6%AD%A5%2C%E6%98%AF%E8%AE%A1%E7%AE%97x+%3D+a+%5E+m+%28mod+n%29%2C%E6%9C%89%E4%B8%A4%E4%B8%AA%E9%97%AE%E9%A2%98%EF%BC%9A%E5%A6%82%E6%9E%9C%E4%BD%BF%E7%94%A8Montgomery%E7%AE%97%E6%B3%95%2C%E6%8A%8A%E6%A8%A1%E5%B9%82%E8%BF%90%E7%AE%97%E8%BD%AC%E5%8C%96%E4%B8%BA%E6%A8%A1%E4%B9%98%E8%BF%90%E7%AE%97%2C%E6%9D%A5%E8%8E%B7%E5%BE%97%E7%9B%B8%E5%90%8C%E7%9A%84%E7%BB%93%E6%9E%9Cx%2C%E9%82%A3%E4%B9%88%E6%A0%B9%E6%8D%AE%E7%AE%97%E6%B3%95%E7%9A%84%E6%AD%A5%E9%AA%A4%2C%E5%B0%86%E8%A6%81%E8%BF%9B%E8%A1%8Cm+-)
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倍,所以判断是否是素数很容易,现在最大已判断出的素数都好多亿位了