能通过2，3，5，7的检验的合数

无心人

看 卡米切尔数 的那个问题有人重新关注了
出个更困难的问题
<<<<<<<<<<<<<<<<****>>>>>>>>>>>>>>
| 素性检验需要以若干素数为底做米勒-罗宾测试
| 2，3，5，7是经常使用的素数底
|                                                                                      
| 现在考虑下面的问题                        
| 能否以比较快的速度求出                    
| 10^32内的能同时通过2，3，5，7测试的合数
-*-@@-*-@@-*-@@-%%%-@@-*-@@-*-@@-*-

仙剑魔

是这个意思吗? a^1 mod 2=1 a^2 mod 3=1 a^4 mod 5=1 a^6 mod 7=1 a<10^32

liangbch

$10^32=10^20 KG$, 假如一块1000G的硬盘占用0.2升，那么这些硬盘占用的空间恐怕超过5亿立方公里，你有那么多硬盘来存储结果吗？

无心人

我也觉得我说的范围有点大 但没有你说的那么恐怖吧 据我知道10^16内满足这个条件的不会很多 是以10^8做单位的 ============================= 所以这个题目改成10^16内的数字

无心人

呵呵 不是通过麦森测试 那个太多了 谢谢media2005提供的数据 我想得到具体的求解方法

medie2005

呵呵，还漏掉了一个46,856,248,255,981。 在http://www.bell-labs.com/user/bleichen/diss/thesis.html中，可以得到一个10^16以内，通过2,3为底的米勒－罗宾测试的合数表． 我们只需要对表中的每个数再判断是否能通过以5,7 为底的米勒－罗宾测试就ok了。

无心人

THX

liangbch

抱歉，我理解错题意了，我以为是可以被2，3，5，7之一整除呢。实际上应该是同时不可被2，3，5，7整除。这样的话，范围就小多了。

无心人

我想知道那些简单的素性测试程序的参数时如何挑选出来的

medie2005

see this: http://math.crg4.com/primes.html
在“My Efficient Sets of Bases”一段中，提到了：
“For these calculations, I used lists of pseudoprimes from Richard Pinch (2-pseudoprimes up to 10^13), William Galway (2-pseudoprimes up to 10^15), and Daniel Bleichenbacher (2- and 3-strong pseudoprimes up to 10^16). My actual calculations were carried out in C#, C++, and PARI/GP.”
因此，还是用类似我上面的方法来做的。
如果有兴趣，也可以自己改进五元组测试基。