第14个费马数的因子是怎么来的？

mathematica

1. Clear["Global`*"];(*Clear all variables*)
   
2. F14=2^(2^14)+1;
   
3. b=1784180997819127957596374417642156545110881094717;
   
4. factor=b*2^16+1;
   
5. IntegerQ[F14/factor]
   

复制代码

经过mathematica软件的检验，确实是一个因子，
但是这个b=1784180997819127957596374417642156545110881094717
也是个49位的整数，
电脑一秒钟算10000个
10^48/(365*24*3600*10000)=3.17098*10^36年，
所以问题来了，这个b是怎么来的？
谁有相关的资料呢？

即使分解这个F14，它也有4933位，根本不可能分解的

虽然费马数的因子都是k*2^(n+2)+1的形式

既然穷举法很难办到，然后质因数分解很难，那么这个b怎么来的？我很想不明白。
感觉就像外星球掉到地球上的一样！

对了，这个factor是个质数

zeroieme

楼主不是有台任何代码都能在一秒算出结果的电脑吗？

mathe

http://www.fermatsearch.org/news.html
http://www.fermatsearch.org/algorithm.html

nyy

第14个费马数F14
Here is the sigma from results.txt
ECM found a factor in curve #1, stage #2
Sigma=8585974330888598, B1=110000000, B2=11000000000.
UID: rajula/desktop_1, F14 has a factor: 116928085873074369829035993834596371340386703423373313

利用椭圆曲线使劲分解整数的，找到素数因子附近的光滑数，然后利用光滑数来找到这个素数因子！
这里陷入了逻辑上的循环：要找到素数因子就必须先找到素数因子附近的光滑数，要找到光滑数就必须先知道这个素数因子的大小。
如何才能破解这个循环呢？假设这个素数因子有10位、假设有15位、假设有20位、假设有25位、假设有30位、假设有35位，不断地试然后找光滑数。
最终通过光滑数来找到这个素数因子！


第一个发现费马数F14因子的论坛记录
https://www.mersenneforum.org/sh ... 1340386703423373313


用来计算群的阶（光滑数）的代码的网站
http://magma.maths.usyd.edu.au/calc/


FindGroupOrder := function (p, sigma)
   K := GF(p);
   v := K ! (4*sigma);
   u := K ! (sigma^2-5);
   x := u^3;
   b := 4*x*v;
   a := (v-u)^3*(3*u+v);
   A := a/b-2;
   x := x/v^3;
   b := x^3 + A*x^2 + x;
   E := EllipticCurve([0,b*A,0,b^2,0]);
   return FactoredOrder(E);
end function;
p:=116928085873074369829035993834596371340386703423373313;
sigma:=8585974330888598;
FindGroupOrder(p,sigma);

[ <2, 2>, <3, 1>, <53, 1>, <107, 1>, <3433, 1>, <37087, 1>, <110323, 1>,
<128321, 1>, <1738307, 1>, <9338881, 1>, <74968979, 1>, <783277631, 1> ]

nyy

nyy 发表于 2023-3-30 08:49
第14个费马数F14
Here is the sigma from results.txt
ECM found a factor in curve #1, stage #2

估计是论坛bug。
我以前粘贴的代码不是那样。如果是那样，我当时就修正过来了。

现在贴上以前的代码

1. FindGroupOrder := function (p, sigma)
   
2.    K := GF(p);
   
3.    v := K ! (4*sigma);
   
4.    u := K ! (sigma^2-5);
   
5.    x := u^3;
   
6.    b := 4*x*v;
   
7.    a := (v-u)^3*(3*u+v);
   
8.    A := a/b-2;
   
9.    x := x/v^3;
   
10.    b := x^3 + A*x^2 + x;
    
11.    E := EllipticCurve([0,b*A,0,b^2,0]);
    
12.    return FactoredOrder(E);
    
13. end function;
    
14. p:=116928085873074369829035993834596371340386703423373313;
    
15. sigma:=8585974330888598;
    
16. FindGroupOrder(p,sigma);

复制代码

贴上几处我以前的代码

https://bbs.emath.ac.cn/forum.ph ... 17438&pid=85700
https://bbs.emath.ac.cn/forum.ph ... 15706&pid=85352
https://bbs.emath.ac.cn/forum.ph ... 15773&pid=77805

为什么我以前贴的没问题，而上面的有问题呢？