米勒罗宾（Miller Rabin）素数检验
给定一个正整数，如何快速的判定它是否是个素数是个经典问题。传统的方法就是试除法和筛法，这些方法对于较小的素数（如一百万以内）判定比较实用，但是对于更大的正整数却显得力不从心。好在人类的智慧是无穷尽的，总会找到更快的办法，米勒罗宾素数检验一个更快的方法。米勒罗宾素数检验顾名思义，米勒和罗宾是两个人，米勒罗宾素数检验算法其实是两个算法，米勒检验是素数检验，罗宾定理是概率性检验。但是在用作素数检验的时候这两个算法一般被合在一起，因此不做区分。这个算法的主要难点在米勒检验，在介绍米勒检验之前，需要一点预备知识，先介绍一下费马小定理。费马小定理如果p是素数，对于任意正整数a，则有$$a^p \equiv a \pmod p$$。 特别的，如果p是素数，而且a和p互素，则可以从等式两边同时除以a，有\(a^{p-1} \equiv 1 \pmod p\)。 但是，费马小定理的逆命题并不成立，也就是说，对于互素的正整数a和p，如果有\(a^{p-1} \equiv 1 \pmod p\)，则p不一定是素数。 例如，341就是让费马小定理逆命题不成立的最好例子，对于a=2，p=341，有\(2^...
米勒罗宾（Miller Rabin）素数检验
给定一个正整数，如何快速的判定它是否是个素数是个经典问题。传统的方法就是试除法和筛法，这些方法对于较小的素数（如一百万以内）判定比较实用，但是对于更大的正整数却显得力不从心。好在人类的智慧是无穷尽的，总会找到更快的办法，米勒罗宾素数检验一个更快的方法。米勒罗宾素数检验顾名思义，米勒和罗宾是两个人，米勒罗宾素数检验算法其实是两个算法，米勒检验是素数检验，罗宾定理是概率性检验。但是在用作素数检验的时候这两个算法一般被合在一起，因此不做区分。这个算法的主要难点在米勒检验，在介绍米勒检验之前，需要一点预备知识，先介绍一下费马小定理。费马小定理如果p是素数，对于任意正整数a，则有$$a^p \equiv a \pmod p$$。 特别的，如果p是素数，而且a和p互素，则可以从等式两边同时除以a，有\(a^{p-1} \equiv 1 \pmod p\)。 但是，费马小定理的逆命题并不成立，也就是说，对于互素的正整数a和p，如果有\(a^{p-1} \equiv 1 \pmod p\)，则p不一定是素数。 例如，341就是让费马小定理逆命题不成立的最好例子，对于a=2，p=341，有\(2^...
