发一个变态的卡米歇尔强伪素数
2887148238050771212671429597130393991977609459279722700926516024197432\3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867
这个数是307以下的所有数强伪素数!
来源
https://ac.els-cdn.com/S0747717185710425/1-s2.0-S0747717185710425-main.pdf?_tid=33f92bb5-2428-4b05-a90d-8420afcf448f&acdnat=1550986509_c19e477a7e993f5bb65273473479dd16 mathematica 发表于 2019-2-24 09:33
这是我重新写的miller rabin算法的代码,又简化了!
Clear["Global`*"];
n=2887148238050771212671429597130393991977609459279722700926516024197432\
3037991527331163289831446392259419778031109293496555784189494417409338\
0561511397999942154241693397290542371100275104208013496673175515285922\
6962916775325475044445856101949404200039904432116776619949629539250452\
6987193290703735640322737012784538991261203092448414947289768854060249\
76768122077071687938121709811322297802059565867;
(*miller rabin子函数*)
MR:=Module[{n=n0,a=a0,s,m,t1,k},
s=0;m=n-1;While==0,m=m/2;s=s+1];
t1=PowerMod;
If];
k=0;While];
If,Return]
]
Do}],{k,1,307}]
运行结果
{1,True}
{2,True}
{3,True}
{4,True}
{5,True}
{6,True}
{7,True}
{8,True}
{9,True}
{10,True}
{11,True}
{12,True}
{13,True}
{14,True}
{15,True}
{16,True}
{17,True}
{18,True}
{19,True}
{20,True}
{21,True}
{22,True}
{23,True}
{24,True}
{25,True}
{26,True}
{27,True}
{28,True}
{29,True}
{30,True}
{31,True}
{32,True}
{33,True}
{34,True}
{35,True}
{36,True}
{37,True}
{38,True}
{39,True}
{40,True}
{41,True}
{42,True}
{43,True}
{44,True}
{45,True}
{46,True}
{47,True}
{48,True}
{49,True}
{50,True}
{51,True}
{52,True}
{53,True}
{54,True}
{55,True}
{56,True}
{57,True}
{58,True}
{59,True}
{60,True}
{61,True}
{62,True}
{63,True}
{64,True}
{65,True}
{66,True}
{67,True}
{68,True}
{69,True}
{70,True}
{71,True}
{72,True}
{73,True}
{74,True}
{75,True}
{76,True}
{77,True}
{78,True}
{79,True}
{80,True}
{81,True}
{82,True}
{83,True}
{84,True}
{85,True}
{86,True}
{87,True}
{88,True}
{89,True}
{90,True}
{91,True}
{92,True}
{93,True}
{94,True}
{95,True}
{96,True}
{97,True}
{98,True}
{99,True}
{100,True}
{101,True}
{102,True}
{103,True}
{104,True}
{105,True}
{106,True}
{107,True}
{108,True}
{109,True}
{110,True}
{111,True}
{112,True}
{113,True}
{114,True}
{115,True}
{116,True}
{117,True}
{118,True}
{119,True}
{120,True}
{121,True}
{122,True}
{123,True}
{124,True}
{125,True}
{126,True}
{127,True}
{128,True}
{129,True}
{130,True}
{131,True}
{132,True}
{133,True}
{134,True}
{135,True}
{136,True}
{137,True}
{138,True}
{139,True}
{140,True}
{141,True}
{142,True}
{143,True}
{144,True}
{145,True}
{146,True}
{147,True}
{148,True}
{149,True}
{150,True}
{151,True}
{152,True}
{153,True}
{154,True}
{155,True}
{156,True}
{157,True}
{158,True}
{159,True}
{160,True}
{161,True}
{162,True}
{163,True}
{164,True}
{165,True}
{166,True}
{167,True}
{168,True}
{169,True}
{170,True}
{171,True}
{172,True}
{173,True}
{174,True}
{175,True}
{176,True}
{177,True}
{178,True}
{179,True}
{180,True}
{181,True}
{182,True}
{183,True}
{184,True}
{185,True}
{186,True}
{187,True}
{188,True}
{189,True}
{190,True}
{191,True}
{192,True}
{193,True}
{194,True}
{195,True}
{196,True}
{197,True}
{198,True}
{199,True}
{200,True}
{201,True}
{202,True}
{203,True}
{204,True}
{205,True}
{206,True}
{207,True}
{208,True}
{209,True}
{210,True}
{211,True}
{212,True}
{213,True}
{214,True}
{215,True}
{216,True}
{217,True}
{218,True}
{219,True}
{220,True}
{221,True}
{222,True}
{223,True}
{224,True}
{225,True}
{226,True}
{227,True}
{228,True}
{229,True}
{230,True}
{231,True}
{232,True}
{233,True}
{234,True}
{235,True}
{236,True}
{237,True}
{238,True}
{239,True}
{240,True}
{241,True}
{242,True}
{243,True}
{244,True}
{245,True}
{246,True}
{247,True}
{248,True}
{249,True}
{250,True}
{251,True}
{252,True}
{253,True}
{254,True}
{255,True}
{256,True}
{257,True}
{258,True}
{259,True}
{260,True}
{261,True}
{262,True}
{263,True}
{264,True}
{265,True}
{266,True}
{267,True}
{268,True}
{269,True}
{270,True}
{271,True}
{272,True}
{273,True}
{274,True}
{275,True}
{276,True}
{277,True}
{278,True}
{279,True}
{280,True}
{281,True}
{282,True}
{283,True}
{284,True}
{285,True}
{286,True}
{287,True}
{288,True}
{289,True}
{290,True}
{291,True}
{292,True}
{293,True}
{294,True}
{295,True}
{296,True}
{297,True}
{298,True}
{299,True}
{300,True}
{301,True}
{302,True}
{303,True}
{304,True}
{305,True}
{306,True}
{307,False}
https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15734&fromuid=865
用此处的lucas判定办法,就回得到false的答案! 这个伪素数可以写成
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 男子痴迷数论研究20年没人认可,如今靠低保度日 本帖最后由 mathematica 于 2019-2-25 08:21 编辑
你的左右晃动,是怎么搞出来的? mathematica 发表于 2019-2-24 15:06
这个伪素数可以写成
n=(353*m+1)*(313*m+1)*(m+1)
296744956686855105501541746429053327307719917998530 ...
Mon Feb 25 18:30:41 2019Msieve v. 1.53 (SVN 1005)
Mon Feb 25 18:30:41 2019random seeds: 2a1e3eb8 e2eb3fca
Mon Feb 25 18:30:41 2019factoring 1636495392239207718177312678502649525872728282432804018087459744908459964833736974107706808081469858029401318407268091150133 (124 digits)
Mon Feb 25 18:30:42 2019searching for 15-digit factors
Mon Feb 25 18:30:42 2019commencing quadratic sieve (124-digit input)
Mon Feb 25 18:30:43 2019using multiplier of 1
Mon Feb 25 18:30:43 2019using generic 32kb sieve core
Mon Feb 25 18:30:43 2019sieve interval: 96 blocks of size 32768
Mon Feb 25 18:30:43 2019processing polynomials in batches of 3
Mon Feb 25 18:30:43 2019using a sieve bound of 14643449 (475000 primes)
Mon Feb 25 18:30:43 2019using large prime bound of 2196517350 (31 bits)
Mon Feb 25 18:30:43 2019using double large prime bound of 65331457041037350 (48-56 bits)
Mon Feb 25 18:30:43 2019using trial factoring cutoff of 56 bits
Mon Feb 25 18:30:43 2019polynomial 'A' values have 15 factors
Mon Feb 25 18:37:02 20195 relations (5 full + 0 combined from 552 partial), need 475096
Mon Feb 25 18:37:02 2019elapsed time 00:06:21
一定是我的打开方式有问题……
大概我可以用一年时间完成这个分解……
我再试试别的 本帖最后由 .·.·. 于 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
不要着急……
Mon Feb 25 21:41:10 2019
Mon Feb 25 21:41:10 2019
Mon Feb 25 21:41:10 2019Msieve v. 1.53 (SVN 1005)
Mon Feb 25 21:41:10 2019random seeds: 6ffdf664 9aae7fb8
Mon
Feb 25 21:41:10 2019factoring
1865057672305216124413628970755133463269286868337470113025947146973580889611152889335486074601687
(97 digits)
Mon Feb 25 21:41:10 2019searching for 15-digit factors
Mon Feb 25 21:41:11 2019commencing quadratic sieve (97-digit input)
Mon Feb 25 21:41:11 2019using multiplier of 3
Mon Feb 25 21:41:11 2019using generic 32kb sieve core
Mon Feb 25 21:41:11 2019sieve interval: 36 blocks of size 32768
Mon Feb 25 21:41:11 2019processing polynomials in batches of 6
Mon Feb 25 21:41:11 2019using a sieve bound of 2331599 (85882 primes)
Mon Feb 25 21:41:11 2019using large prime bound of 349739850 (28 bits)
Mon Feb 25 21:41:11 2019using double large prime bound of 2391889720101900 (43-52 bits)
Mon Feb 25 21:41:11 2019using trial factoring cutoff of 52 bits
Mon Feb 25 21:41:11 2019polynomial 'A' values have 13 factors
Tue Feb 26 02:16:31 201986444 relations (20669 full + 65775 combined from 1299346 partial), need 85978
Tue Feb 26 02:16:32 2019begin with 1320015 relations
Tue Feb 26 02:16:33 2019reduce to 227228 relations in 11 passes
Tue Feb 26 02:16:33 2019attempting to read 227228 relations
Tue Feb 26 02:16:35 2019recovered 227228 relations
Tue Feb 26 02:16:35 2019recovered 214747 polynomials
Tue Feb 26 02:16:35 2019attempting to build 86444 cycles
Tue Feb 26 02:16:35 2019found 86444 cycles in 6 passes
Tue Feb 26 02:16:35 2019distribution of cycle lengths:
Tue Feb 26 02:16:35 2019 length 1 : 20669
Tue Feb 26 02:16:35 2019 length 2 : 14862
Tue Feb 26 02:16:35 2019 length 3 : 14475
Tue Feb 26 02:16:35 2019 length 4 : 11726
Tue Feb 26 02:16:35 2019 length 5 : 9005
Tue Feb 26 02:16:35 2019 length 6 : 6099
Tue Feb 26 02:16:35 2019 length 7 : 3974
Tue Feb 26 02:16:35 2019 length 9+: 5634
Tue Feb 26 02:16:35 2019largest cycle: 20 relations
Tue Feb 26 02:16:36 2019matrix is 85882 x 86444 (25.0 MB) with weight 5849567 (67.67/col)
Tue Feb 26 02:16:36 2019sparse part has weight 5849567 (67.67/col)
Tue Feb 26 02:16:37 2019filtering completed in 3 passes
Tue Feb 26 02:16:37 2019matrix is 82107 x 82171 (23.7 MB) with weight 5554996 (67.60/col)
Tue Feb 26 02:16:37 2019sparse part has weight 5554996 (67.60/col)
Tue Feb 26 02:16:37 2019saving the first 48 matrix rows for later
Tue Feb 26 02:16:37 2019matrix includes 64 packed rows
Tue Feb 26 02:16:37 2019matrix is 82059 x 82171 (15.6 MB) with weight 4447022 (54.12/col)
Tue Feb 26 02:16:37 2019sparse part has weight 3255824 (39.62/col)
Tue Feb 26 02:16:37 2019using block size 8192 and superblock size 884736 for processor cache size 9216 kB
Tue Feb 26 02:16:38 2019commencing Lanczos iteration
Tue Feb 26 02:16:38 2019memory use: 9.9 MB
Tue Feb 26 02:16:57 2019linear algebra at 58.6%, ETA 0h 0m
Tue Feb 26 02:17:09 2019lanczos halted after 1299 iterations (dim = 82057)
Tue Feb 26 02:17:09 2019recovered 16 nontrivial dependencies
Tue Feb 26 02:17:10 2019p42 factor: 179951404407700053508335546465851287509301
Tue Feb 26 02:17:10 2019p56 factor: 10364229601007831878377902195192125938721193826116042587
Tue Feb 26 02:17:10 2019elapsed time 04:36:00
.·.·. 发表于 2019-2-25 21:29
found factor = 877450288288670004098523859
pari/GP已经尽力了
剩下的工作很快就能完成
有个软件叫GMP-ECM可惜要在Linux上玩，估计应该是ECM界最先进的分解整数的办法了！
但是我不会Linux mathematica 发表于 2019-2-26 08:56
有个软件叫GMP-ECM可惜要在Linux上玩，估计应该是ECM界最先进的分解整数的办法了！
但是我不会Linux
pari/gp自带一个ECM，可以用来过滤小因子
你开\g4之后仔细看日志就好
然后，ecm速度不如qs速度快
本来想尝试nfs的，结果被坑得很惨很惨……
看上去我还需要仔细研究一下nfs究竟是个什么鬼才好
页:
[1]
2