米勒-拉賓檢驗

米勒-拉賓檢驗

程式編寫日期: 2008年3月19日

程式 (173 bytes)

ClrMemory: ?→B: B-1→Y: ?→A: Fix0:

Lbl 0: Y=2Rnd( Y÷2 - . 5 => X + 1→X: Ans => Y÷2→Y:

Ans => Goto 0: Lbl 1: 1→C: X - 1→X: 0>X => Goto 4:

2^( X )Y→M: A→D: Lbl 2: D - BRnd( D ÷ B - . 5→D:

M ÷ 2→M: M=Rnd( Ans => Goto 3: DC => Rnd( DC ÷ B - . 5:

DC - BAns→C: . 5M-: Lbl 3: D²→D: M => Goto 2:

C≠B^(X≠0 => C ≠ B - 1 => Goto 1: Lbl 4: Norm 1

例題1: 試用米勒-拉賓檢驗，檢測 3127 是否質數。

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

例題2: 試用米勒-拉賓檢驗，檢測 37 是否質數。

按 Prog 1 再按 37 EXE (輸入檢查的數值) 2 EXE (嘗試A=2進行檢測，顯示0表示37可能為質數)

參考資料: