I have trouble classifying Elliptic Curve Discrete Logarithm Problem as NP-Hard or NP-Complete. Where does ECDLP belong? Any brief comprehensive answer is encouraged. Thanks.
Asked
Active
Viewed 752 times
3
Henno Brandsma
- 235,532
- 9
- 102
- 245
alyssaeliyah
- 223
- 2
- 10
-
I don't think anyone knows.... – Angina Seng Mar 13 '19 at 07:19
-
@LordSharktheUnknown Why, please enlighten me? – alyssaeliyah Mar 13 '19 at 07:27
-
2It's unknown. You'll be famous if you can prove it to be NP hard or NP complete... – Henno Brandsma Mar 13 '19 at 16:46
-
@Why is it unknown? Why is it not NP-Hard? – alyssaeliyah Mar 14 '19 at 02:10
-
Because there is no proof that it is or is not. There are many open problems in this area. Cryptography is based on ignorance. – Henno Brandsma Mar 15 '19 at 18:19
-
You first need a clean definition on how you define the input size. For a fixed curve, discrete logarithm is obviously O(1) as there are only a fixed number of candidates that need to be checked. – Peter Zeller Aug 12 '22 at 15:55