米勒-拉宾检验

米勒-拉宾检验

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

eq 1</math> 且 <math>a^{2^{rd}} mod N

eq -1</math>，则 N 是合数。否则，<math>N</math> 有 <math>3/4</math> 的机率为质数。