Why integer factorization is so f***ing hard: a history

No ratings

Presented at JawnCon 0x2 by

Integer factorization (breaking down a whole number into its prime factors) is an action that many of us (and certainly computers) do every day, but which we take for granted. Figuring out if a number is prime and decomposing a composite number into its prime factors is actually pretty hard... Have you ever paused to ask why? This talk traces the history of integer factorization, from Fermat's 17th-century breakthrough to the status of integer factorization and the General Number Field Sieve (GNFS). We'll watch trial division fail spectacularly, see how the Quadratic Sieve made 100-digit ""impossible to factor"" numbers trivial, and witness the moment distributed computing first tasted blood with RSA-130. We will eventually work our way up to the GNFS-an algorithm so elegant (or maybe... bizarre?) it operates in parallel mathematical universes, exploiting algebraic structures that can be hard to wrap your mind around (but we'll try our best!). We'll demystify how this mathematical monster works without drowning in theory, explore why it represents the current ""final boss"" of classical factoring, and discuss why quantum computers might be the only way to level up from here. Along the way, I plan to discuss notable moments in cryptographic history, and the relationship between integer factorization algorithms and topics in cybersecurity. As a general warning, there WILL be mathematics in this talk... but there will also be history, hacking, and horseplay. No prior number theory or mathematical experience required - just a healthy respect for algorithms and some patience. I promise this talk will be way cooler than your high school algebra class (and yes, I realize how low that bar might already be).