2011年7月27日星期三

Is prime?

若要知一個數p是否prime number,有何方法呢?Factorization? 可以,但若p很大(即過百digit),即使由2開始嘗試factor到p平方,也需要很長時間。若只需知是否prime,可以試試它有沒有prime的性質。

根據Fermat's little theorem
a p - 1 1 mod p
只要p是prime便一定餘1,但餘1的未必一定是prime,如561等Carmichael number。不等如1就一定是composite。於是有人發明Miller-Rabin primality test。這test雖叫primality,實際上是composite test,即是它可以肯定test number p是composite,而沒有composite特性,很大機會是prime。

若p是odd prime,p-1是even,然後ap-1餘1,那麼a(p-1)/2的餘數是什麼?1的square root,只可能是±1(p是prime,a和p coprime),p - 1可以表示成2de,e是odd number,那麼,ae餘±1便有可能是prime,可以找下一個a試試。若不是,可以繼續square試,試到2d-1也不是±1,那肯定是composite了。

以下這個function,一開始先mod 6,篩走餘數0, 2, 3, 4,便可以篩走2/3機會的數,之後才對餘數1和5進行composite test。

這function部份根據Wikipedia的pseudocode寫,應用了Modular exponentiation,但和Extended Euclidean algorithm沒有直接關係,因為這篇文章也是材料之一,為另一文章作準備,但至今材料尚欠一項,毫無頭緒,煩惱中...

沒有留言:

發佈留言