isProbablyPrime property

bool isProbablyPrime

Tests if this BigInt is probably a prime.

This variant of the probabilistic prime test by Miller–Rabin is deterministic. It has been verified to return correct results for 64 bit integers.

Implementation

bool get isProbablyPrime {
  if (this <= _bases.last) {
    return _bases.contains(this);
  }
  for (final base in _bases) {
    if (this % base == BigInt.zero) {
      return false;
    }
  }
  var d = this - BigInt.one, s = 0;
  while (d.isEven) {
    d ~/= BigInt.two;
    s++;
  }
  loop:
  for (final base in _bases) {
    var x = base.modPow(d, this);
    if (x == BigInt.one || x == this - BigInt.one) {
      continue loop;
    }
    for (var r = 1; r < s; r++) {
      x = x.modPow(BigInt.two, this);
      if (x == BigInt.one) {
        return false;
      }
      if (x == this - BigInt.one) {
        continue loop;
      }
    }
    return false;
  }
  return true;
}