> > - *is_prime = 0; > > + *is_prime = 1; > > Nit: you call this a pseudo-prime - which I agree with, but the variable you > have added > is "is_prime" - maybe call it "maybe-prime" or "pseudo-prime"
Yes. I agree. I did this for consistency with the existing code. I will keep this as-is and change all is_prime to is_pseudo_prime in the entire file in a separate pass. > > .Pp > > It is unknown whether any composite number exists that the > > Baillie-PSW algorithm misclassifies as a prime. > > Some suspect that there may be infinitely many such numbers, > > but not a single one is currently known. > > It is known that no such number exists below 2\(ha64. > > You are now pre-checking with miller rabin to reduce the likelyhood of > a composite number of any size, but you are not explaining this here. > > The point of the miller-rabin pre-test is to cheaply reduce the likelyhood > of a composite number being fed to Ballie-PSW to "very small" so that even > if the future hypothesis finds such numbers we are still protected, > and this should be explained here. I see your point. We can add a sentence like Because of this, in addition to the Miller-Rabin test with base 2 that is part of the Baillie-PSW test, additional rounds of Miller-Rabin with random bases are performed. Which then leads to the next paragraph. > > > > +.Pp > > +The number of Miller-Rabin rounds performed by > > +.Fn BN_is_prime_fasttest_ex > > +and > > +.Fn BN_is_prime_ex > > +is determined by > > +.Fa checks : > > +If it is positive, it is used as the number of rounds. > > +If > > +.Fa checks > > +is zero or the special value > > +.Dv BN_prime_checks , > > +a suitable number of rounds is calculated from the bit length of > > +.Fa a . > > .Pp > > If > > .Dv NULL
