Re: ECPP cerificate validation problem

[Andreas Enge <andreas.enge@inria.fr>]

Hello,

I surmise the certificate was created with my CM software. I had considered
this possibility of q > N, but did not expect it to actually happen in
practice; as Karim says:

Am Thu, Oct 19, 2023 at 11:52:40PM +0200 schrieb Karim Belabas:
> But this q >= N assumption is irrelevant since the given data and checks
> prove the primality of N assuming the primality of q. Whether q >= N holds
> or not.

The fastECPP implementation in CM creates a bunch of discriminants (the more
cores are used for the MPI version, the more discriminants are considered in
one step), computes the cardinalities of the associated elliptic curves,
removes smallish prime factors and then tests whether the results are prime.
Potential primes are tested in increasing order, which means that all
smaller candidates were not prime. This can either mean that too few cores
were used, resulting in few candidates to be tested; or that the number was
particularly difficult to prove. In this case, just moving away from it,
even if it increases the number, is a welcome progress and in a sense an
alternative to backtracking. But as said, it should happen very rarely.
By the way, this is a bit similar to the proven, hyperelliptic primality
test by Adleman and Huang, which can double the size of the prime in one step.

Andreas