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

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.

• Reading the wikipedia article again, after saying "we achieve sufficiency if ..." and listing the D values where h(D)=1, the very next sentence (the first of section "The test") says "Pick discriminants D in sequence of increasing h(D)." That h(D) needs to be 1 is not said anywhere in the Atkin/Morain paper. Nothing in the ECPP pseudocode in Crandall/Pomerance says that, and shows using h(D)=2. I don't see anything like it in Cohen. Husemoeller A.2.1.2 implies h(D) > 1. Morain 2005, page 7: "Typical values of h are now routinely in the 10000 zone." (!) Feb 23, 2016 at 20:01

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.

• Thanks very much for your help! Would you be able to explain a bit more about how we could precompute a list of discriminants to choose from? Other sources, not just wikipedia, seem to also give a short list of discriminants based on the fact the Hilbert class number needs to be 1. For example, Prime Numbers: A Computational Perspective gives the list {−3, −4, −7, −8, −11, −19, −43, −67, −163} Feb 23, 2016 at 15:18
• See page 361 of that book. The list you give is for h(D) = 1. These are the most effective, but you can keep going -- h(D) does not have to be 1. Their example on page 366 gives curve parameters using all discriminants where h(D) <= 2. Also see Cohen's "Course in Computational Algebraic Number Theory" section 9.2. It gives enough detail to guide an implementation. Absolutely essential reading is "Elliptic Curves and Primality Proving" by Atkin and Morain 1992. It's tough slogging but it answers so many details. Morain 2005 is also worth reading. Feb 23, 2016 at 18:36

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."

• I agree with your answer, but also think that the false result makes sense in a compositeness test (e.g. "probably prime") but should never be done in a program or function whose purpose is a proof. I've seen software do it though. Feb 23, 2016 at 2:06
• Yes definitely. This was in the context of the programs that the OP was finding on the Internet Feb 23, 2016 at 2:23
• Okay, it seems I'm incorrect in thinking that the elliptic curve primality testing will give a definite output of prime/composite then. Its nice to know that I wasn't just misunderstanding the algorithm though. Thanks! Feb 23, 2016 at 10:49
• @sophie, while that is true, it almost never actually happens. I've not seen a failure from Primo or ecpp-dj. They can churn and churn on inputs, but they have enough discriminants that there is work to do. Feb 23, 2016 at 18:49