Hacker News Reader

Comment by jl2718 | Hacker News Reader

This is probably a stupid question, but why do they use an elliptic group rather than, e.g. an ordinary exponential group? It seems they’re using the property that the group order is N-1.

View on HN

You can do the same thing with modular exponentiation, i.e. Pocklington's primality proving, but that requires finding a large factor of N-1, which is not easy in general.

With elliptic curves you get as many shots at finding a group order with a large factor as you want, since if you fail the current attempt you can simply try another curve with a different order. So you can keep trying until you find a curve that has an easy to find large group order factor which, as it turns out, happens in probabilistic polynomial time.

My understanding is that this particular proof works by constructing a curve over a finite field built of the number to be tested with a "sufficiently large" prime order, you prove its order by just multiplying a generator by the order. The curve won't work right if the field isn't a field (or in other words unless our candidate is actually prime). The proof has to be applied recursively to prove the order of the test group is itself prime.

Take your pick of redundant WP articles for a more technical explanation.

https://en.wikipedia.org/wiki/Primality_certificate#Atkin%E2...

https://en.wikipedia.org/wiki/Elliptic_curve_primality

I wonder if the AKS algorithm might have been faster for numbers of this size.

AKS doesn't produce a certificate so it would make the computation much less useful. Verifying a ECPP certificate is faster than running AKS for sure.

Someone could go around claiming to have proved numbers prime with AKS when really they just passed strong Baillie-PSW ... if someone ever caught their fraud they'd at least make an important discovery of a Baillie-PSW pseudoprime. :)

Reply on news.ycombinator.com