probablyPrimeMillerRabin method

bool probablyPrimeMillerRabin(int reps, { bool force2 = true, })

Implementation

bool probablyPrimeMillerRabin(int reps, {bool force2 = true}) {
  final nMinus1 = this - BigInt.one;
  final k = nMinus1.trailingZeroBits;
  final q = nMinus1 >> k;

  // Used to generate a, so that a is greater than 2
  final nMinus3 = this - BigInt.two;
  final nMinus3BitLength = nMinus3.bitLength;

  nextRep:
  for (int rep = 0; rep < reps; rep++) {
    var a = randomBigInt(nMinus3BitLength, max: nMinus3) + BigInt.two;
    var modulo = a.modPow(q, this);

    if (modulo == BigInt.one || modulo == nMinus1) continue nextRep;

    for (int j = 1; j < k; j++) {
      modulo *= modulo;
      modulo = modulo % this;

      if (modulo == nMinus1) {
        continue nextRep;
      }
      if (modulo == BigInt.one) {
        return false;
      }
    }

    return false;
  }

  return true;
}