[tofof]

It's unfortunate that he doesn't understand complexity analysis and has taken it upon himself to write an article that requires it as an underpinning.

In particular, I stopped reading at

> the discrete logarithm for elliptic curves, ... We don’t technically know whether these are NP-complete

This is wildly misleading. We do know with absolute certainty that the decision problem for DLC is NP-Hard, and therefore that EPDLC inherits at least NP-Hardness. While it is true that their presence in NP-Hard does not require their pressence in NP (and thus are not proved NP Complete), it is misleading to characterize as the author has here that they are weaker than NP, instead of the known certainty that NP is the absolute minimum bound for their hardness.

[cevi]

If the discrete logarithm problem is NP-hard, then I will eat my hat. The discrete logarithm problem can be solved by Shor's algorithm on a quantum computer, placing it in the complexity class BQP. Anyone who claims that BQP contains an NP-hard problem is selling something - I would bet at a trillion-to-one odds against such a claim (if there were any hope of definitively settling the problem).

[Vervious]

Not sure it's misleading, he did write the word "technically", and anyone who knows what NP-complete is knows that NP-hard does not necessarily mean NP-complete. I am a cryptographer and the article is fine.

Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"

[JohnKemeny]

DLC is in NP and co-NP. Very unlikely to be NP-hard. It is usually listed as one of the candidates for problems that are NP-intermediate, ie, problems in-between P and NP-hard (should they be different).

See e.g. https://cs.stackexchange.com/a/2765

[memkit]

> While it is true that their presence in NP-Hard does not require their pressence in NP (and thus are not proved NP Complete)

You're confused here. The two conditions for a problem being NP-complete are (1) it being NP-hard and (2) it being in NP.

You suggest (2) is the issue, but usually it's harder to prove (1) rather than (2). In the context of factorization problems, the factors are simply the certificate that satisfy condition (2).