米勒-拉賓檢驗

程式編寫日期: 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

 

 

 

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

Free Web Hosting