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, a 2=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, a 2=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(pi+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 是單一理論,很清楚告訴我們一個數是質數或合數的原因。

我以Eratosthenesg篩選法篩選3到10^10-1的奇數檢驗GQQ質數檢驗法,全部通過。質數是質數,合數是合數。

當然, 你會像我一樣想這特別數列能否用來因數分解。令人失望,我從2003年開始研究因數分解,在2013年11月發現這數列,半年後我發現了 GQQ Primality Test. 但又三年半過去了,我仍然找不到用這特別數列來因數分解的方法。

在這裡要說聲抱歉的,是我目前不會談 GQQ Primality Test的細節,但是我會為你檢測你輸入的數字。

這檢測是免費的,如 GQQ Primality Test 所檢測的數字是質數/合數,你發現卻是合數/質數時,如你是第一個發現這數字,且驗證碼和這系統產生的驗證碼一樣時,我會給你100美元獎金。

一個GQQ質數篩選 (數字區間) 不久之後可供使用。

Chair Zhuang 寫於2017/10/07。