PRIMES in P: A Quiet Revolution in Algorithms

The day prime numbers quietly entered P

For over 2,000 years, mathematicians knew what prime numbers were — but didn’t know how to test them fast and perfectly. In 2002, three people at Indian Institute of Technology Kanpur proved that the problem everyone thought was hard… wasn’t.

This is the story of the AKS Primality Test and the moment computation changed forever.

A Simple Question That Refused to Go Away

A prime number is easy to define:

A number greater than 1 that has no divisors except 1 and itself.

Checking small primes is trivial. Checking a 500-digit number is not.

Why this matters:

• Internet security
• Online banking
• Military communication
• Cryptography (RSA depends on large primes)

The entire digital world depends on one question:

Is this number prime?

Fast… but “Probably”

Before 2002, computers used probabilistic algorithms.

The most famous one was the Miller–Rabin primality test.

• Very fast
• Almost always correct
• But never 100% certain

For engineers, “almost” was fine. For mathematicians, it was unacceptable.

Mathematics does not tolerate probably.

Ever Thought About NP Becoming P?

In computational complexity, problems are classified by how hard they are.

• P → problems computers can solve efficiently
• NP → problems whose solutions can be verified efficiently

The biggest open question in computer science is:

P vs NP — are hard problems secretly easy?

Primality testing lived in an uncomfortable middle ground. Many believed it should be in P — but nobody could prove it.

Until someone stopped assuming it was hard.

Kanpur, Summer 2002

Most of the campus was empty. The heat was brutal. Inside a quiet office sat three people:

• Manindra Agrawal — professor, believer in raw undergraduate thinking
• Neeraj Kayal — sharp, focused
• Nitin Saxena — obsessed with why, not shortcuts

No supercomputers. No funding hype. Just algebra, whiteboards, and patience.

They weren’t improving old methods.

They were asking a different question:

What if primes reveal themselves through algebraic structure?

The Breakthrough: PRIMES Is in P

Their key insight came from polynomials.

They proved that a number n is prime if and only if a specific algebraic identity holds and crucially, that identity can be checked in polynomial time.

No randomness. No probability. No unproven assumptions.

They wrote a short paper titled:

PRIMES is in P

The algorithm became known as the AKS Primality Test (Agrawal–Kayal–Saxena).

It was the first algorithm in history that was:

• General
• Deterministic
• Polynomial-time
• Unconditional

All four at once.

The Math World Tries to Break It

The paper was emailed to experts.

Reaction:

• “There must be a mistake.”
• “This can’t be this simple.”

They checked. They rechecked. No flaw.

In August 2002:

• Mathematicians worldwide verified the proof
• The New York Times reported it
• IIT Kanpur’s servers crashed

A 2,000-year-old question was finally settled.

So… Did NP Turn Into P?

No.

But something equally important happened.

A problem long suspected to be hard was proven easy.

Primality testing officially entered P.

This didn’t solve P vs NP, but it proved something deeper:

Our intuition about difficulty can be wrong.

That realization reshaped how computer scientists think about algorithms.

Why AKS Still Matters

Even today, cryptographic systems often use probabilistic tests — they’re faster in practice.

But AKS matters because:

• It guarantees absolute correctness
• It sets a theoretical foundation
• It shows elegance can beat brute force

AKS is about truth, not speed.

What Happened After

In 2006, the trio received the Gödel Prize, the highest honor in theoretical computer science.

Today:

• Nitin Saxena works on algebraic complexity and the limits of computation
• He is the founding Dean of the Wadhwani School of AI and Intelligent Systems
• His focus: strong mathematical foundations for real-world AI

From prime numbers to artificial intelligence the same curiosity drives it all.

Official & Authoritative Links

• AKS original paper (IIT Kanpur — PDF) https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
• AKS Primality Test — Wikipedia https://en.wikipedia.org/wiki/AKS_primality_test
• Manindra Agrawal — IIT Kanpur profile https://www.cse.iitk.ac.in/users/manindra/
• P vs NP Problem (Clay Mathematics Institute) https://www.claymath.org/millennium/p-vs-np/

A Good Ending to Remember

Sometimes, the problem isn’t that something is impossible.

Sometimes, it’s that everyone agreed it was.

Three people in a quiet office didn’t know they weren’t supposed to succeed. So they didn’t stop.

And one summer later, mathematics had to admit:

Impossible was just unexplored.