数学研发网设为首页收藏本站
切换到窄版

 找回密码
 欢迎注册
数学研发论坛»论坛 › 【数学研究】 › 数学欣赏 › 发一个变态的卡米歇尔强伪素数
12下一页
返回列表 发新帖
查看: 15725|回复: 22

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

[复制链接]
mathematica
发表于 2019-2-24 13:54:40 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要 登录 才可以下载或查看，没有账号？欢迎注册

×
2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867

这个数是307以下的所有数强伪素数!


来源
https://ac.els-cdn.com/S07477171 ... f5bb65273473479dd16
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复

使用道具 举报

mathematica
 楼主| 发表于 2019-2-24 14:13:31 | 显示全部楼层
mathematica 发表于 2019-2-24 09:33
这是我重新写的miller rabin算法的代码,又简化了!

  1. Clear["Global`*"];
  2. n=2887148238050771212671429597130393991977609459279722700926516024197432\
  3. 3037991527331163289831446392259419778031109293496555784189494417409338\
  4. 0561511397999942154241693397290542371100275104208013496673175515285922\
  5. 6962916775325475044445856101949404200039904432116776619949629539250452\
  6. 6987193290703735640322737012784538991261203092448414947289768854060249\
  7. 76768122077071687938121709811322297802059565867;
  8. (*miller rabin子函数*)
  9. MR[n0_,a0_]:=Module[{n=n0,a=a0,s,m,t1,k},
  10.     s=0;m=n-1;While[Mod[m,2]==0,m=m/2;s=s+1];
  11.     t1=PowerMod[a,m,n];
  12.     If[t1==1,Return[True]];
  13.     k=0;While[k<s-1&&t1!=n-1,k=k+1;t1=Mod[t1^2,n]];
  14.     If[t1==n-1,Return[True],Return[False]]
  15. ]
  16. Do[Print[{k,MR[n,k]}],{k,1,307}]
复制代码

运行结果
  1. {1,True}
  2. {2,True}
  3. {3,True}
  4. {4,True}
  5. {5,True}
  6. {6,True}
  7. {7,True}
  8. {8,True}
  9. {9,True}
  10. {10,True}
  11. {11,True}
  12. {12,True}
  13. {13,True}
  14. {14,True}
  15. {15,True}
  16. {16,True}
  17. {17,True}
  18. {18,True}
  19. {19,True}
  20. {20,True}
  21. {21,True}
  22. {22,True}
  23. {23,True}
  24. {24,True}
  25. {25,True}
  26. {26,True}
  27. {27,True}
  28. {28,True}
  29. {29,True}
  30. {30,True}
  31. {31,True}
  32. {32,True}
  33. {33,True}
  34. {34,True}
  35. {35,True}
  36. {36,True}
  37. {37,True}
  38. {38,True}
  39. {39,True}
  40. {40,True}
  41. {41,True}
  42. {42,True}
  43. {43,True}
  44. {44,True}
  45. {45,True}
  46. {46,True}
  47. {47,True}
  48. {48,True}
  49. {49,True}
  50. {50,True}
  51. {51,True}
  52. {52,True}
  53. {53,True}
  54. {54,True}
  55. {55,True}
  56. {56,True}
  57. {57,True}
  58. {58,True}
  59. {59,True}
  60. {60,True}
  61. {61,True}
  62. {62,True}
  63. {63,True}
  64. {64,True}
  65. {65,True}
  66. {66,True}
  67. {67,True}
  68. {68,True}
  69. {69,True}
  70. {70,True}
  71. {71,True}
  72. {72,True}
  73. {73,True}
  74. {74,True}
  75. {75,True}
  76. {76,True}
  77. {77,True}
  78. {78,True}
  79. {79,True}
  80. {80,True}
  81. {81,True}
  82. {82,True}
  83. {83,True}
  84. {84,True}
  85. {85,True}
  86. {86,True}
  87. {87,True}
  88. {88,True}
  89. {89,True}
  90. {90,True}
  91. {91,True}
  92. {92,True}
  93. {93,True}
  94. {94,True}
  95. {95,True}
  96. {96,True}
  97. {97,True}
  98. {98,True}
  99. {99,True}
  100. {100,True}
  101. {101,True}
  102. {102,True}
  103. {103,True}
  104. {104,True}
  105. {105,True}
  106. {106,True}
  107. {107,True}
  108. {108,True}
  109. {109,True}
  110. {110,True}
  111. {111,True}
  112. {112,True}
  113. {113,True}
  114. {114,True}
  115. {115,True}
  116. {116,True}
  117. {117,True}
  118. {118,True}
  119. {119,True}
  120. {120,True}
  121. {121,True}
  122. {122,True}
  123. {123,True}
  124. {124,True}
  125. {125,True}
  126. {126,True}
  127. {127,True}
  128. {128,True}
  129. {129,True}
  130. {130,True}
  131. {131,True}
  132. {132,True}
  133. {133,True}
  134. {134,True}
  135. {135,True}
  136. {136,True}
  137. {137,True}
  138. {138,True}
  139. {139,True}
  140. {140,True}
  141. {141,True}
  142. {142,True}
  143. {143,True}
  144. {144,True}
  145. {145,True}
  146. {146,True}
  147. {147,True}
  148. {148,True}
  149. {149,True}
  150. {150,True}
  151. {151,True}
  152. {152,True}
  153. {153,True}
  154. {154,True}
  155. {155,True}
  156. {156,True}
  157. {157,True}
  158. {158,True}
  159. {159,True}
  160. {160,True}
  161. {161,True}
  162. {162,True}
  163. {163,True}
  164. {164,True}
  165. {165,True}
  166. {166,True}
  167. {167,True}
  168. {168,True}
  169. {169,True}
  170. {170,True}
  171. {171,True}
  172. {172,True}
  173. {173,True}
  174. {174,True}
  175. {175,True}
  176. {176,True}
  177. {177,True}
  178. {178,True}
  179. {179,True}
  180. {180,True}
  181. {181,True}
  182. {182,True}
  183. {183,True}
  184. {184,True}
  185. {185,True}
  186. {186,True}
  187. {187,True}
  188. {188,True}
  189. {189,True}
  190. {190,True}
  191. {191,True}
  192. {192,True}
  193. {193,True}
  194. {194,True}
  195. {195,True}
  196. {196,True}
  197. {197,True}
  198. {198,True}
  199. {199,True}
  200. {200,True}
  201. {201,True}
  202. {202,True}
  203. {203,True}
  204. {204,True}
  205. {205,True}
  206. {206,True}
  207. {207,True}
  208. {208,True}
  209. {209,True}
  210. {210,True}
  211. {211,True}
  212. {212,True}
  213. {213,True}
  214. {214,True}
  215. {215,True}
  216. {216,True}
  217. {217,True}
  218. {218,True}
  219. {219,True}
  220. {220,True}
  221. {221,True}
  222. {222,True}
  223. {223,True}
  224. {224,True}
  225. {225,True}
  226. {226,True}
  227. {227,True}
  228. {228,True}
  229. {229,True}
  230. {230,True}
  231. {231,True}
  232. {232,True}
  233. {233,True}
  234. {234,True}
  235. {235,True}
  236. {236,True}
  237. {237,True}
  238. {238,True}
  239. {239,True}
  240. {240,True}
  241. {241,True}
  242. {242,True}
  243. {243,True}
  244. {244,True}
  245. {245,True}
  246. {246,True}
  247. {247,True}
  248. {248,True}
  249. {249,True}
  250. {250,True}
  251. {251,True}
  252. {252,True}
  253. {253,True}
  254. {254,True}
  255. {255,True}
  256. {256,True}
  257. {257,True}
  258. {258,True}
  259. {259,True}
  260. {260,True}
  261. {261,True}
  262. {262,True}
  263. {263,True}
  264. {264,True}
  265. {265,True}
  266. {266,True}
  267. {267,True}
  268. {268,True}
  269. {269,True}
  270. {270,True}
  271. {271,True}
  272. {272,True}
  273. {273,True}
  274. {274,True}
  275. {275,True}
  276. {276,True}
  277. {277,True}
  278. {278,True}
  279. {279,True}
  280. {280,True}
  281. {281,True}
  282. {282,True}
  283. {283,True}
  284. {284,True}
  285. {285,True}
  286. {286,True}
  287. {287,True}
  288. {288,True}
  289. {289,True}
  290. {290,True}
  291. {291,True}
  292. {292,True}
  293. {293,True}
  294. {294,True}
  295. {295,True}
  296. {296,True}
  297. {297,True}
  298. {298,True}
  299. {299,True}
  300. {300,True}
  301. {301,True}
  302. {302,True}
  303. {303,True}
  304. {304,True}
  305. {305,True}
  306. {306,True}
  307. {307,False}
复制代码
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2019-2-24 14:14:29 | 显示全部楼层
https://bbs.emath.ac.cn/forum.ph ... 734&fromuid=865
用此处的lucas判定办法,就回得到false的答案!
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2019-2-24 15:06:53 | 显示全部楼层
这个伪素数可以写成
n=(353*m+1)*(313*m+1)*(m+1)
2967449566868551055015417464290533273077199179985304335099507553127683\
8753171770199594238596428121188033664754218345562493168782882
=18132954*1636495392239207718177312678502649525872728282432804018087459744908459\
964833736974107706808081469858029401318407268091150133

问题来了
1636495392239207718177312678502649525872728282432804018087459744908459964833736974107706808081469858029401318407268091150133
是个合数,但是谁能分解呢?


补充内容 (2019-2-26 08:43):
n=(353*m+1)*(313*m+1)*(m+1)其中m=29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782882
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

zeroieme
发表于 2019-2-24 16:59:08 | 显示全部楼层
男子痴迷数论研究20年没人认可,如今靠低保度日

点评

wayne
好可乐  发表于 2019-2-24 17:10
wayne
蛤蛤蛤  发表于 2019-2-24 17:10
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2019-2-25 08:20:23 | 显示全部楼层
本帖最后由 mathematica 于 2019-2-25 08:21 编辑

你的左右晃动,是怎么搞出来的?
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

.·.·.
发表于 2019-2-25 18:38:32 | 显示全部楼层
mathematica 发表于 2019-2-24 15:06
这个伪素数可以写成
n=(353*m+1)*(313*m+1)*(m+1)
296744956686855105501541746429053327307719917998530 ...
  1. Mon Feb 25 18:30:41 2019  Msieve v. 1.53 (SVN 1005)
  2. Mon Feb 25 18:30:41 2019  random seeds: 2a1e3eb8 e2eb3fca
  3. Mon Feb 25 18:30:41 2019  factoring 1636495392239207718177312678502649525872728282432804018087459744908459964833736974107706808081469858029401318407268091150133 (124 digits)
  4. Mon Feb 25 18:30:42 2019  searching for 15-digit factors
  5. Mon Feb 25 18:30:42 2019  commencing quadratic sieve (124-digit input)
  6. Mon Feb 25 18:30:43 2019  using multiplier of 1
  7. Mon Feb 25 18:30:43 2019  using generic 32kb sieve core
  8. Mon Feb 25 18:30:43 2019  sieve interval: 96 blocks of size 32768
  9. Mon Feb 25 18:30:43 2019  processing polynomials in batches of 3
  10. Mon Feb 25 18:30:43 2019  using a sieve bound of 14643449 (475000 primes)
  11. Mon Feb 25 18:30:43 2019  using large prime bound of 2196517350 (31 bits)
  12. Mon Feb 25 18:30:43 2019  using double large prime bound of 65331457041037350 (48-56 bits)
  13. Mon Feb 25 18:30:43 2019  using trial factoring cutoff of 56 bits
  14. Mon Feb 25 18:30:43 2019  polynomial 'A' values have 15 factors
  15. Mon Feb 25 18:37:02 2019  5 relations (5 full + 0 combined from 552 partial), need 475096
  16. Mon Feb 25 18:37:02 2019  elapsed time 00:06:21
复制代码

一定是我的打开方式有问题……
大概我可以用一年时间完成这个分解……
我再试试别的
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

.·.·.
发表于 2019-2-25 21:29:27 | 显示全部楼层
本帖最后由 .·.·. 于 2019-2-26 02:33 编辑

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

found factor = 877450288288670004098523859
pari/GP已经尽力了
剩下的工作很快就能完成
2756 relations (2494 full + 262 combined from 156862 partial), need 85978
不要着急……

  1. Mon Feb 25 21:41:10 2019  
  2. Mon Feb 25 21:41:10 2019  
  3. Mon Feb 25 21:41:10 2019  Msieve v. 1.53 (SVN 1005)
  4. Mon Feb 25 21:41:10 2019  random seeds: 6ffdf664 9aae7fb8
  5. Mon
  6. Feb 25 21:41:10 2019  factoring
  7. 1865057672305216124413628970755133463269286868337470113025947146973580889611152889335486074601687
  8. (97 digits)
  9. Mon Feb 25 21:41:10 2019  searching for 15-digit factors
  10. Mon Feb 25 21:41:11 2019  commencing quadratic sieve (97-digit input)
  11. Mon Feb 25 21:41:11 2019  using multiplier of 3
  12. Mon Feb 25 21:41:11 2019  using generic 32kb sieve core
  13. Mon Feb 25 21:41:11 2019  sieve interval: 36 blocks of size 32768
  14. Mon Feb 25 21:41:11 2019  processing polynomials in batches of 6
  15. Mon Feb 25 21:41:11 2019  using a sieve bound of 2331599 (85882 primes)
  16. Mon Feb 25 21:41:11 2019  using large prime bound of 349739850 (28 bits)
  17. Mon Feb 25 21:41:11 2019  using double large prime bound of 2391889720101900 (43-52 bits)
  18. Mon Feb 25 21:41:11 2019  using trial factoring cutoff of 52 bits
  19. Mon Feb 25 21:41:11 2019  polynomial 'A' values have 13 factors
  20. Tue Feb 26 02:16:31 2019  86444 relations (20669 full + 65775 combined from 1299346 partial), need 85978
  21. Tue Feb 26 02:16:32 2019  begin with 1320015 relations
  22. Tue Feb 26 02:16:33 2019  reduce to 227228 relations in 11 passes
  23. Tue Feb 26 02:16:33 2019  attempting to read 227228 relations
  24. Tue Feb 26 02:16:35 2019  recovered 227228 relations
  25. Tue Feb 26 02:16:35 2019  recovered 214747 polynomials
  26. Tue Feb 26 02:16:35 2019  attempting to build 86444 cycles
  27. Tue Feb 26 02:16:35 2019  found 86444 cycles in 6 passes
  28. Tue Feb 26 02:16:35 2019  distribution of cycle lengths:
  29. Tue Feb 26 02:16:35 2019     length 1 : 20669
  30. Tue Feb 26 02:16:35 2019     length 2 : 14862
  31. Tue Feb 26 02:16:35 2019     length 3 : 14475
  32. Tue Feb 26 02:16:35 2019     length 4 : 11726
  33. Tue Feb 26 02:16:35 2019     length 5 : 9005
  34. Tue Feb 26 02:16:35 2019     length 6 : 6099
  35. Tue Feb 26 02:16:35 2019     length 7 : 3974
  36. Tue Feb 26 02:16:35 2019     length 9+: 5634
  37. Tue Feb 26 02:16:35 2019  largest cycle: 20 relations
  38. Tue Feb 26 02:16:36 2019  matrix is 85882 x 86444 (25.0 MB) with weight 5849567 (67.67/col)
  39. Tue Feb 26 02:16:36 2019  sparse part has weight 5849567 (67.67/col)
  40. Tue Feb 26 02:16:37 2019  filtering completed in 3 passes
  41. Tue Feb 26 02:16:37 2019  matrix is 82107 x 82171 (23.7 MB) with weight 5554996 (67.60/col)
  42. Tue Feb 26 02:16:37 2019  sparse part has weight 5554996 (67.60/col)
  43. Tue Feb 26 02:16:37 2019  saving the first 48 matrix rows for later
  44. Tue Feb 26 02:16:37 2019  matrix includes 64 packed rows
  45. Tue Feb 26 02:16:37 2019  matrix is 82059 x 82171 (15.6 MB) with weight 4447022 (54.12/col)
  46. Tue Feb 26 02:16:37 2019  sparse part has weight 3255824 (39.62/col)
  47. Tue Feb 26 02:16:37 2019  using block size 8192 and superblock size 884736 for processor cache size 9216 kB
  48. Tue Feb 26 02:16:38 2019  commencing Lanczos iteration
  49. Tue Feb 26 02:16:38 2019  memory use: 9.9 MB
  50. Tue Feb 26 02:16:57 2019  linear algebra at 58.6%, ETA 0h 0m
  51. Tue Feb 26 02:17:09 2019  lanczos halted after 1299 iterations (dim = 82057)
  52. Tue Feb 26 02:17:09 2019  recovered 16 nontrivial dependencies
  53. Tue Feb 26 02:17:10 2019  p42 factor: 179951404407700053508335546465851287509301
  54. Tue Feb 26 02:17:10 2019  p56 factor: 10364229601007831878377902195192125938721193826116042587
  55. Tue Feb 26 02:17:10 2019  elapsed time 04:36:00
复制代码

点评

mathematica
你分解了四个半小时呀，真难为你了！  发表于 2019-2-26 08:42
mathematica
你分解了四个半小时呀，真难为你了！  发表于 2019-2-26 08:42
mathematica
你分解了四个半小时呀，真难为你了！  发表于 2019-2-26 08:41
mathematica
我也想学会用pari/gp过滤出小的因子！  发表于 2019-2-26 08:38
mathematica
877450288288670004098523859这个27的因子如何用pari/gp得到的？  发表于 2019-2-26 08:38
下一页
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

mathematica
 楼主| 发表于 2019-2-26 08:56:13 | 显示全部楼层
.·.·. 发表于 2019-2-25 21:29
found factor = 877450288288670004098523859
pari/GP已经尽力了
剩下的工作很快就能完成

有个软件叫GMP-ECM可惜要在Linux上玩，估计应该是ECM界最先进的分解整数的办法了！
但是我不会Linux
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

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

pari/gp自带一个ECM，可以用来过滤小因子
你开\g4之后仔细看日志就好
然后，ecm速度不如qs速度快
本来想尝试nfs的，结果被坑得很惨很惨……
看上去我还需要仔细研究一下nfs究竟是个什么鬼才好
毋因群疑而阻独见　　毋任己意而废人言
毋私小惠而伤大体　　毋借公论以快私情
回复 支持 反对

使用道具 举报

12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-4-26 23:58 , Processed in 0.092275 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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