米勒-拉賓檢驗
程式編寫日期: 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: D2→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可能為質數)
參考資料:
http://planetmath.org/encyclopedia/MillerRabinPrimeTest.html
http://en.wikipedia.org/wiki/Miller-Rabin_primality_test