神马作文网java实现素数检测的问题
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/09/29 15:29:24
java实现素数检测的问题
如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题：
如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m - 1次循环,而m可能是一个500位长的数,这么多次循环是不可能的,是我理解错算法了么?
如果可以转化为模乘运算,那么用BigIntegr如何实现?
如上图,其中模幂运算那一步,是计算x = a ^ m (mod n),有两个问题：
如果使用Montgomery算法,把模幂运算转化为模乘运算,来获得相同的结果x,那么根据算法的步骤,将要进行m - 1次循环,而m可能是一个500位长的数,这么多次循环是不可能的,是我理解错算法了么?
如果可以转化为模乘运算,那么用BigIntegr如何实现?
你要计算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倍,所以判断是否是素数很容易,现在最大已判断出的素数都好多亿位了
再问： 你说的是计算a^m的方式，平方运算次数为2log(m)，但重点不是这
a和m各自可能是500位的大数，Montgomery算法就是为了避免直接计算位数如此大的结果，因为500位数的500位次幂，占用的内存是非常大的，而且结果只是一个中间数（马上就要mod n），非常浪费，对于业务上来说也是不可接受的
其实问题就是Montgomery算法是否在这个运算中需要循环m次
再答： 算了，算我对牛弹琴，对数论一点不了解还学mr
上面所有运算都是基于某模的剩余系
不效率但不增加复杂度的实现是每步后取模（如果这个还要问为什么那么只能说你选错了行业）
并不是只有现实中的乘法才叫乘法，现实中的乘方才叫乘方
多看看群域环相关的数论吧，现在大数质因数分解理论都是基于这些方面的概率算法
再问： 我问的就是如何把模幂分解为模乘分步取模，你先回答一堆如何计算大数的高次幂现在又来说对牛弹琴，不知道是谁比较搞笑，还答非所问
a^m求出来一旦有并发操作业务能承受么？每个数上十M，现在运算速度是快，可是你完全没考虑内存，Montgomery约分就是为了解决内存的问题
没做过什么项目就不要来高谈阔论数学理论
再答： 数学理论？拜托，哥不是搞数学理论的。不过这个是小学数学而已
你不可以先算出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倍,所以判断是否是素数很容易,现在最大已判断出的素数都好多亿位了
再问： 你说的是计算a^m的方式，平方运算次数为2log(m)，但重点不是这
a和m各自可能是500位的大数，Montgomery算法就是为了避免直接计算位数如此大的结果，因为500位数的500位次幂，占用的内存是非常大的，而且结果只是一个中间数（马上就要mod n），非常浪费，对于业务上来说也是不可接受的
其实问题就是Montgomery算法是否在这个运算中需要循环m次
再答： 算了，算我对牛弹琴，对数论一点不了解还学mr
上面所有运算都是基于某模的剩余系
不效率但不增加复杂度的实现是每步后取模（如果这个还要问为什么那么只能说你选错了行业）
并不是只有现实中的乘法才叫乘法，现实中的乘方才叫乘方
多看看群域环相关的数论吧，现在大数质因数分解理论都是基于这些方面的概率算法
再问： 我问的就是如何把模幂分解为模乘分步取模，你先回答一堆如何计算大数的高次幂现在又来说对牛弹琴，不知道是谁比较搞笑，还答非所问
a^m求出来一旦有并发操作业务能承受么？每个数上十M，现在运算速度是快，可是你完全没考虑内存，Montgomery约分就是为了解决内存的问题
没做过什么项目就不要来高谈阔论数学理论
再答： 数学理论？拜托，哥不是搞数学理论的。不过这个是小学数学而已