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