What happens in elliptic curve primality testing if you cannot find a suitable discriminant?

Question

I'm trying to understand the computational aspect of elliptic curve primality testing (specifically the Atkin-Morain test), and in general, I understand why it works for a prime number.

However, when it comes to composite numbers, I can't understand why not being able to find a suitable discriminant (and hence not being able to use complex multiplication to construct an elliptic curve with an easily calculable number of points) implies that the number n (which we are testing for primality) is therefore composite.

On the wikipedia page, it states that the list of suitable discriminants is {−3, −4, −7, −8, −11, −12, −16, −19, −27, −28, −43, −67, −163}, and that we need to find a D in that list, such that a^{2}+|D|b^{2}=4N. In most of the implementations of the algorithm that I have found online, if we can't find this representation, for any of the discriminants in the list, then the algorithm returns that N is composite.

I don't understand how this implies that N is composite, rather than implying that we have not been able to set up the Atkin-Morain ECPP properly.

Answer 1

I believe this is a poor wording in the Wikipedia page. We in fact have a huge number of discriminants to choose from, not just that list. I have precomputed lists in my software, varying from 611 choices (a very small set) to almost 17,000 (a bloated set). With fast software such as CM it can be done quickly as needed. Primo looks like it has an enormous quantity to choose from, and I believe goes beyond just Hilbert and Weber polynomials.

The bigger issue is typically being able to factor one of the results sufficiently. That is, we can find a set of appropriate discriminants and from these generate a set of values we want to partially factor. For smallish inputs (say, under 300 digits) this almost never a problem. But as the input size grows, so does the chance that none of them cooperate. More discriminants to choose from helps, as does better factoring. But if we can't succeed here, we're left either failing (this is not saying it is composite!) or trying harder.

There are a lot of steps in the algorithm, and as you note, it is very important to distinguish between "I don't know" and "Composite". It's also important (in my opinion) to have a way to output a verifiable certificate so we know it is working correctly.

In practical implementations, given the times involved, it makes sense to add something like a BPSW test at the beginning. This will very quickly weed out almost every composite so we don't waste time on them. Aside: I say "almost every" since we assume they exist, even though nobody has ever reported a composite that passes. Both Primo and my ECPP implementation run a BPSW test at every stage, more for safety than necessity.

Answer 2

You're correct that it doesn't necessarily make $N$ composite just because you happen to not be able to find the proof that $N$ is prime.

This is a pragmatic, not mathematician decision. Some numbers are really hard to tell using this method, and type 1 error (a false positive) is more dangerous than a type 2 error (false negative) and so type 1 error is selected as the default. Thus people choose to falsely return "composite" when the true answer is "I don't know."