论坛 › 刨根究底 › 人类是怎么知道费马数F118的因子的?

mathematica 发表于 2019-4-3 11:51:26

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

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 发表于 2019-4-3 14:37:59

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

mathematica 发表于 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}
我只知道这么多,不知道你有没有更好的办法!

mathematica 发表于 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里面大概能找到）

mathematica 发表于 2020-11-4 10:31:12

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


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

mathematica 发表于 2020-11-4 10:36:59

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


Clear["Global`*"];
n=0;
Do,n=n+1],{k,10^5,2*10^5}]
Print


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

.·.·. 发表于 2020-11-4 13:18:16

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

别这么搞
这么搞太慢效率太低
第一步是初筛，只需要排除2,3,5,7,11,13这些数字的倍数，就可以保证在30030个数字里只有5760个待选数字
这一步可以节省一点伪素数算法的耗时
ClearSystemCache[]; Timing[n = 0;
t = Pick,
   Table[! (Divisible || Divisible ||
       Divisible || Divisible ||
       Divisible || Divisible), {i,
   1, 30030}]]; Do[n += \!\(
\*UnderoverscriptBox[\(\\), \(i\), \(t\)]\(PrimeQ[\((i +
         k\ 30030)\)\
\*SuperscriptBox[\(2\), \(120\)] + 1]\)\), {k, 1, 10}]; n]
Clear["Global`*"];
n = 0;
Timing[Do[a = k*2^120 + 1;
If, n = n + 1], {k, 30030, 30030*11}]]
Print
In:= ClearSystemCache[]; Timing[n = 0;
t = Pick,
   Table[! (Divisible || Divisible ||
       Divisible || Divisible ||
       Divisible || Divisible), {i,
   1, 30030}]]; Do[n += \!\(
\*UnderoverscriptBox[\(\\), \(i\), \(t\)]\(PrimeQ[\((i +
         k\ 30030)\)\
\*SuperscriptBox[\(2\), \(120\)] + 1]\)\), {k, 0, 99}]; n]

Out= {30.1495, 1089772 False + 62228 True}

In:= N

Out= 48.1812

In:= Clear["Global`*"];
n = 0;
Timing[Do[a = k*2^120 + 1;
If, n = n + 1], {k, 0, 30030*100}]]
n

Out= {36.0193, Null}

Out= 62228

.·.·. 发表于 2020-11-4 13:18:51

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

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

mathematica 发表于 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}}
且需要模合数，你觉得你模得起吗？

查看完整版本: 人类是怎么知道费马数F118的因子的?