米勒-拉賓檢驗

米勒-拉賓檢驗

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

程式 (176 bytes)

Mem clear: ?→B: B-1→Y: ?→A: Fix0:

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

Lbl 1: 1→C: X - 1→X: 0>X => Goto 4: 2^XY→M: A→D: Lbl 2:

D ÷ B - . 5: Rnd: D - BAns→D: M ÷ 2→M: Rnd:

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

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可能為質數)

參考資料: