发一个变态的卡米歇尔强伪素数

.·.·.

mathematica 发表于 2019-2-24 15:06
这个伪素数可以写成
n=(353*m+1)*(313*m+1)*(m+1)
296744956686855105501541746429053327307719917998530 ...

有没有分解

1. 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867-1

复制代码

的想法？

mathematica

.·.·. 发表于 2019-2-27 13:28
有没有分解
的想法？

卡米歇尔数特殊呀，n=(353*m+1)*(313*m+1)*(m+1)这个数有因子
353*m
313*m
m
而这个m都被你分解了！

m=29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782882
18132954
877450288288670004098523859
179951404407700053508335546465851287509301
10364229601007831878377902195192125938721193826116042587
上面三个是你给出的因子
这个是因子呀
107
313
353
6833
这四个也是因子呀，合并起来就是80781933059

剩下这个没分解了
1204402074581484201772741997070828846397316087291970006499792212079626\
3374681528894350842189934080263942574287348857587613478134990127005938\
0701567847111959285586830089089882272379808702281016550561146854693789\
7100403922019888509674828834999181775429597207
一定是合数，要想分解这个256位的整数很难，你可以试试，运气好也能分解出来

.·.·.

mathematica 发表于 2019-2-27 13:54
卡米歇尔数特殊呀，n=(353*m+1)*(313*m+1)*(m+1)这个数有因子
353*m
313*m

写错了……
我本来是想分解phi(n)的……
算质数的phi算多了照着合数就来了一个n-1……
然而发现phi(n)好像已经被分解完了……

.·.·.

mathematica 发表于 2019-2-26 08:56
有个软件叫GMP-ECM可惜要在Linux上玩，估计应该是ECM界最先进的分解整数的办法了！
但是我不会Linux

Complete Factorization: Total cpu/elapsed time for entire factorization: 183389/18975.4
10364229601007831878377902195192125938721193826116042587 179951404407700053508335546465851287509301 877450288288670004098523859
用了20000秒左右的样子分解了m（没筛掉那个小因子）
cado-nfs果然是个好东西
GNFS果然是世界最快算法