Offensive Security Researcher & Quantum Cryptography Analyst

Complexity Theory Algorithm: Working, Explanation, and Computational Limits

Abdul Wahab Junaid
Complexity Theory algorithm and working of this algorithm.

Complexity Theory algorithm and working of this algorithm.

I want to step back from specific algorithms in this file and talk about the theoretical framework that tells me why those algorithms are considered secure or insecure in the first place: computational complexity theory. Whenever I say something like “factoring is hard” or “this cipher is secure,” I’m implicitly making a claim rooted in complexity theory — about how the resources (time, memory) needed to solve a problem scale as the problem gets larger. I find this is the piece that ties the whole series together: complexity theory is the language cryptographers use to precisely state what “hard” and “secure” actually mean.

History and Background

I trace the formal origins of computational complexity theory to the 1930s work of Alan Turing, who introduced the Turing machine as an abstract model of computation, and to Alonzo Church’s related work on computability. But complexity theory as a distinct field — concerned not just with whether a problem is computable at all, but with how efficiently it can be computed — really took shape in the 1960s and 1970s. Juris Hartmanis and Richard Stearns formalized time and space complexity classes in 1965. Stephen Cook’s 1971 paper introduced the concept of NP-completeness and the Cook-Levin theorem, and Richard Karp’s 1972 paper showed 21 important problems were NP-complete, which together kicked off the modern study of computational hardness. Cryptography’s marriage to complexity theory happened almost immediately afterward: the 1976 Diffie-Hellman paper and the 1977 RSA paper both explicitly framed their security arguments in terms of the presumed computational hardness of certain number-theoretic problems, launching the field now known as “complexity-based” or “computational” cryptography — as opposed to the “information-theoretic” security I cover in the next file.

Problem Statement

Complexity theory, in the context I care about here, addresses the question: how do I formally classify computational problems by the resources required to solve them, and how does that classification let me build cryptographic systems whose security rests on rigorous (even if unproven) hardness assumptions? Specifically, cryptography needs problems that are easy to compute in one direction (so legitimate users can encrypt/decrypt/sign efficiently) but believed intractable to invert without a secret (so attackers cannot break the scheme in feasible time) — complexity theory gives me the vocabulary and proof techniques to reason precisely about this asymmetry.

Core Concepts

How It Works

I think about applying complexity theory to a cryptosystem’s design in these stages:

  1. I identify a computational problem believed to be hard — for example, integer factorization, the discrete logarithm problem, or the subset-sum (knapsack) problem.
  2. I design a cryptographic scheme (encryption, signature, key exchange) whose security — specifically, an attacker’s ability to break confidentiality or forge signatures — can be shown to require solving that hard problem, typically via a reduction: “if an attacker can break this scheme, I can use that attacker as a subroutine to solve the underlying hard problem.”
  3. I choose parameter sizes (key lengths, group sizes) large enough that, given the best known algorithms for the underlying hard problem (as covered in the factoring and discrete-log files), the concrete number of operations required to break the scheme exceeds what’s feasible with realistic computational resources over a meaningful time horizon.
  4. I monitor ongoing cryptanalytic research; if better algorithms are found for the underlying hard problem (reducing its complexity), I may need to increase parameter sizes or migrate to different hardness assumptions entirely.
  5. For schemes without a formal reduction to a well-studied hard problem, I rely instead on extensive public cryptanalysis over time as an empirical (rather than provable) form of confidence — this is the situation with most symmetric ciphers, like AES, where no P vs NP-style reduction exists, and confidence is built through decades of failed attack attempts by the research community.

Working Principle

I find the core intellectual move here is turning an unproven mathematical belief (like “factoring is hard”) into a rigorous, quantitative promise about a cryptosystem’s security, using the machinery of reductions. A security proof by reduction says something precise: “any algorithm that breaks this cryptosystem with non-negligible probability, in polynomial time, can be transformed into an algorithm that solves the underlying hard problem, also in polynomial time.” Since no known polynomial-time algorithm exists for problems like factoring or discrete log (despite decades of dedicated effort by the world’s best mathematicians and computer scientists), this gives strong (though not absolute — since P vs NP itself remains unproven) practical confidence that the cryptosystem is secure as long as the underlying assumption holds. This is fundamentally different from “security through obscurity” — the security doesn’t rest on secrecy of the algorithm, but on a mathematically precise, publicly scrutinized computational hardness claim.

Mathematical Foundation

Big-O notation, describing an algorithm’s growth rate:

$$f(n) = O(g(n)) \iff \exists c, n_0 \text{ such that } f(n) \le c \cdot g(n) \text{ for all } n \ge n_0$$

Class P (polynomial time):

$$P = { L : L \text{ decidable by a deterministic Turing machine in time } O(n^k) \text{ for some constant } k }$$

Class NP (nondeterministic polynomial time), equivalently defined via verification:

$$L \in NP \iff \exists \text{ polynomial-time verifier } V \text{ such that } x \in L \iff \exists w, |w| = O(|x|^k), V(x, w) = \text{accept}$$

NP-completeness: a problem $L$ is NP-complete if $L \in NP$ and every problem in NP polynomial-time reduces to $L$:

$$\forall L’ \in NP, \quad L’ \le_p L$$

One-way function definition: a function $f$ is one-way if it is computable in polynomial time, but for every probabilistic polynomial-time algorithm $A$, the probability of inverting it is negligible:

$$\Pr_{x \leftarrow {0,1}^n} \big[ A(f(x)) \in f^{-1}(f(x)) \big] \le \text{negl}(n)$$

Security reduction (informal template), showing a scheme’s security reduces to a hard problem’s hardness: if an adversary $\mathcal{A}$ breaks scheme $S$ with probability $\epsilon$ in time $t$, I construct an algorithm $\mathcal{B}$ using $\mathcal{A}$ as a subroutine that solves hard problem $\Pi$ with probability related to $\epsilon$ in time close to $t$:

$$\text{Adv}{\mathcal{A}}^{S}(t) \le f\big(\text{Adv}{\mathcal{B}}^{\Pi}(t’)\big)$$

for some efficiently computable relationship $f$ and comparable running time $t’$, which is the standard form of a “tight” or “loose” security reduction found throughout modern cryptographic proofs.

Diagrams

flowchart TD
    A[Choose a believed-hard computational problem] --> B[Design cryptographic scheme built on that problem]
    B --> C[Construct security reduction: breaking scheme implies solving hard problem]
    C --> D[Choose parameter sizes based on best known algorithm complexity]
    D --> E[Monitor cryptanalysis research for algorithmic improvements]
    E --> F{Better algorithm found?}
    F -- Yes --> G[Increase key sizes or migrate assumptions]
    F -- No --> H[Confidence maintained at current parameters]

Pseudocode

// Conceptual template for a reduction-based security argument
function security_reduction(adversary_A, hard_problem_instance):
    // Given an adversary that breaks the cryptosystem, build a
    // solver for the underlying hard problem
    function solver_B(problem_instance):
        scheme_instance = embed_problem_into_scheme(problem_instance)
        adversary_output = adversary_A(scheme_instance)
        solution = extract_hard_problem_solution(adversary_output, problem_instance)
        return solution

    // If adversary_A succeeds with non-negligible probability,
    // solver_B solves the hard problem with related probability,
    // contradicting the assumed hardness of the problem
    return solver_B

// Concrete security parameter selection (illustrative)
function choose_key_size(security_level_bits, best_known_attack_complexity_fn):
    key_size = minimal_starting_size
    while best_known_attack_complexity_fn(key_size) < 2^security_level_bits:
        key_size = increase(key_size)
    return key_size

Step-by-Step Example

I’ll trace a simplified, illustrative version of a security reduction — the kind of reasoning behind RSA’s textbook security discussion (informally, not the full formal RSA assumption proof, which has some subtleties around specific attack models).

  1. Suppose I claim: “if an attacker can compute the private RSA exponent $d$ from the public key $(n, e)$, then that attacker can factor $n$.”
  2. To justify this, I construct a reduction: given an algorithm $\mathcal{A}$ that outputs $d$ from $(n, e)$, I build a factoring algorithm $\mathcal{B}$ as follows.
  3. $\mathcal{B}$ calls $\mathcal{A}(n, e)$ to get $d$.
  4. Knowing $ed \equiv 1 \pmod{\varphi(n)}$, I can compute $ed – 1$, which is a multiple of $\varphi(n)$.
  5. Using a known number-theoretic technique (finding a nontrivial square root of 1 modulo $n$ using the multiple of $\varphi(n)$, similar in spirit to the Miller-Rabin structure I described in the prime-generation file), $\mathcal{B}$ can, with high probability, extract a nontrivial factor of $n$.
  6. So $\mathcal{B}$ successfully factors $n$ using $\mathcal{A}$ as a subroutine, in time close to $\mathcal{A}$’s running time.
  7. Conclusion: recovering the RSA private exponent is at least as hard as factoring $n$ (since I’ve shown a way to turn a $d$-recovering algorithm into a factoring algorithm) — so as long as factoring $n$ remains computationally infeasible for the chosen key size, recovering $d$ directly (via this particular attack strategy) is also infeasible.

I find this example valuable because it shows exactly how “security” claims get built, piece by piece, from more fundamental, well-studied hardness assumptions, rather than being asserted from thin air.

Time Complexity

Complexity theory itself doesn’t have a single “time complexity” — it’s the meta-framework for describing time complexity of everything else. But within cryptography, I typically care about three specific complexity regimes: polynomial time algorithms (efficient — what a legitimate user can do, like RSA encryption at $O(k^2 \log e)$ for $k$-bit numbers), subexponential time algorithms (like the Number Field Sieve for factoring, at roughly $L_n[1/3, c]$, too slow to be practical at large scale but faster than brute force), and exponential time algorithms (like brute-force key search, at $O(2^k)$ for a $k$-bit key, considered infeasible for sufficiently large $k$). Cryptographic security parameters are chosen specifically to push the best known attack complexity for a given scheme into the “practically exponential/infeasible” regime, even when the underlying problem is only proven subexponential or is merely conjectured to lack a polynomial-time solution.

Space Complexity

Similarly, space complexity considerations show up throughout cryptanalysis: some attacks (like meet-in-the-middle attacks, or Baby-step Giant-step for discrete logs, as I described earlier) trade increased memory usage for reduced time, and a full security analysis must account for both dimensions — a “time-space tradeoff” attack that needs infeasible amounts of memory (even if the raw operation count looks feasible) may not constitute a practical break. This is why modern security parameter recommendations (like NIST’s key-size guidelines) specify security levels in terms of a combined time-and-memory cost model, not time alone.

Correctness Analysis

I think “correctness” in complexity theory takes on a different character than in the specific algorithm files earlier in this series — here, the relevant claims aren’t “does this algorithm compute the right answer” but rather “does this classification of a problem’s difficulty hold up under formal scrutiny.” The P vs NP question itself remains formally unproven (it’s one of the seven Clay Millennium Prize problems), meaning that, strictly speaking, no cryptographic scheme based on an NP-hard or presumed-hard problem has an absolute proof of security in the way a mathematical theorem does — what I actually have is a conditional guarantee: “this scheme is secure, assuming problem X is hard,” backed by a rigorous reduction proof plus decades of failed attempts by the research community to solve X efficiently. This distinction — conditional, reduction-based security versus absolute mathematical proof — is one of the most important conceptual points in all of modern cryptography, and I think every cryptography student eventually needs to internalize it.

Advantages

Disadvantages

Applications

Complexity theory underlies the entire theoretical justification for public-key cryptography (RSA, Diffie-Hellman, ElGamal, elliptic curve cryptosystems), the formal security proofs used in modern cryptographic protocol design (provable security, exact/concrete security analysis), and the ongoing effort to design post-quantum cryptography, where new hardness assumptions (like lattice problems or hash-based constructions) are being formally studied precisely because Shor’s algorithm complexity-theoretically breaks the classical factoring and discrete-log assumptions. Beyond cryptography, complexity theory is foundational across all of theoretical computer science, algorithm design, and the study of computational limits generally.

Implementation in C

Because complexity theory itself is a mathematical and analytical framework rather than a single algorithm, I demonstrate its application here with a small C program that empirically measures and compares the growth rates of a polynomial-time algorithm versus an exponential-time algorithm, illustrating the practical gap complexity theory predicts.

#include <stdio.h>
#include <time.h>
#include <math.h>

/* Polynomial-time example: trial division primality check, O(sqrt(n)) */
int is_prime_trial_division(long long n) {
    if (n < 2) return 0;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}

/* Exponential-time example: brute-force subset-sum search, O(2^n) */
int subset_sum_exists(int arr[], int n, int target) {
    for (long long mask = 0; mask < (1LL << n); mask++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1LL << i)) sum += arr[i];
        }
        if (sum == target) return 1;
    }
    return 0;
}

int main(void) {
    /* Demonstrate polynomial-time scaling */
    printf("Trial division primality timing (polynomial-time O(sqrt n)):\n");
    long long test_values[] = {104729, 1299709, 15485863};
    for (int i = 0; i < 3; i++) {
        clock_t start = clock();
        int result = is_prime_trial_division(test_values[i]);
        clock_t end = clock();
        double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
        printf("  n=%lld prime=%d time=%.6fs\n", test_values[i], result, elapsed);
    }

    /* Demonstrate exponential-time scaling */
    printf("\nBrute-force subset-sum timing (exponential-time O(2^n)):\n");
    for (int n = 15; n <= 22; n += 2) {
        int arr[22];
        for (int i = 0; i < n; i++) arr[i] = i + 1;
        int target = -1; /* force worst case: no solution, must check all subsets */

        clock_t start = clock();
        int result = subset_sum_exists(arr, n, target);
        clock_t end = clock();
        double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
        printf("  n=%d subsets_checked=2^%d found=%d time=%.6fs\n", n, n, result, elapsed);
    }

    return 0;
}

I designed this program to make the abstract idea of “polynomial vs. exponential growth” concrete and measurable: the primality checks stay fast even as $n$ grows into the millions, while the subset-sum brute force visibly slows down dramatically with each small increase in $n$, which is exactly the qualitative distinction complexity theory formalizes.

Sample Input and Output

Input: primality checks on three values near 100,000–15,000,000, and brute-force subset-sum searches with no valid solution (worst case) for input sizes 15 through 22.

Output (illustrative timings; exact numbers vary by machine):

Trial division primality timing (polynomial-time O(sqrt n)):
  n=104729 prime=1 time=0.000002s
  n=1299709 prime=1 time=0.000006s
  n=15485863 prime=1 time=0.000021s

Brute-force subset-sum timing (exponential-time O(2^n)):
  n=15 subsets_checked=2^15 found=0 time=0.000112s
  n=17 subsets_checked=2^17 found=0 time=0.000451s
  n=19 subsets_checked=2^19 found=0 time=0.001823s
  n=21 subsets_checked=2^21 found=0 time=0.007290s

Even at this tiny scale, I can already see the subset-sum timings roughly quadrupling with each 2-step increase in $n$ (consistent with $2^n$ growth), while the primality check timings barely move even as the numbers being tested grow by two orders of magnitude — a small, hands-on illustration of exactly the asymptotic gap complexity theory predicts, and exactly why cryptographers can confidently push key sizes into a regime where brute-force attacks become physically infeasible.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version