素数与RSA算法的疑问

Question

我有几点思考，个人能力有限想不明白，望有人指点下：
1、找素数的时候，我在想：不能被比他小的素数整除的数就是素数。请各位指正该推理成立吗？1亿以内的素数我都写程序论证过了，没有问题。
2、都说RSA很难破译，是真的吗？人类目前找到的素数是个有限集合，公钥里面包含了两个大素数的乘积，如果进行穷举，是不是就可以破解了？

Answer 1

1.当然是正确的
不能被素数整除，必然也不能被合数整除，因为合数是素数相乘得到的呀，这还用写程序论证？
问题是在求素数的过程中如果还要顺带求比它小的素数，反而复杂化了，所以写程序一般都不考虑是素数还是合数，直接遍历。
如果你不是要验证一个数是质数还是合数，而是要求N以内的所有质数，那么筛法才是最效率的。
2.穷举当然是可以破解的，问题是需要花多长时间呢？如果你花600年能破解，跟破解不了有多大区别呢
实际上，算法也是在不断迭代的，最早RSA算法只有128位，现在512位也不止了吧，好像已经有2048位的RSA了
所以实际应用中你不需要600年破解，只要3年不被破解基本上就等于永远不会被破解了，因为3年之后算法提升，破解难度又变大了