1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机算法（有较小的可能性错误），用于判断一个大数是否是素数。快速素数检验是目前大部分公钥密码体系的关键。

米勒-拉宾检验的内容是:要测试 N 是否为质数，首先将N-1 分解为 2^s d。在每次测试开始时，先随机选一个 介于[1, n-1的整数a，之后如果对所有的r in [0, s-1]，若a^d mod N <> 1 且 a^{2^{rd}} mod N <> -1，则 N 是合数。否则，N 有3/4 的机率为质数。