費馬檢驗

程式更新日期: 2010年1月27日

網友 roviury 提供簡化程式意見。

程式使用費馬檢驗方法檢查一個數是否質數。若檢測 n是否質數及a為正整數,程式會計算 an-1 mod n 的數值 ,如果答案不是1表示 n為合成數,相反若果是1則不能證明是合成數,請繼續嘗試不同的A值,若果經過多次測試都無法證明是合成數,那麼檢測的數值 n 是偽質數的機會會很低。

 

程式 (92 bytes,使用記憶為A、B、C及M)

?→B: 1→C: While C=1: B - 1: ?→A: Fix 0:

Lbl 0: . 5 Ans→M: A - BRnd( A ÷ B - . 5→A:

M-Rnd( M => . 5M- => (AC≠0)(AC - BRnd( AC ÷ B - Ans→C:

A2→A: M => Goto 0: Norm 1: C◢ WhileEnd

 

例題1: 試用費馬檢驗方法,檢測 3127 是否質數。

按 Prog 1 再按 3127 EXE (輸入檢查的數值) 2 EXE (嘗試A=2進行檢測,顯示2608)

再按 EXE (顯示0及程式終止表示3127為合成數)

 

例題2: 試用費馬檢驗方法,檢測 561 是否質數。

按 Prog 1 再按 561 EXE (輸入檢查的數值) 2 EXE (嘗試A=2進行檢測,顯示1)

再按 EXE 3 EXE (嘗試A=3進行檢測,顯示375)

再按 EXE (顯示0及程式終止表示561為合成數)

 

註: 費馬小定理: 若n為質數,則對所有與n互質的數a,an-1≡1 (mod n)

參考資料:

http://en.wikipedia.org/wiki/Fermat_primality_test

http://en.wikipedia.org/wiki/Carmichael_number

 

返回 CASIO fx-50FH、fx-3650P II、fx-50FH II及fx-50F PLUS 程式集

Free Web Hosting