math/MillerRabin.h

• View this file on GitHub
• Last update: 2025-11-18 17:42:34+07:00

Required by

• math/Factor.h

Verified with

• tests/Factorize.test.cpp
• tests/Primality_Test.test.cpp
• tests/Primitive_Root.test.cpp

Code

bool isPrime(u64 n) {
  if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  u64 A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
      s = __builtin_ctzll(n - 1), d = n >> s;
  for (u64 a : A) {  // ^ count trailing zeroes
    u64 p = modpow(a % n, d, n), i = s;
    while (p != 1 && p != n - 1 && a % n && i--) p = modmul(p, p, n);
    if (p != n - 1 && i != s) return 0;
  }
  return 1;
}

#line 1 "math/MillerRabin.h"
bool isPrime(u64 n) {
  if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
  u64 A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
      s = __builtin_ctzll(n - 1), d = n >> s;
  for (u64 a : A) {  // ^ count trailing zeroes
    u64 p = modpow(a % n, d, n), i = s;
    while (p != 1 && p != n - 1 && a % n && i--) p = modmul(p, p, n);
    if (p != n - 1 && i != s) return 0;
  }
  return 1;
}

Back to top page