isProbablyPrime property

bool isProbablyPrime

Tests if this int 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 == 0) {
      return false;
    }
  }
  var d = this - 1, s = 0;
  while (d.isEven) {
    d ~/= 2;
    s++;
  }
  loop:
  for (final base in _bases) {
    var x = base.modPow(d, this);
    if (x == 1 || x == this - 1) {
      continue loop;
    }
    for (var r = 1; r < s; r++) {
      x = x.modPow(2, this);
      if (x == 1) {
        return false;
      }
      if (x == this - 1) {
        continue loop;
      }
    }
    return false;
  }
  return true;
}