求一个最小的素数p，使得 p+2293是2的幂

hujunhua

俺用M10搜索计算了20分钟还不输出结果，中止了。谁的电脑牛，给算算看。

hujunhua

对一般的奇数n，使得2^k-n为素数（包括负素数）的k都不会太大.
较小的一个例外是127，最小的k是47，最小p=2^47-127=140737488355201.
较小而十分可观的一个例外是337，最小k=791，最小p=2^791-337= 13023465689218465379062210528752456635048356098273258125773941038601635230112562639690297267327254474107284981627799297745876565730701884922584679789708652433779604647488309684498199777171511767048759797140403519495489742260696213459304111

这两个已经很奇特了，居然还有一个小小的2293跟无解似的，不会真的无解吧。

mathe

这个不能光拼电脑，还得用些诀窍。
由于大整数n是素数概率只有$O(1/{log(n)})$
我们需要将需要提高判断算法中常系数的值
可以先使用筛选法要求结果不是小素数的倍数，也就是排除$2^n-2293$是小素数q的倍数，比如对于q小于10000而且q-1的素因子都不是太大
由此可以事先排除掉很多整数n

hujunhua

俺算337的也是一瞬间嘛，20分钟还不出结果的，那肯定已经很大了，可惜俺忘了取得k的值有多大，也不能再算了，怕把俺6G内存的机子撑破了。
恐怕俺的M10程序也不够高效。

lsr314

http://math.stackexchange.com/qu ... s-always-composite#

如果2^n-2293是素数，那么n=24k+1,并且n>300000.

hujunhua

俺眼拙了，居然把它发到小题大作里来了

mathe

由于对于一个随机大整数N,它是素数概率大概为$1/{ln(N)}$,而对于奇数n,由于大整数$2^k-n$已经排除了2的倍数，概率要增大一倍，所以是素数概率为$2/{ln(2^k-n)}$,在k比较大时约为$2/{kln(2)}$,所以$k<=K$范围内找到素数概率大概为${2ln(K)}/{ln(2)}$
其中主要问题对于小的k上面公式估算不准，最好数值计算一下。但是可以知道，增长速度为很慢。但是如果我们已经搜索过对于$k<K_0$都无解，那么再$K_0<k<K_1$范围找到解的期望大概为\(\dfrac{2\left(\ln(K_1)-\ln(K_0)\right)}{\ln(2)}\),所以感觉通常数目翻倍后找到的可能性就已经不小了。所以如果在配合筛选法，找到候选解，问题就不大了，余下就是如果判断这些候选解中有真正的解，毕竟数值不小

mathe

对于$2^k-n$形式素数的搜索，我们可以先选定一个数M,比如M=1000000
1.判断是否存在小于M的满足条件的素数，下面进考虑不存在的情况
2.对于小于M的每个奇素数q,而且q不是n的因子，解方程$2^x=n(mod q)$,可以得出$x=x_q(mod q-1)$,
   由此，我们可以排除所有形如$x=x_q(mod q-1)$的k
  这部分复杂度最多$O(M^2)$,实际上还可以用复杂算法进行加速（如Class Index?）
3. 对没有被排除的k采用欧拉判别法快速排除非素数情况
   也就是先假设$P=2^k-n$是素数，于是对于较小整数$a$,（比如可以选a=2）,必然有$a^{P-1}=1(mod P)$,或者$a^{2^k}=a^{n+1}(mod P)$
于是非常有意思，我们进需要先计算$a^n(mod P)$,然后对$a$连续关于模P平方k次
其中模P也可以加速，对于$1<=x<P^2$,我们可以写成$x=a+b*2^k=a+b*n(mod P)$,此后在此调整得到b必然很小，再使用一次就得出结果了

lsr314

到了n=300000这个地方要判断是不是素数已经很难了，2^300000数字长达9万位，如果没有排除p被小素数整除的可能性，那么下一步是判断是否满足费马小定理：$2^p\equiv2(mod p)$,这个判断起来也是很慢的。

mathe

用上面试着写了个程序（效率不是很高），在花费30000秒左右，验算到17万以内均没有解。程序还在继续运行中，当然越后面越慢。
首先容易得出n必须是12k+1 (上面链接中提到24k+1我不知道是如何得出的),但是如果再次使用筛选法，大概可以变成每一万个数余70~80个数。也就是在1/12的基础上继续筛到约1/10
后面就是利用判别式$2^{2^k} -=2^{n+1}(mod 2^k-n)$