Blog List View

素性测试新算法 

2018-06-26 16:51:50
693 次阅读

三条件的素性测试新算法:

Ln = ((1+√5)/2)^n+((1 - √5)/2)^n
    = 1,3,4,7,11,18,29,47,......

Cn = [(1+√2)^n+(1 - √2)^n]/2
    = 1,3,7,17,41,99,239,577,......

若 2^(n-1)  mod  n = 1,
且 Ln   mod   n = 1,
且 Cn   mod   n = 1,
则 n 一定是素数。


编程验证
s = 1;
For[n = 1, n <= 1000000, n++, 
If[(Mod[2^(n - 1), n] == 1) 
&& (Mod[Round[((1+√5)/2)^n + ((1 - √5)/2)^n], n] == 1) 
&& (Mod[Round[((1+√2)^n + (1 - √2)^n)/2],n] == 1), s = s + 1;
  Print[s, "-----", n, "-----", PrimeQ[n]]]]

发表评论