Computation Theory and Why Hard Problems Matter
Sections 1.3 and 1.4 of Computational Number Theory and Modern Cryptography are the moment the textbook stops warming up. Song Y. Yan, ISBN 978-1-118-18858-3, finally names the problems the rest of the book will live inside. I read this as the whole map on one table. Computational number theory, the hard problems, then modern crypto after the 1970s.
He defines computational number theory as number theory plus computation theory. Computers solve number problems. Number ideas solve computer problems. This book picks the first direction, and only the problems that talk to public-key cryptography.
Primality is the easy gate
The Primality Testing Problem is almost polite. Input n greater than 1. Output yes if n is prime, no otherwise. Theoretically, PTP is in polynomial time. It is efficient. Yan still says a huge candidate can be annoying in practice. Easy in complexity slang is not the same as instant on a laptop from 2008.
He cannot talk primes without Mersenne primes, numbers of the form 2^p - 1 where p is prime and the result is also prime. As of the book, only 47 such p were known. The largest then was 2^43112609 - 1, which is also his largest known prime, 12,978,189 digits, found in 2008. The 48th slot in the table is a question mark.
The Electronic Frontier Foundation had put up prize money for huge primes, from fifty thousand dollars for a million digits up to a quarter million for a billion digits. Nayan Hajratwala claimed the first prize with the 38th Mersenne prime in 1996. Edson Smith at UCLA claimed the ten-million-digit prize in 2008. The last two prizes were still sitting there. We still do not know if there are infinitely many Mersenne primes.
Factoring is one chunk, not a full recipe
The Integer Factorization Problem is meaner, and more honest than the pop version. Input n greater than 1. Output one nontrivial factor a, with 1 less than a less than n. You do not even have to output a prime factor. One chunk. The assumption is that going from the product back to a factor is hard.
If you want the full Prime Factorization Problem, you recurse. Test primality. Split. Repeat. Yan writes PFP as PTP plus IFP. Primality is the cheap pass. Factoring is the expensive one.
He is blunt. PTP is polynomial time. IFP is not, so far. Nobody has a polynomial-time factoring algorithm. Nobody has proved one cannot exist. That sentence is the book’s spine again, now with a name.
The world record in the text is RSA-768, 768 bits, 232 digits, factored on 9 December 2009. The process took about 10 to the 20 operations. Yan says that is about 2000 years on a single-core 2.2 GHz AMD Opteron. “We factored it” still meant a giant collaboration, not a weekend script.
Discrete logs, then the curve remix
Ordinary real logarithms are old. John Napier, 16th century. Given x and y, find k with x^k = y. Over the reals you take ln y over ln x and you get an answer. The Discrete Logarithm Problem is not that.
Over the multiplicative group of units modulo n, you are given x, n, and y. You want k such that y is congruent to x^k mod n. Sometimes k does not exist. Sometimes k is not unique. Yan’s tiny examples modulo 1009 show all three moods.
Elliptic Curve Discrete Logarithm Problem is the same dare on a curve y^2 = x^3 + ax + b. Points add with a line-and-reflect rule. Given k and P, computing Q = kP is easy. Given P and Q, finding k is the hard direction. When the field is small, he finds k = 419 modulo 1009 in a shrug. When the field is huge, Certicom was offering real money. ECCp-97 fell in 1998. ECCp-109 fell in 2002. Bigger curves in the table were still open. The best IFP and DLP algorithms are subexponential. ECDLP did not even have a subexponential attack in this book. That is why your phone likes curves.
Three kinds of hard
He keeps going because RSA is not the only lock. Square roots modulo a composite N are polynomial-time equivalent to IFP. That is why Rabin could build a cryptosystem on square roots in 1979. Quadratic residuosity, deciding if y is a square mod N, also collapses to factoring when N is composite. Shortest Vector Problem in a high-dimensional lattice is its own swamp. LLL finds somewhat short vectors and chokes when the dimension is large, say 100 or more. NTRU and Ajtai-Dwork live there.
Then Yan sorts hardness, and this is the part I wish more explainers copied.
Some problems are provably intractable. They sit in EXP or in spaces we know are beyond P. Some are presumably intractable. NP-complete problems like TSP and SAT. If P equals NP, that pile collapses. Very few working encryption schemes are actually based on NP-complete problems.
Then the third bin. Conjectured intractable. IFP, DLP, ECDLP. They look NP-complete-ish. Nobody proved they are. An algorithm could dump them into P tomorrow. And those three are “essentially the only three intractable problems that are practical and widely used in commercial cryptography.” RSA sits on IFP. That is not a vibe. That is the product.
Modern crypto, with RSA as the sketch
Section 1.4 is why anyone outside a math department is here. Cryptography is secure data over an insecure channel. Alice wants to send M to Bob. Eve can listen. So Alice sends ciphertext C instead. The subject is about 5000 years old. Yan wants modern cryptography, mainly after the 1970s, built on serious math.
Secret-key crypto uses keys that are polynomial-time equivalent. Given encryption key e you can compute decryption key d quickly. Public-key crypto uses keys that are not. Given e, you cannot compute d in polynomial time. You could in exponential time. Not absolutely broken. Just computationally ugly.
RSA is his worked example. Invented in 1977 by Rivest, Shamir, and Adleman, then all at MIT. Plaintext M becomes C congruent to M^e mod n. Ciphertext C becomes M congruent to C^d mod n. The keys satisfy e d congruent to 1 mod phi(n). Euler’s theorem makes the exponents cancel. If you can factor n = p q, you compute phi(n) = (p-1)(q-1), invert e, and read the mail.
RSA also signs by running the keys backward. Signature S is M^d mod n. Anyone checks M congruent to S^e mod n with the public e. Public-key can encrypt and sign.
The last exercise is the one I underlined. Explain why RSA is only computationally unbreakable, not absolutely unbreakable. If you can factor n, or find roots, or get d from e, the scheme dies. None of those are proved impossible. They are just expensive on the computers we have.
The thought I kept after I closed the chapter
This chapter is the book’s whole map in one place. Number theory plus computation gives you a list of problems. PTP is the easy gate. IFP, DLP, and ECDLP are the conjectured walls. Square roots and quadratic residuosity are IFP in costume. Lattices are the other neighborhood. Modern crypto after the 1970s is the decision to build doors that open one way on purpose.
Yan will say hard, infeasible, intractable. Then he will sort those words into proved, presumed, and conjectured. IFP is in the third box. The internet still shops in that box.
Next the book leaves the brochure and starts chapter 2, the actual algebraic toolkit. Groups, rings, fields, divisibility, congruences, curves. The pain is real. At least now I know why he is making us carry it.
Previous: What Number Theory Is Actually About Next: Groups, Rings, and Fields Without the Pain