用mathematica写的miller rabin算法 - 第2页 - 算法交流 - 数学研发论坛

mathematica 发表于 2019-1-26 12:11:47

本帖最后由 mathematica 于 2019-1-26 12:13 编辑

mathematica 发表于 2008-11-30 18:47
上面的那个数是一个素数。这个例子给出一个强伪素数，它是前46个素数
的强伪素数。可以看出，最后的结果判 ...

观察下面的结果
{2,1,-1,prime}
{3,0,-1,prime}
{4,0,-1,prime}
{5,0,1,prime}
{6,1,-1,prime}
{7,1,-1,prime}
{8,1,-1,prime}
{9,0,1,prime}
{10,1,-1,prime}
{11,1,-1,prime}
{12,0,1,prime}
{13,1,-1,prime}
{14,composite}
提取
{2,1,-1,prime}
{7,1,-1,prime}
这个意味着
\(x^2\equiv-1\pmod{n}\)
\(y^2\equiv-1\pmod{n}\)
那么
\((x*y)^2\equiv1^2\pmod{n}\)
并且x与y互质,
所以可以利用这个同余等式来分解质因数
分别计算
x*y-1与n的最大公约数
x*y+1与n的最大公约数
然后就能得到质因子
4009582166394996054183064520845468530051881660411325087745062047380032\
1707011962427162231915972197335821631650853581669691452338139171692875\
27980445796800452592031836601

代码如下:
Clear["Global`*"];(*Clear all variables*)
n=803837457453639491257079614341942108138837688287558145837488917522\
2974273765333652186502336163960045457915042023603208766569966760987284\
0439654082329287387918508691668573282677617710293896977394701670823042\
8687109997439976544144845341155872450633409279022275296229414984230688\
1685404326457534018329786111298960644845216191652872597534901;
m=n-1;s=0;
While==0,m=m/2;s=s+1];
kk=PowerMod
ga=GCD

mathematica 发表于 2019-2-24 09:33:56

Clear["Global`*"];
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]
]

这是我重新写的miller rabin算法的代码,又简化了!

mathematica 发表于 2019-2-24 13:58:54

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}

mathematica 发表于 2019-2-24 14:07:09

https://bbs.emath.ac.cn/forum.php?mod=viewthread&tid=15734&fromuid=865
用此处的lucas判定办法,就回得到false的答案!

nyy 发表于 2022-9-19 14:21:20

好地方发表于 2008-11-30 20:31
这个伪素数够强，不过越强的伪素数其实越脆弱，略施小计，只需一眨眼的时间就将它分解为下面两个素数的乘积 ...

能说说你是怎么分解的吗？我需要的是方法

页: 1 [2]

数学研发论坛's Archiver