怎么样求N以下所有素数

liangbch

说一说我的对加密领域中的大数运算优化的观点吧。
  GMP找出1个2048bit以内的数需要1秒左右的时间，这很出乎我的意料，我原以为这种计算的时间花费是毫秒级的。
  对2048bit以内的大数，FFT算法完全派不上用场。Karatsuba 和Toom-3 算法应该够了，从算法上能够改进的很少，性能提升主要靠优化了，Intel新款CPU "Core 2 Wolfdale 45nm"改进了PSHUFD指令的性能，使用SSE2指令优化乘法的效果应该很好。关于SIMD优化大数乘法的讨论请参照 http://bbs.emath.ac.cn/viewthread.php?tid=216

fly

32# liangbch

大牛，因为我对硬件和汇编完全不熟，所以不是很懂你的意思，你是不是说还有可能找到1毫秒的算法或者大数库？还是说在硬件固定的条件下，只有这个1秒的算法了？

如果只找1个随机素数的算法时间不能改进了，那么能不能在找2^20个随机素数的时间上优化和改进呢。哎呀，这些问题会经常让我头痛

liangbch

大牛，因为我对硬件和汇编完全不熟，所以不是很懂你的意思，你是不是说还有可能找到1毫秒的算法或者大数库？还是说在硬件固定的条件下，只有这个1秒的算法了？

SS2指令优化大数乘法，性能或许提升到200%或更多，但没有办法做到从1s到1ms.
再一个改进就是，看看GMP的Rabin-Miller素数检测的代码能否优化。Rabin-Miller的核心是模幂算法，如果使用更好的模幂算法，速度可再次提高。

如果只找1个随机素数的算法时间不能改进了，那么能不能在找2^20个随机素数的时间上优化和改进呢。哎呀，这些问题会经常让我头痛

  求100万个素数的运行时间等同于求1个素数运行时间的100万倍，复杂度已经是线性的了，我想不出更好的算法。

mathe

2^20个大素数的任务还是比较难的。至少，我们需要对每个候选素数做一次Miller-Rabin素数测试吧。
即使1秒钟能够判断100个，需要的时间3小时左右。而如果是liangbch估算的一个素数需要1秒钟判断，那么时间已经很难让人接受了