How to prove that an algorithm is the time optimal algorithm for implementing a problem?

Given an objective function, we can give many programming implementations based on existing computers. Can we prove that the algorithm given is time optimal? For example, if we give a recursive solver for the NTH term of the Fibonacci sequence, how can we prove that the recursive solver is not optimal (by a general method rather than a program that directly gives constant time complexity)?

• In general, this is not possible. Otherwise, you could probably solve P (!)= NP. For specific problems and assumptions, e.g. compared based sorting in n log n, optimal lower bounds can be calculated. But this is no cryptography question. For a detailed answer, ask theoretical computer science SE. Nov 27, 2023 at 9:27
• Thank you. The reason why I think it's relevant to cryptography is because cryptography is based on hard problems, are the hard problems really hard? That's what I'm wondering, and are they really different in their level of difficulty? I know the P and NP problems, but because I haven't studied them carefully, I don't know if the leading edge research has solved my problem, so I'm asking here.
– 槿铃兔
Nov 27, 2023 at 12:34

Since you stated interest in how to prove an algorithm is time-optimal, a telescopic summary:

This requires proving lower bounds on complexity, which is very difficult in general. I will use "strong" to vaguely refer to polynomial complexity. Let $$b$$ be the bitlength of the key.

RSA: Factoring problem. No strong lower bounds are known, the best algorithms are superpolynomial (in bitlength) but subexponential, e.g., number field sieve has complexity $$e^{c(\log n)^{1/3} ~(\log \log n)^{1/3}}$$ where $$b=\log_2 n$$ (the logs in the exponent are natural logs) and $$c$$ is an absolute constant of the form $$c=(64/9)^{1/3}+o(1).$$

ECC: EC Discrete Logarithm Problem. No strong general lower bounds are known here either. The best known generic algorithms are of exponential complexity though, such as Pollard's rho which has complexity $$2^{b/2}.$$ CAVEAT: All these complexities are based on good choice of parameters and avoiding weak cases for the relevant algorithms.

– 槿铃兔
Nov 27, 2023 at 13:50

What's asked is possible only for some restricted objectives, an no interesting one if we require an exact optimum rather than an optimum within an additive or multiplicative constant, or asymptotic.

For example, it is possible to prove than given $$n$$, adding a list of $$n$$ non-negative integers each stored as one word in memory at incremental addresses from $$4$$ to $$n+3$$, producing the result on two words at $$2$$ and $$3,$$ is possible with $$4n+9$$ clock cycles for a certain program running on some idealized CPU architectures with some characteristic such that loop enrolling past a certain threshold incurs a penalty; and that this is $$4n+9$$ bound is strictly optimal. It would be possible to prove $$\mathcal o(4n)$$ more easily and on more architectures, and even easier to prove $$\mathcal O(n)$$ on a wide class of machines.

However, we can't do this for many practically useful objectives, and we can't for any that in practice seems to requires super-polynomial (including exponential) time with the size $$n$$ of the problem. Examples include factorization of an RSA moduli, and solving certain classes of Discrete Logarithm Problem. For these, we do not even know how to prove the asymptotic growth rate.

• Thank you for your answer, I am researching the security of RSA and ECC, so I ask the above question.
– 槿铃兔
Nov 27, 2023 at 12:45
• @槿铃兔: you want to study the complexity of GNFS for RSA and BS/GS (or some others) for ECC. For recommendations there is keylength.com
– fgrieu
Nov 27, 2023 at 15:37