nutella2007's blog

Fast primality test wanted
By nutella2007, history, 5 weeks ago, In English

Hello. Does anyone know any (non-pseudo) primality tests with complexity better than O(√n)? The thing is, I was reading about a simple one that has O(∛n) or O(∜n) complexity, but now I just can't find it! I remember that the core idea was checking some divisors (not up to square root) and then analyzing cases of prime decomposition. Thank you.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Miller–Rabin primality test is the fastest algorithm, but it is not deterministic. You need to run the test multiple times to reduce the failure probability.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    For relatively small $$$n$$$, you can use a deterministic version of the Miller-Rabin test, which is the fastest. From the Wikipedia page:

    if n < 3,317,044,064,679,887,385,961,981, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.

    This should be enough for all practical purposes, and it has time complexity $$$O(k*log^3(n))$$$, where $$$k$$$ is the number of primes tested, 13 in this case.

    Additionally, there is the Pollard-Rho algorithm, which works in $$$O(n^{\frac{1}{4}})$$$ on average.

    → Reply