Ona se vůbec těžko dokazuje výpočetní náročnost. Doufáme a věříme, že pro RSA ani ECC neexistuje algoritmus pro prolomení v lineárním čase na klasickém (nekvantovém) počítači. Ale kdyby se to někomu povedlo dokázat, dokáže tím zároveň P≠NP.
Taky se čeká, že prolomení RSA ani ECC není NP-complete. Opět, kdyby se to někomu povedlo dokázat, dokáže tím P≠NP. A kdyby to náhodou bylo NP-complete, znamenal by Shorův algoritmus s příchodem kvantových počítačů hrozbu nejen pro dnes převládající asymetrické algoritmy, ale i pro symetrické algoritmy a postkvantové algoritmy – vlastně by zbyly unconditionally secure algoritmy (Vernamova šifra, Shamir Secret Sharing Scheme, …) a vše ostatní by rozluštil kvantový počítač v polynomiálním čase.
A dokázat relativní sílu ECC vůči RSA bude asi ještě vetší oříšek než dokazovat asymptotickou složitost, kde můžete zanedbat některé konstanty…