Skip to content

Files

Latest commit

3db51e5 · Nov 30, 2018

History

History

Miller-Rabin Primality Test

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Nov 13, 2018
Nov 30, 2018
Nov 30, 2018

Miller-Rabin Primality Test

Miller-Rabin素性检测

In 1976, Gray Miller introduced an algorithm, through his ph.d thesis1, which determines a primality of the given number. The original algorithm was deterministic under the Extended Reimann Hypothesis, which is yet to be proven. After four years, Michael O. Rabin improved the algorithm2 by using probabilistic approach and it no longer assumes the unproven hypothesis.

1976年,格雷米勒通过他的博士论文1介绍了一种算法,它确定了给定数字的素数。 原始算法在扩展Reimann假设下是确定性的,尚未得到证实。 四年后,Michael O. Rabin通过使用概率方法改进了算法2,并且不再假设未经证实的假设。

Probabilistic

概率

The result of the test is simply a boolean. However, true does not implicate the number is prime. In fact, it means the number is probably prime. But false does mean the number is composite.
测试结果只是一个布尔值。 但是,true并不意味着 the number is prime 。 事实上,这意味着 the number is probably prime。 但是false的意思是 the number is composite

In order to increase the accuracy of the test, it needs to be iterated few times. If it returns true in every single iteration, then we can say with confidence that the number is pro......bably prime.
为了提高测试的准确性,需要迭代几次。 如果它在每一次迭代中都返回true,那么我们可以自信地说 the number is pro......bably prime

Algorithm

算法

Let n be the given number, and write n-1 as 2^s·d, where d is odd. And choose a random number a within the range from 2 to n - 1.
n为给定数字,并将n-1写为2^s·d,其中d为奇数。 并选择从2n - 1范围内的随机数a

Now make a sequence, in modulo n, as following:
现在以模n形式创建一个序列,如下所示:

a^d, a^(2·d), a^(4·d), ... , a^((2^(s-1))·d), a^((2^s)·d) = a^(n-1)

And we say the number n passes the test, probably prime, if 1) a^d is congruence to 1 in modulo n, or 2) a^((2^k)·d) is congruence to -1 for some k = 1, 2, ..., s-1.
并且我们说数字n通过测试, probably prime ,如果1)a^d与modulon中的1是一致的,或2)a^((2^k)·d) 对于某些 k = 1, 2, ..., s-1,与-1是一致的。

Pseudo Code

伪代码

The following pseudo code is excerpted from Wikipedia3:
以下伪代码摘自维基百科3

Image of Pseudocode

Usage

使用

mrPrimalityTest(7)                      // test if 7 is prime. (default iteration = 1)
mrPrimalityTest(7, iteration: 10)       // test if 7 is prime && iterate 10 times.

Reference

参考

  1. G. L. Miller, "Riemann's Hypothesis and Tests for Primality". J. Comput. System Sci. 13 (1976), 300-317.
  2. M. O. Rabin, "Probabilistic algorithm for testing primality". Journal of Number Theory. 12 (1980), 128-138.
  3. Miller–Rabin primality test - Wikipedia, the free encyclopedia

Written for Swift Algorithm Club by Sahn Cha, @scha00

作者:Sahn Cha*
翻译:Andy Ron