找回密码
 欢迎注册
楼主: mathematica

[欣赏] 发一个变态的卡米歇尔强伪素数

[复制链接]
发表于 2019-2-27 13:28:04 | 显示全部楼层
mathematica 发表于 2019-2-24 15:06
这个伪素数可以写成
n=(353*m+1)*(313*m+1)*(m+1)
296744956686855105501541746429053327307719917998530 ...

有没有分解
  1. 2887148238050771212671429597130393991977609459279722700926516024197432303799152733116328983144639225941977803110929349655578418949441740933805615113979999421542416933972905423711002751042080134966731755152859226962916775325475044445856101949404200039904432116776619949629539250452698719329070373564032273701278453899126120309244841494728976885406024976768122077071687938121709811322297802059565867-1
复制代码
的想法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-2-27 13:54:56 | 显示全部楼层
本帖最后由 mathematica 于 2019-2-27 14:07 编辑
.·.·. 发表于 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位的整数很难,你可以试试,运气好也能分解出来

点评

发现了一个好东西,cado-nfs,等我弄清楚之后告诉你怎么用  发表于 2019-2-28 13:45
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-27 14:24:25 | 显示全部楼层
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)好像已经被分解完了……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-28 19:34:51 | 显示全部楼层
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果然是世界最快算法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 21:28 , Processed in 0.041345 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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