APRTest

Files CCore/inc/math/APRTest.h CCore/src/math/APRTest.cpp

APRTest is a primality test (stands for Adelman-Pomerance-Rumely). It can determine for the given Integer is it prime or not. The all related software entities are enclosed in the namespace APRTest.

namespace APRTest {

/* enum TestResult */

enum TestResult
 {
  IsPrime = 0,
  
  NoPrime,
  HasDivisor,
  HardCase,
  TooLarge
 };

const char * GetTextDesc(TestResult res);

....

template <class Integer>
class TestEngine : NoCopy
 {
  public:

   TestEngine();
   
   ~TestEngine() {}
   
   template <class Report>
   TestResult operator () (Integer N,Report &report) const;
 };

} // namespace APRTest

To run the test you need a TestEngine object. The template parameter is an Integer class. This test can work with numbers below the cap equals

2344337676639901536537009401439404459102294287774013395319053152263858791495945836639889196503326005
9520088483759129991798707943484180793270736534582280513971100947583455853098329737899837958507744735
4683335120251519658249534398302901895877463628834707798772705852582450272480141515494120589894234211
2361568705229747177644785121702633492129409249902062718254593393467922576395445572789668065684906542
1801923236420777680300140870378859146308344835679285297560117712475682763611135113880013934844035430
7607166673168224204210193260243671452637764519001279467104727735157233629375614278099574889925182461
0783877131172698572041426393287052042434045479373798332352076819889705650982210275578842687690491587
5455885964664044686141124161779448938428504837377473247745615609037377118071051335319446866702358636
9662285645762015852544317953658074850730715239817586046929514135055358855148722799736454249812675981
2417046521705659662042123068991437529465635512326652330046906357173897897125887967884716841651949482
5019447667108736352236292460528034458480842646277646148655349875167265104873502522379778566006795244
6270665261377787844134075732390500690020179267915760301612737751839386483112656160271521314112605823
3848792488795326134373148850736324312919886997218561456600960347910963445599213966660176604365445039
9694577896052051888073932043997306437670601959738752480561143205077181422382972642902321333791234058
0460354380741424755549264802253245352841717268600146619850089549120758178003237501181610762160661025
0675027386707007781142168530846576081212867139662696695047672572359662200294496457367209474048326740
5423849061004318678239699030541058123140966728010722658659745107230286811969277892072040348188630207
0655779146178297533320554790910730326106451845257463507561272899421287549624400560723516533571191462
1609165286318453807291146422169704392586520387701891425544357472300429578010581103545069432635783020
1957349944479360350486458460580640215470462880417740684142948484334489570630940249785222564343666957
1161068235554293464199193396919617491789783935442503388374670609662331164193236937025615869841579305
7738914993648444975579245608653237989267513937095546850031712547589411981327192126225542098643729904
3857522705822300391521134516260861112229668835120905248115729261261736226883766430044275044174340814
5277304794378446693660154409387317501654237034229164329991564186121601002665397164207819724465172173
2419657166613957388502145410053007166620802836547034262579320675600648865858127949014420092818949480
6595991444657908030060891182914349261724317431250502860784799046163961947905818150287118990151388987
9013386419142421937354738116723734914275284977023269383764783207411817508810730360702421562219606245
0785284458052516

This number has 9021 bit length. So numbers with 9020 bit length or less can be tested.

To test the given Integer use the operator (). The first argument is the number to be tested. The second is the reference to a report object. There is a default silent Report class:

class NoReport
 {
  public:
   
   NoReport() {}
  
   template <class Integer>
   void start(const Integer &N) { Used(N); }
   
   void sanity(const char *msg) { Used(msg); }
   
   void isSmallPrime() {}
   
   void testP(unsigned prime_p) { Used(prime_p); }
   
   void testQ(QType prime_q) { Used(prime_q); }
   
   template <class Integer>
   void cappa(PtrLen<const Integer> cappa,const Integer &Nminus1) { Used(cappa); Used(Nminus1); }
   
   template <class Integer>
   void cappa2(const Integer &cappa,const Integer &Nminus1) { Used(cappa); Used(Nminus1); }
   
   void startProbe() {}
   
   template <class Integer>
   void probe(const Integer &cnt) { Used(cnt); }
   
   template <class Integer>
   void div(const Integer &D) { Used(D); }
   
   void hard() {}
   
   void isPrime() {}
   
   void noPrime() {}
 };

Any report class must have the same interface.

A test result is returned as the value of the enumeration TestResult.

IsPrime equals 0 means the number is prime.

NoPrime means the number is no prime.

HasDivisor means the number is no prime and some divisor can be presented.

HardCase means the test was unable to determine the primality of the given number. This is a very rare case.

TooLarge means the number is above the test cap.

Report methods are called to indicate some stages of the test.

start() is called at the start of the test. The argument is the number to be tested.

sanity() is called if some sanity checks are failed. The argument is the text description of the situation.

isSmallPrime() is called if the number been tested is a small prime.

testP() is called at the beginning of a series of subtests. The argument is a small prime number p.

testQ() is called at the beginning of a subtest. The argument is a small prime number q. The couple (p,q) is the subtest index.

startProbe() is called at the beginning of the searching divisors.

probe() is called during the searching divisors. The argument is the remaining possible divisor count.

div() is called if some divisor has been found. The argument is that divisor.

hard() is called if it is the hard case.

isPrime() is called if the number been tested is prime.

noPrime() is called if the number been tested is not prime.

There is a faster parallel variant of this test.

template <class Integer,template <class T,class F=GetNoThrowFlags<T> > class ArrayAlgo>
class ParaTestEngine : NoCopy
 {
  public:
 
   ParaTestEngine();
   
   ~ParaTestEngine() {}
   
   template <class Report>
   TestResult operator () (Integer N,Report &report) const;
 };

This variant is working fatser on multi-core systems. To achieve a greater efficiency you have to use TaskHeap. Here is an example of the proper usage:

using ParaInt = Math::Integer<Math::IntegerFastAlgo,RefArray,TaskHeapArrayAlgo> ;

using ParaTestEngine = Math::APRTest::ParaTestEngine<ParaInt,TaskHeapArrayAlgo> ;

....

  Job::Init init;
  TaskHeap task_heap;

....

  ParaTestEngine test;

  Math::APRTest::TestResult result;

  ParaInt N=....;
        
  {
   Math::APRTest::NoReport report;
         
   result=test(N,report);
  }