Computationally Hard Problems

Cryptography · Axiom Academy

INTRO Computationally Hard Problems Discover why some problems are easy for computers to solve forward but nearly impossible to reverse. Let's explore the difference between easy and hard problems. Adjust the problem size and see how the time required changes. Watch what happens when we visualize polynomial growth versus exponential growth. Cryptography relies on specific problems that are easy in one direction but hard in reverse. Try breaking this lock by guessing keys. Prime Factorization: Easy to multiply 1,234 × 5,678, hard to factor 7,006,652 Discrete Logarithm: Easy to compute 3⁵ = 243, hard to find x when 3ˣ = 243 Elliptic Curves: Easy to go forward, exponentially hard to reverse P vs NP: The Million Dollar Question P problems can be solved quickly. NP problems have solutions that can be verified quickly, but finding them might be hard. Problems that can be solved efficiently. Problems where solutions can be verified efficiently, but finding them might be hard. If P = NP, every problem whose solution can be verified quickly can also be solved quickly. Most computer scientists believe P ≠ NP, which keeps cryptography secure. Modern cryptography relies on asymmetry: one direction is easy, the reverse is hard. Some problems grow exponentially with size, making them effectively impossible to solve for large inputs even with modern supercomputers.

This is the written version of the interactive lesson above. See the full Cryptography course.