費馬檢驗

費馬檢驗

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

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

程式使用費馬檢驗方法檢查一個數是否質數。若檢測 n是否質數及a為正整數，程式會計算 a^n-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:

A²→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，a^n-1≡1 (mod n)

參考資料: