找回密码
 欢迎注册
查看: 24741|回复: 14

[原创] 人类是怎么知道费马数F118的因子的?

[复制链接]
发表于 2019-4-3 11:51:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
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



毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-11-4 13:18:16 | 显示全部楼层
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. Out[71]= {30.1495, 1089772 False + 62228 True}

  11. In[65]:= N[1/(6856/30030/11)]

  12. Out[65]= 48.1812

  13. In[72]:= Clear["Global`*"];
  14. n = 0;
  15. Timing[Do[a = k*2^120 + 1;
  16.   If[PrimeQ[a], n = n + 1], {k, 0, 30030*100}]]
  17. n

  18. Out[74]= {36.0193, Null}

  19. Out[75]= 62228
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-4-4 07:36:05 | 显示全部楼层
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}
我只知道这么多,不知道你有没有更好的办法!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-5 13:38:21 | 显示全部楼层
.·.·. 发表于 2020-11-4 13:18
别这么搞
这么搞太慢效率太低
第一步是初筛,只需要排除2,3,5,7,11,13这些数字的倍数,就可以保证在300 ...

30030/5760=5.21354166667
平均每五个你才去掉四个,
而用素数判定,要四五十个最后才保留一个,比你这个算法不知道高到哪里去了

点评

我只是说,初筛可以节省素数判定的时间——你不会觉得筛素数是免费的吧  发表于 2020-11-6 10:58
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-3 14:37:59 | 显示全部楼层
很多电脑同时计算就可以缩短这个时间了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-3 13:45:56 | 显示全部楼层
lsr314 发表于 2019-4-3 14:37
很多电脑同时计算就可以缩短这个时间了

我感觉不像
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-11-3 16:32:14 | 显示全部楼层
有可能是GPU试除
GPU比CPU快很多
一群人一起拿CPU试除,应该会出结果的
有专门的GPU试除程序(在mersenneforum.org里面大概能找到)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-4 10:31:12 | 显示全部楼层
.·.·. 发表于 2020-11-3 16:32
有可能是GPU试除
GPU比CPU快很多
一群人一起拿CPU试除,应该会出结果的

2030912570882086247957711831528946513898296129355777
这个素数有52位,我觉得即使分算也很多
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-4 10:36:59 | 显示全部楼层
.·.·. 发表于 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个当中产生一个质数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-11-4 13:18:51 | 显示全部楼层
mathematica 发表于 2020-11-4 10:36
48.0077
平均48个当中产生一个质数

忽然想到一点
有没有可能是p-1?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-11-4 14:44:33 | 显示全部楼层
.·.·. 发表于 2020-11-4 13:18
忽然想到一点
有没有可能是p-1?

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

点评

你说得对,看来只可能是试除了。  发表于 2020-11-5 12:01
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-6-13 04:34 , Processed in 0.055319 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表