3 ms·
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptog
by Dylan16807 2y ago
> The next question is whether there are programs with lower time bounds that can be made arbitrarily large. Actually, we don't know the answer to that. Cryptography assumes the answer is yes, but that's an assumption.
Cryptography does not assume that. It only needs a certain amount of slowness, and a large polynomial like n^20 is more than sufficient. But more importantly the best case for cryptographic security is exponential time. Cryptography ignores the entire science of super large numbers.
To really boil down what cryptography needs, it's problems that take ≤2^40 operations to verify but ≥2^200 (irreversible) operations to solve. It doesn't actually need to scale at all.
Also it's not hard to make programs that take huge amounts of time. In particular, a program that uses exponential time and leaves an exponentially long output is downright trivial to write. In pseudocode: while(i++ < 2^n) output.append(1)