10^n+1素数问题

〇〇

记录学习

gxqcn

我调用 HugeCalc 编程得到如下结论：

$N=10^r+1$ 在 $0<=r<=2^15$ 范围内，仅有 r=1 和 r=2 使 N 为素数；

考察 $N=n^(2^r)+1\quad(2<=n<1024, 0<=r<10)$ 中为素数的情况：

• 素数数目最多的是n=2时，它有5个：r=0, 1, 2, 3, 4；
• 素数数目达到4个的有：n=4, 156, 306, 430, 562, 690；
• r=9时，有n=46；
• r=8时，对应有n=278, 614, 892, 898；
• r=7时，对应有n=120, 190, 234, 506, 532, 548, 960；
• r=6时，对应有n=102, 162, 274, 300, 412, 562, 592, 728
  

gxqcn

在上述结论中，r=9 的仅有 n=46 一个数，我后来检验了其对应的 r=10,11,12,13 均非素数。

请问：让 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 r 可有上限？

悬赏：找出一个使 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 $(n,r)$ 组合，但要求 $r>=10$，将额外奖励100枚金币！
（注：第一份悬赏奖励已给 21# wayne ）

winxos

Lucas's Primality Test With Factored N-1
n-1 tests and Pepin's Test for Fermats
mathe 发表于 2009-8-28 05:30

看了第一个的内容，怎么刚好和素数循环节求法一样。
前段时间写了个求循环数的程序，做法是先将P-1分解，然后利用mathe以前告诉我的$10^n-=1 (mod p)$的性质，将因子当做n从小往大算，第一个%=1 的就是循环节位数了，发现速度还是非常的快啊。

winxos

根据第二个链接的定理2,对于$P=10^{2^k}+1$,只要找到一个数a,使得
$a^{P-1}-=1(mod P)$,
$gcd(a^{(P-1)/5}-1","P)=1$
那么P是素数.
mathe 发表于 2009-8-28 05:44

我直接用的GMP的素性测试来做的，不过数大了也非常慢。

mathe

我直接用的GMP的素性测试来做的，不过数大了也非常慢。
winxos 发表于 2009-8-28 14:15

主要是数字大了计算模幂就很慢.
不过上面这个结论最大的好处就是如果找到了一个伪素数,通常可以很快的确定是否是真正的素数.

winxos

在上述结论中，r=9 的仅有 n=46 一个数，我后来检验了其对应的 r=10,11,12,13 均非素数。

请问：让 $n^(2^r)+1\quad(n,r in ZZ)$ 为素数的 r 可有上限？

悬赏：找出一个使 $n^(2^r)+1\quad(n,r in ZZ)$ 为素 ...
gxqcn 发表于 2009-8-28 11:30

看来这个悬赏老大应该差不多算了比较大的范围吧，
我测了r=10时候，200以内无解。

fengaas

好像有一个新的素数判定算法。
一个数满足十三个方程，则它是素数。
http://www.irgoc.org/Article/ShowArticle.asp?ArticleID=85

gxqcn

那不是13个方程，而是13行伪代码。
这是网上广为流传的由三个印度数学家发现的素数确定性判定算法，其算法复杂度比先前的要低。

但针对某些特殊数字，
可以有更快的判定算法（一样是确定性判定），
比如对 Mersenne number 可以用 Lucas-Lehmer Test 快速判定。

另，恭喜LS荣获“优秀新人奖”勋章！

wayne

我调用 HugeCalc 编程得到如下结论：

$N=10^r+1$ 在 $0
gxqcn 发表于 2009-8-28 11:16

搜到了很多这样的广义费尔马素数
$70906^(2^15)+1$，$167176^(2^15)+1$,......

链接：
http://pagesperso-orange.fr/yves.gallot/primes/index.html