CoCoA » CoCoALib

Several CRT loops look a lot like this:

  while (true)
  {
    p = NextPrime(p);
    ModP = SmallFpImpl(p);
    // do computation mod p
  }

The point is that both NextPrime and SmallFpImpl check that the number is prime, and this is quite costly (when the number actually is prime).

So maybe there should be a ctor SmallFpImpl(p, NoCheck) which says not to check that arg is prime (woe betide those who lie!)

Another posibility is for a "prime source" to produce values of a new type SmallPrime (which is really just a long, but with the guarantee that its arg is prime). Then there could be ctor for SmallFpImpl which accepts a SmallPrime, and knows that it does not need to check primality!