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;
}