郭有没有兴趣做出一个确定性的素性检测函数

qianyb

好多都错了,考虑不周啊

gxqcn

对于搜索连续长度为10以上的素数，我们只需要搜索形式如2*3*5*11*k-1的素数。
而如果搜索长度为12以上的，只需要搜索形式如2*3*5*11*13*k-1的素数
mathe 发表于 2010-7-8 15:29

Why？

无心人

是必需形式么？
是的话，我修改程序去

mathe

是必须形式。

无心人

那8,9,11,13都要什么形式？

mathe

由于
$p_{n+1}=2p_n+1$
我们可以有
$p_{n+1}-p_n=2(p_n-p_{n-1})=...=2^n(p_1-p_0)$
于是$p_n=(2^n-1)(p_1-p_0)+p_0=(2^n-1)(p_0+1)+p_0=2^n(p_0+1)-1$
如果2是素数P的原根，那么我们知道，上面序列长度最大P-2,(除非第一个数据是P),这个是因为如果长度达到P-1
那么$2^0(p_0+1),2^1(p_0+1),...,2^{P-2}(p_0+1)$可以构成P的一个完系，其中必然有一个为1，所以对应的$p_i$是P的倍数。
由于2是素数3,5,11,13的原根，我们可以有前面的结论

mathe

而再后面几个以2为原根的素数为19，29，37.
当然，我们也可以用素数7在此过滤，比如我们计算可知这些素数模7的余数必须是{2,4,5,6}之一，不过这个过滤效果就要差很多了，使用起来没有那么方便

无心人

你的结论对计算最小长度为8的可以么？

mathe

那只可以用2*3*5*k-1（当然可以添加对关于模7和11的一些特殊处理，但是效果没有那么好了，实际11比7还有效一些）

mathe

Pari/Gp通过冗长的计算找出一个10个素数的链了:
26089808579
52179617159
104359234319
208718468639
417436937279
834873874559
1669747749119
3339495498239
6678990996479
13357981992959