Score:3

Crypto

EC group order primality test

valdo

4/24/24, 3:16 PM

(Sorry for a newbie question) In ECC the intent is to create a group of a prime order (or prime multiplied by a relatively small cofactor).

I know there's an algorithm for ECC to count the number of elements. My question is: how is it known that the group order is indeed prime? AFAIK there're no known deterministic algorithms to test the primality of a number in polynomial time.

There're examples of cryptographic EC groups that are commonly used (such as secp256k1) with known group order, and it's asserted that it's prime.

Is this because this group order was tested with probabilistic algorithms (such as Frobenius test) many times? Or in particular case of this number it was possible to prove its primality?

294

2 + 5

elliptic-curves

prime-numbers

Daniel S

4/24/24, 3:23 PM

"AFAIK there're no known deterministic algorithms to test the primality of a number in polynomial time". In fact, there are e.g. the (AKS primality test)[https://en.wikipedia.org/wiki/AKS_primality_test]. There have been probabilistic algorithms to certify primality for even longer e.g. the (Atkin-Morain test)[https://en.wikipedia.org/wiki/Elliptic_curve_primality].

Daniel S

4/24/24, 3:53 PM

@poncho have done as you suggest.

fgrieu

4/24/24, 4:23 PM

To illustrate how much deterministic primality testing has become practical, in Sage (a free algebra package), on my 4yo PC, after `n=115792089237316195423570985008687907852837564279074904382605163141518161494337` (the order of secp256k1), deterministic primality testing with `n.is_prime(proof=True)` lasts <0.04s, versus <0.0001s for probabilistic primality testing `n.is_prime(proof=False)`.

valdo

4/30/24, 9:39 AM

@fgrieu of course. Obviously it's possible to reach arbitrary arbitrary high probability within feasible (even negligible) amount of time. My question was about the existence of a rigorous proof.

fgrieu

4/30/24, 10:17 AM

`n.is_prime(proof=True)` answers `True` only if it (internally) came with a rigorous proof, in the mathematical sense, that this particular `n` is prime. There are methods that also output primality certificates that can be checked. See [this](https://cr.yp.to/primetests.html).

Score:7

Crypto

Daniel S

4/24/24, 3:53 PM

"AFAIK there're no known deterministic algorithms to test the primality of a number in polynomial time". In fact, there are e.g. the AKS primality test. There have been probabilistic algorithms to certify primality for even longer e.g. the Atkin-Morain test.

+ 1

poncho

4/24/24, 6:33 PM

Yes, I suggested that you post this answer; I then realized that, in the context of this question, an answer relating to the time SEC was developed would be a better answer

Score:6

Crypto

poncho

4/24/24, 4:09 PM

Or in particular case of this number it was possible to prove its primality?

I'll try to place this in the context of the 1990's, when the curves were created; at that time, algorithms such as AKS were unknown.

I don't believe Certicom has published what criteria they used to assess primality.

However, what was known at the time was that, if you had the factorization of $p-1$, it would be straight-forward to prove the primality of $p$.

For secp256k1, $p$ (and thus $p-1$) is a 256 bit number; I believe that it was practical (at the time) to factor a 256 bit number [1]; hence if they wanted to, they could have proved the primality.

Alternatively, an early form of Elliptic Curve Primality Testing was also known at the time; it is possible that they used that to prove the primality of the curve orders (as well as the primality of the field characteristics)

Now, I don't know if they did - they also defined much larger curves (where some of the above techniques would have been impractical), and so they may have satisfied themselves with probabilistic methods (such as Miller-Rabin, which was also known at the time).

[1]: Back in the 1980's, I was factoring 200 bit values on my IBM AT; they would have had considerably more resources than that at their disposal.

+ 2

valdo

4/30/24, 9:36 AM

Thanks for the detailed answer. Can you please elaborate this: "f you had the factorization of p−1, it would be straight-forward to prove the primality of p".

poncho

4/30/24, 11:04 AM

@valdo: if you have the factorization of $p-1$, then you can show that an element $g$ has order $p-1$ modulo $p$ (which implies the primality of $p$). And, there are lots of primitive elements modulo $p$ (if $p$ is prime), so checking on random ones is straight-forward. Actually, there are more efficient ways to use the factorization of $p-1$ - this is the easiest to explain (and is efficient enough to be practical)

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: EC group order primality test

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.