米勒-拉宾检验

维库，知识与思想的自由文库

要測試 $N$ 是否為質數，首先將 $N - 1$ 分解為 $2 s d$ 。在每次測試開始時，先隨機選一個介於 $[1, n - 1]$ 的整數 $a$ ，之後如果對所有的 $r \in [0, s-1]$ ，若 $a^d \mod N \neq 1$ 且 $a^{2^{rd}} \mod N \neq -1$ ，則 N 是合數。否則， $N$ 有 $3 / 4$ 的機率為質數。

来自“http://9d.movieclub.com.cn/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C”

个人工具

米勒-拉宾检验

维库，知识与思想的自由文库

查看

导航

搜索

工具

其它语言

AD Links