Why Computational Number Theory Still Runs the Internet
I picked up Computational Number Theory and Modern Cryptography because I was tired of the one-line version of internet security. Song Y. Yan wrote it. The ISBN is 978-1-118-18858-3. Wiley and Higher Education Press published it in 2013. It is a graduate textbook. It is dry in places. It is formula-heavy. And the spine of the argument is still the security model your phone uses when it opens a lock icon.
This series is me reading that book out loud. I am not reprinting the lectures. I am retelling the claims, arguing with them, and marking what still holds in 2026. You get a review, not a course clone.
A stack, not a vibe
Yan’s preface is blunt. The book is about computational number theory and the public-key cryptography that sits on it. He draws a stack. Number theory on one side. Computation theory on the other. Computational number theory in the middle. Modern number-theoretic crypto hanging off that middle.
If you only keep one sentence from these posts, keep this. Primality testing is easy. Integer factorization and discrete logarithms are believed hard on a classical computer. Public-key crypto sits on that belief. Not on a finished proof.
He says the quiet part in the same paragraph. Nobody has proved that factoring and discrete logs must be infeasible on a digital computer. Crypto Twitter says “hard” like it is gravity. Yan says it is an observation plus a bet. I like him more for that. The rest of the book is him building locks on the bet, then showing how a quantum machine would pick them.
Four parts, eleven chapters
The book has four parts and eleven chapters. I am going to walk them in order.
Part I is preliminaries. Chapter 1 is the tour of number theory, computation theory, computational number theory, and modern cryptography. Chapter 2 is the toolkit. Groups, rings, fields, divisibility, congruences, primitive roots, elliptic curves.
Part II is the computational engine. Chapter 3 is primality testing, with Miller-Rabin, elliptic curve tests, and the AKS test that put primality in polynomial time. Chapter 4 is integer factorization, up through ECM, the quadratic sieve, and the number field sieve. Chapter 5 is discrete logarithms, including the elliptic curve version.
Part III is the crypto you meet in the wild. Chapter 6 is secret-key cryptography. Chapter 7 is factoring-based public-key stuff: RSA, Rabin, probabilistic encryption, zero-knowledge proofs. Chapter 8 is discrete-log crypto: Diffie-Hellman-Merkle, ElGamal, Massey-Omura, digital signatures. Chapter 9 is the elliptic curve analogues, including ECDSA.
Part IV is the plot twist. Chapter 10 is quantum algorithms for order finding, factoring, discrete logs, and elliptic curve discrete logs. Chapter 11 is what might survive. Coding-based crypto, lattice-based crypto, plus a look at true quantum cryptography and even DNA schemes.
Eleven chapters. I will treat each as a review stop, not as a problem set.
Who Yan is, and why the last chapters exist
The author page is doing work here. Song Y. Yan majored in computer science and mathematics. He got a PhD in number theory at the University of York in England. His research list is this book’s table of contents in human form. Computational number theory. Complexity. Algebraic coding. Public-key cryptography. Network security.
He had already written the prequels. Number Theory for Computing. Cryptanalytic Attacks on RSA. Primality Testing and Integer Factorization in Public-Key Cryptography. Quantum Attacks on Public-Key Cryptosystems in 2012. This 2013 book folds those threads into one course text. He signed the preface in London in June 2012.
So when he talks about RSA attacks, he is not visiting. When he talks about quantum algorithms, he had just published a whole book on quantum attacks. The last two chapters are not a sticker. They are him following his own research into the thing that breaks the hardness story.
Then quantum shows up and eats the bet
Primality testing can be done in polynomial time. Factoring and discrete logs still cannot, as of his writing. Part III studies schemes that rely on that gap. RSA needs factoring to stay ugly. Diffie-Hellman needs discrete logs to stay ugly. Elliptic curve crypto needs the curve discrete log to stay ugly.
Then the hangover. Those same problems can be solved in polynomial time on a quantum computer, if you can build a practical one with several thousand quantum bits. If that machine exists, IFP, DLP, and ECDLP stop being locks. RSA, Diffie-Hellman, and elliptic curve schemes break.
Yan is not a doomer about all cryptography. A quantum computer, in his telling, is a special device. It is good at some problems. It is not a wand for every hard problem. Coding-based problems and lattice-based problems, he says, cannot be solved in polynomial time even on a quantum computer. At least not with the attacks he knows then.
He also notes that quantum-resistant cryptography is still classical cryptography that happens to resist quantum attacks. Then he introduces a truly quantum scheme from physics, and DNA schemes from molecular computation. Some of that last stop aged. Some of it became the post-quantum standards fight you keep seeing in 2026.
Why a 2013 textbook still matters
Because the logical machine did not move as much as the product names did.
We still generate primes because primality is the easy step. We still multiply two big primes and call the product a public modulus. We still treat factoring that modulus as the expensive direction. We still do Diffie-Hellman, mostly on elliptic curves now. And we still argue about when a quantum machine becomes large enough to make chapter 10 operational, not theoretical.
What did move is the furniture on top. Yan’s Mersenne prime tables stop in 2009. RSA-768 is the factoring trophy in the book. Key sizes went up. Lattice schemes left the research poster and entered standards work. But the argument is the same. Easy direction, hard direction, and a hardness we have not proved.
It is written as a text for final-year undergraduates or first-year postgraduates. If you wanted a beach read, this is the wrong object. If you wanted to see why “the internet runs on primes” is both true and sloppy, this is the right object. The formulas are real. The dryness is real. The internet still sits on the bet he wrote down in 2012.
How I am going to read this
Next I start chapter 1 for real. Integers, primes, unique factorization, Euclid’s infinite primes, the Prime Number Theorem, the Riemann Hypothesis as a million-dollar problem. Then Turing machines, and the Cook-Karp idea that polynomial time means practical.
After that, the same chapter turns into the book’s whole map. Primality, factoring, discrete logs, RSA as a sketch, and the admission that the security is computational, not absolute. That is the whole argument in one chapter. I am treating it as a review, not a reprint.
This book says the internet’s locks are number-theoretic bets. Classical computers have not cashed them out. Quantum computers, on paper, can. Codes and lattices are the spare keys. I am here to see if that story still holds when you actually read the pages. And I will keep saying when the 2013 snapshot is just a snapshot, not the last word.