[数论]Miller-Rabin素性测试

如果给出一个正奇数 n,要判断它是不是素数,有一个最简单暴力的方法,就是从 2 开始一直试到 \sqrt n,这样的话能保证结果绝对正确,但是,时间复杂度也就是 \Theta (\sqrt n),当 n 的规模到达 10^{30} 甚至更高的级别的时候,就不能在可以忍受的时间内看到结果了。尤其是构造 RSA 密码体制时所需要用到的,找一个极大的素数。

那么,有没有一个比较快的方法来判断一个数是不是素数呢?

(more…)

Read More