English 繁中
lizhuanggarden.comsince 2017-10-7
当这些绿色字消失时, GQQ Primality Test就开始发放奖金。
一个快速又确定的素数检验法。
时间复杂度:O(ln n)2.
语意有所不清时,以繁体中文为準.

这素数检验法以我母亲张闺秀和我两个哥哥奇福和庆治名字命名。

这程式每天检测10,000个数字,世界标准时间隔天上午2:00可开始查各数字素性。每天以世界标准时间下午2:00做为一天的开始。

受我电脑和程式的限制,所输入的数字必须是自然数(包括0),且在10进位3010位(210000)以下,受测数字型态的运算子包括 " + - * ^ ( 和 )",不含 " / "。。
***************************************受测数字:
***********先前你取得做为查询素性的流水号:
********************************************留言:
*********************************************************

GQQ Primality Test 是一个基于特别数列所形成的确定性素数检测演算法。这个特别数列含盖fermat数列、Lucas数列及更多的其他数列 。如Lucas数列称为Lucas数列,那这特别数列就以我哥哥的名子命名为奇福数列。对受测数字仅给予一个非随机性而是从受测数计算出来的关键性数字, GQQ Primality Test 就能判别出这受测数字的素性。

在 Fermat Primality Test 里, 假使 ap − 1 ≡ 1 (mod p),那么模数 p 是一个可能素数。例如: 从 27 − 1 ≡ 1 (mod 7) 和 391 − 1 ≡ 1 (mod 91)中, 我们知道 7 是素数但91不是。但是在 GQQ Primality Test里, 检验值是一个平方根。例如: (f(k)n)2 ≡ 2 (mod 7), 这里 f(k)n 的意思是在GQQ Primality Test奇福数列里第n项的值,而 n = (7 + 1) ∕ 2。 注意:在 Fermat Primality Test里, 我们取这数列第p − 1的值, 而在 GQQ Primality Test里, 我们取奇福数列第 (p+1)/2项的值。一个是 " - " 而另一个是 " + "。 在GQQ Primality Test里,就如在Fermat Primality Test的a, 假使这个a不是1,第(p+1)/2项的值不会是1 or p-1,所以我们不会把一个合数误当为素数。事实上, Fermat Primality Test的数列仅是奇福数列的一个特殊情形。

在miller-Rabin Primality Test里,检验第(p-1)/2r项的值,这和Fermat Primality Test有相同的问题。

在Fermat检验里,当已知n=p1*p2*····*pi,n-1被LCM(f(p1-1),f(p2-1),····*f(pi-1))整除时,(f(p1-1)指p1-1的任一因数,其相对应的基数为a1。其它亦同),就有伪证a使an-1≡ 1 (mod n)成立。 a可用中国余数定理求得。这种检验法,不管n为单因数(即n为素数)或多因数(即合数)ap − 1 ≡ 1 (mod p)都成立。

例如:n=11*23。取f(11-1)=2,a1=10, f(23-1)=1, a2=1. LCM(2,1)=2, n-1=253-1=252, and 252≡ 0 (mod 2). 伪证a=208 用中国余数定理求得。从这个例子, GCD((11-1)/2,(23-1)/2)=1, 我们发现一个事实,就是含有2个素因数的每个合数都有它的伪证。另一个例子: n=11*23*29=7337. 取f(11-1)=1, a1=1, f(23-1)=1, a2=1 and f(29-1)=7, a3=16. LCM(1,1,7)=7, n-1=7337-1=7336, and 7336≡ 0 (mod 7). 伪证a=2278 用中国余数定理求得。注意: 11*23=36*7+1而29=4*7+1, 所以(11*23)*29-1=7*k. 现在我们可说,对决定一个数的素性来说Fermat Primality Test 是一个无效的演算法. 它的决定只是运气,对大部份的数字来说是一个很棒的运气.

从上述知道的伪证求法来看miller-Rabin Primality Test。要符合ad≡1 (mod n),取各个f(pi-1)为奇因数,若这些奇因数的最小公倍数整除n-1,那由其相对应的ai以中国余数定理求得伪证a。要符合a2rd≡-1 (mod n),取适当的ai使aif(pi-1)≡-1 (mod n),这里每一个素因数的f(pi-1)要相同。若f(pi-1)整除n-1,求算a即得伪证。

当然,在GQQ Primality Test也要考虑这情形。由上述伪证的由来来看GQQ Primality Test,因GQQ Primality Test取奇福数列第p+1项的值来检验,所以没有Fermat伪素数或miller-Rabin伪质数的问题。有兴趣者自行证明,在此不赘述。这里所要谈的是有否GQQ伪质数。因GQQ Primality Test的奇福数列和a是经过计算而非随机性(关键数须小于n的平方根)而来,当n+1被f(p< sub>i+1)的最小公倍数整除时,第(n+1)/2项的值并非我们所想的值,而是因为n为合数有二个以上的素因数,所以为一另可用中国余数定理求得的值。当基数a小于n的平方根时,此值与n呈线性关系,不若n为质数时,不论n的大小,都会等于所要的且不会改变的平方根,所以只要基数a小于平方根和大于1就没有伪素数的问题。

GQQ Primality Test是結合Fermat Primality Test和AKS Primality Test嗎?我們可用Carmichael number和其它數字來測試。GQQ Primality Test的时间复杂度是O(ln n)2。 以我Core i5-2400 (3.10 GHz)的个人电脑检验梅森素数(Mersenne prime number) 24253 − 1, 不计输出入时间,仅耗用 0.21556 秒。但是 AKS Primality Test 的时间复杂度最少是 O(log (n))6。当耗用极少时间测试大的Carmichael number并且说是合数时,我们可说GQQ Primality Test是一个快速又确定的素性检验法吗?

Baillie-PSW Primality Test 以基数为2的强Fermatle probable prime test 结合 Lucas probable prime test。但是,为什么结合二个理论? 其他的素性检验法以Fermat Primality Test 或Miller-Rabin Primality Test 结合Lucase Sequence or Fibonacci Test. 但是,为什么? GQQ Primality Test 是单一理论,很清楚告诉我们一个数是素数或合数的原因。

我以Eratosthenes筛选法筛选3到10^10-1的奇数检验GQQ素性检验法,全部通过。素数是素数,合数是合数。

当然, 你会像我一样想这奇福数列能否用来因数分解。令人失望,我从2003年开始研究因数分解,在2013年11月发现这数列,半年后我发现了GQQ Primality Test. 但又三年半过去了,我仍然找不到用这奇福数列来因数分解的方法。

在这里要说声抱歉的,是我目前不会谈 GQQ Primality Test的细节,但是我会为你检测你输入的数字。

这检测是免费的,如GQQ Primality Test 所检测的数字是素数/合数,你发现却是合数/素数时,如你是第一个发现这数字,且验证码和这系统产生的验证码一样时,我会给你100美元奖金。

一个GQQ素数筛选 (数字区间) 不久之后可供使用。

Chair Zhuang 写于2017/10/07。