CoCoA » CoCoALib

Add a new class to CoCoALib for generating primes in succession -- for use inside CRT loops.

Currently a CRT loop looks like this:

  long p;
  while (true)
  {
    p = NextPrime(p);
    SmallFpImpl ModP(p);
    // computation modulo p
  }

NextPrime simply increments its arg (in a "clever" way) and then calls IsPrime (or IsSmallPrime), and keeps going until IsPrime produces true.

However it is known that Eratothenes's Sieve is a quick way of generating a table of primes over a given range, so it may be a good idea to have a PrimeSource object which generates an internal table, then uses that.

So the loop could look like this:

  PrimeSource PS(1000000);  // arg is start value
  while (true)
  {
     long p = NextPrime(PS);
     SmallFpImpl ModP(p, NoCheck);
     // do computation mod p
  }