人类是怎么知道费马数F118的因子的?

mathematica

1527888802614951*2^120 + 1是 F118=2^(2^118)+1的因子

F118的十进制数有100034374451893909912121200439553939多位,约等于10^35位大整数,
而椭圆曲线算法需要模这个大整数,因此是不可能利用椭圆曲线来分解这个大整数的,

1527888802614951有16位,
如果只是用同余试除法的话,
假设一秒钟计算10^5次,那么需要
10^15/(365*24*60*60)/10^5=317.1年
这显然是不可能的,但是现在F118的因子给出来了,
那么问题来了,人类怎么知道这个因子的呢?


资料来源
http://www.prothsearch.com/fermat.html

lsr314

很多电脑同时计算就可以缩短这个时间了

mathematica

lsr314 发表于 2019-4-3 14:37
很多电脑同时计算就可以缩短这个时间了

k*2^120 + 1首先必须是素数,
{7, 162, 231, 277, 315, 331, 336, 352, 372, 501, 541, 546, 567, 640, \
651, 723, 738, 787, 808, 861, 913, 966, 1005, 1015, 1018, 1113, 1173, \
1243, 1321, 1408, 1453, 1492, 1530, 1548, 1705, 1843, 1887, 1993, \
2116, 2128, 2161, 2242, 2376, 2592, 2601, 2608, 2692, 2808, 2835, \
2871, 2878, 2886, 2968, 2977, 3018, 3088, 3153, 3208, 3271, 3355, \
3421, 3588, 3612, 3627, 3768, 3775, 3796, 3832, 3883, 3957, 4012, \
4258, 4275, 4281, 4390, 4398, 4405, 4582, 4590, 4593, 4701, 4716, \
4768, 4803, 4852, 4890, 4891, 4918, 4951, 4956, 5013, 5050, 5097, \
5128, 5163, 5178, 5188, 5250, 5376, 5437, 5461, 5463, 5481, 5482, \
5497, 5533, 5556, 5566, 5590, 5622, 5646, 5682, 5707, 5727, 5751, \
5988, 6028, 6037, 6046, 6055, 6193, 6217, 6232, 6240, 6262, 6276, \
6283, 6336, 6337, 6405, 6417, 6562, 6570, 6583, 6675, 6711, 6787, \
6793, 6807, 6828, 6847, 6903, 7012, 7158, 7177, 7210, 7345, 7366, \
7378, 7432, 7465, 7527, 7570, 7641, 7672, 7876, 7987, 8110, 8145, \
8316, 8395, 8398, 8418, 8421, 8452, 8461, 8496, 8647, 8712, 8778, \
8823, 8872, 8886, 8976, 9000, 9117, 9235, 9291, 9357, 9412, 9433, \
9565, 9696, 9763, 9766, 9870, 9916, 9936, 9945, 9952}
我只知道这么多,不知道你有没有更好的办法!

mathematica

lsr314 发表于 2019-4-3 14:37
很多电脑同时计算就可以缩短这个时间了

我感觉不像

.·.·.

有可能是GPU试除
GPU比CPU快很多
一群人一起拿CPU试除，应该会出结果的
有专门的GPU试除程序（在mersenneforum.org里面大概能找到）

mathematica

.·.·. 发表于 2020-11-3 16:32
有可能是GPU试除
GPU比CPU快很多
一群人一起拿CPU试除，应该会出结果的

2030912570882086247957711831528946513898296129355777
这个素数有52位，我觉得即使分算也很多

mathematica

.·.·. 发表于 2020-11-3 16:32
有可能是GPU试除
GPU比CPU快很多
一群人一起拿CPU试除，应该会出结果的

1. Clear["Global`*"];
   
2. n=0;
   
3. Do[a=k*2^120+1;If[PrimeQ[a],n=n+1],{k,10^5,2*10^5}]
   
4. Print[10^5/n*1.0]
   

复制代码

48.0077
平均48个当中产生一个质数

.·.·.

mathematica 发表于 2020-11-4 10:36
48.0077
平均48个当中产生一个质数

别这么搞
这么搞太慢效率太低
第一步是初筛，只需要排除2,3,5,7,11,13这些数字的倍数，就可以保证在30030个数字里只有5760个待选数字
这一步可以节省一点伪素数算法的耗时

1. ClearSystemCache[]; Timing[n = 0;
   
2. t = Pick[Table[i, {i, 1, 30030}],
   
3.    Table[! (Divisible[i 2^120 + 1, 2] || Divisible[i 2^120 + 1, 3] ||
   
4.        Divisible[i 2^120 + 1, 5] || Divisible[i 2^120 + 1, 7] ||
   
5.        Divisible[i 2^120 + 1, 11] || Divisible[i 2^120 + 1, 13]), {i,
   
6.      1, 30030}]]; Do[n += \!\(
   
7. \*UnderoverscriptBox[\(\[Sum]\), \(i\), \(t\)]\(PrimeQ[\((i +
   
8.          k\ 30030)\)\
   
9. \*SuperscriptBox[\(2\), \(120\)] + 1]\)\), {k, 1, 10}]; n]

复制代码

1. Clear["Global`*"];
   
2. n = 0;
   
3. Timing[Do[a = k*2^120 + 1;
   
4.   If[PrimeQ[a], n = n + 1], {k, 30030, 30030*11}]]
   
5. Print[10^5/n*1.0]

复制代码

1. In[71]:= ClearSystemCache[]; Timing[n = 0;
   
2. t = Pick[Table[i, {i, 1, 30030}],
   
3.    Table[! (Divisible[i 2^120 + 1, 2] || Divisible[i 2^120 + 1, 3] ||
   
4.        Divisible[i 2^120 + 1, 5] || Divisible[i 2^120 + 1, 7] ||
   
5.        Divisible[i 2^120 + 1, 11] || Divisible[i 2^120 + 1, 13]), {i,
   
6.      1, 30030}]]; Do[n += \!\(
   
7. \*UnderoverscriptBox[\(\[Sum]\), \(i\), \(t\)]\(PrimeQ[\((i +
   
8.          k\ 30030)\)\
   
9. \*SuperscriptBox[\(2\), \(120\)] + 1]\)\), {k, 0, 99}]; n]
   
10. 
    
11. Out[71]= {30.1495, 1089772 False + 62228 True}
    
12. 
    
13. In[65]:= N[1/(6856/30030/11)]
    
14. 
    
15. Out[65]= 48.1812
    
16. 
    
17. In[72]:= Clear["Global`*"];
    
18. n = 0;
    
19. Timing[Do[a = k*2^120 + 1;
    
20.   If[PrimeQ[a], n = n + 1], {k, 0, 30030*100}]]
    
21. n
    
22. 
    
23. Out[74]= {36.0193, Null}
    
24. 
    
25. Out[75]= 62228

复制代码

.·.·.

mathematica 发表于 2020-11-4 10:36
48.0077
平均48个当中产生一个质数

忽然想到一点
有没有可能是p-1？

mathematica

.·.·. 发表于 2020-11-4 13:18
忽然想到一点
有没有可能是p-1？

p-1的质因数分解是这样
{{2,120},{3,1},{7,2},{19,1},{283,1},{1933011229,1}}
且需要模合数，你觉得你模得起吗？