一个564位大整数分解

wsc810

  n=1734624471791475554302589708643097783774218447236640846493470190613635\
7919287910885759103833040883717798381086845154642194071297830613418986\
4280826014542758708589243873685563973118948869399158545506611147420216\
1325570172605641393943669457932209686651089596854827053880726458285541\
5193640191246493118254609287981573305779557335850498227928009094287256\
7591518912118622751714319229788100979251036035496917279912663527358783\
2366471931547770914277453770382945849189175903251109393813224860442985\
7397165071105924446217754254070691304703466464360349138244172330659883\
4176

这个数是费马数$F_11$的一个564位素因子减一得到的数值


F11=319489 × 974849 × 167988556341760475137 × 3560841906445833920513 × P564




这个数目前能完全分解么，找到它的小素因子也可以

mathematica

1. n=173462447179147555430258970864309778377421844723664084649347019061363579192879108857591038330408837177983810868451546421940712978306134189864280826014542758708589243873685563973118948869399158545506611147420216132557017260564139394366945793220968665108959685482705388072645828554151936401912464931182546092879815733057795573358504982279280090942872567591518912118622751714319229788100979251036035496917279912663527358783236647193154777091427745377038294584918917590325110939381322486044298573971650711059244462177542540706913047034664643603491382441723306598834176
   
2. m=2^13*139*1847*32488628503*1847272285831883*92147345984208191
   
3. aaa=n/m
   

复制代码

n=173462447179147555430258970864309778377421844723664084649347019061363579192879108857591038330408837177983810868451546421940712978306134189864280826014542758708589243873685563973118948869399158545506611147420216132557017260564139394366945793220968665108959685482705388072645828554151936401912464931182546092879815733057795573358504982279280090942872567591518912118622751714319229788100979251036035496917279912663527358783236647193154777091427745377038294584918917590325110939381322486044298573971650711059244462177542540706913047034664643603491382441723306598834176
m=2^13*139*1847*32488628503*1847272285831883*92147345984208191
aaa=n/m



1847272285831883
92147345984208191
32488628503
139
1847
2^13
这些都是因子

mathematica

mathematica 发表于 2020-10-25 08:17
n=1734624471791475554302589708643097783774218447236640846493470190613635791928791088575910383304 ...

23位的因子23918760924164258488261

mathematica

大整数分解很难，而且根据我的人生经验，似乎所有的有效分解算法，都依赖于小素数！

.·.·.

mathematica 发表于 2020-10-26 14:52
大整数分解很难，而且根据我的人生经验，似乎所有的有效分解算法，都依赖于小素数！

GNFS不是
但问题在于
GNFS也分解不了
现在剩下的这1624 bit，大概snfs应该也分解不出

mathematica

.·.·. 发表于 2020-10-26 23:12
GNFS不是
但问题在于
GNFS也分解不了

http://www.docin.com/p-436516064.html

我感觉你又胡说八道了！

.·.·.

mathematica 发表于 2020-10-27 08:21
http://www.docin.com/p-436516064.html

我感觉你又胡说八道了！

NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

NFS的本质就是找到类似x^2=y^2(mod n)但是x不等于正负y的一组解（只是类似，具体我没仔细研究）
论文里面说的是，我们要借助RFB寻找一个类似x^2=y^2(mod n)的结果
到这一步为止，我们对原数n没有任何假设。不管n的因子长什么样子，我们都可以用这种算法。

所以n的分解不会依赖某些$特定的$小素数。

当然你说”依赖于小素数“的意思是，只要素数出现过一次就算出现过，那你当我是胡说就好了。

mathematica

.·.·. 发表于 2020-10-27 19:57
NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

都需要小素数试除，把这个搞成光滑数

mathematica

.·.·. 发表于 2020-10-27 19:57
NFS跟你想的不一样
NFS对基底的要求并不高
并不是要求一个数字一定有一个非常好看的约数。

也许只有量子分解算法不依赖小素数

.·.·.

mathematica 发表于 2020-10-28 10:45
都需要小素数试除，把这个搞成光滑数

并不是
NFS分解只需要拿小素数做一组基
我简单地用MPQS来解释一下好了（虽然可能不对但原理类似）
在mod n意义下
比如你得到a^2=p1p2,b^2=p2p3,c^2=p1p3，那么(abc)^2=(p1p2p3)^2
如果abc不等于正负p1p2p3，那么我们就可以直接得到abc+p1p2p3和abc-p1p2p3都与n有非平凡的公约数

在这一过程中p1p2p3只起到了基底的作用