4 ms·

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 t

by jl2718 4y ago

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.

nullc 4y ago
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%80%93Goldwasser%E2%80%93Kilian%E2%80%93Morain_certificates https://en.wikipedia.org/wiki/Primality_certificate#Atkin%E2... https://en.wikipedia.org/wiki/Elliptic_curve_primality https://en.wikipedia.org/wiki/Elliptic_curve_primality
- throwaway81523 4y ago
  I wonder if the AKS algorithm might have been faster for numbers of this size.
  - nullc 4y ago
    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. :)
pbsd 4y ago
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.

by jl2718 4y ago

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.

nullc 4y ago

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%80%93Goldwasser%E2%80%93Kilian%E2%80%93Morain_certificates https://en.wikipedia.org/wiki/Primality_certificate#Atkin%E2... https://en.wikipedia.org/wiki/Elliptic_curve_primality https://en.wikipedia.org/wiki/Elliptic_curve_primality

throwaway81523 4y ago
I wonder if the AKS algorithm might have been faster for numbers of this size.
- nullc 4y ago
  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. :)

pbsd 4y ago

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.