BSidesCharm 2026 - Why Integer Factorization is F****** Hard: a History

Hello everybody. The mic is working. Is there a mic in the audience? Okay, that concludes the mic check. Um This is what you've signed up for, okay? [laughter] Um thank you so much for coming to my talk. This is my first time speaking at BSides Charm, but I've been coming for a few years. Um double thanks because this is a math talk. Who wants to see a math talk at 4:00? I mean, yes, okay. So, um as extra incentive um if you answer questions during my talk, I'm going to try to pelt you with a rubber chicken uh keychain. It actually does make noise. So, if you want one, um pay attention and answer some questions because uh

there is some math that we're I'm going to lead you through it and it's going to be great. Um but again, thank you so much for coming. I'm very excited to talk about this. I'm going to motivate the talk and then, like I said, get into some math. So, who am I? Um my name is Jessie. My friends call me Dr. J or Jmoney. Um I am actually I'm announcing this publicly for the first time. I am, starting next Monday, going to be a mathematician at Turngate. If you haven't Yes. If you haven't heard of Turngate, you should check them out. They make really cool products. Um I'm also a goon at DEF CON. I'm a serial con

attender. And again, I told you, you're signing up for terrible puns and terrible jokes. Um I am a pun maker extraordinaire. Now, this talk is inspired by a question from my friend uh Bob Weiss. Anybody know Bob? Yeah, okay. So, PW Crack, he's a pen tester, also a goon, crypto nerd, not the coins, but also the coins. And I'll tell you about the inspiration behind this talk as we go on. But, yeah. So, this is your final warning. If you don't want to see math, you can just leave now. >> [laughter] >> Anyway, okay. So, before we get started, the title of my talk is integer factorization is [ __ ] hard a history. But, integer factorization is a problem

that really underpins a number of things in cybersecurity. The probably the most notable of which is cryptography. So, we're going to take a short diversion into cryptography and make sure we're kind of all on the same page. Shannon, Claude Shannon, I call him the Shannonator, very famous mathematician, information theorist, computer scientist. And he, you know, is considered by many to be the father of many things including information theory and cryptography. When a perfectly random string, you can read this, I'm not going to read it to you. But, if you combine a perfectly random string, use a perfectly random string to generate a ciphertext. It's the principle behind the one-time pad. It's proven to be unbreakable. You

can use each key only once. This is part of the problem. But, also your key has to be as long as the message. And, you know, we can squint and say crypto is a solved problem. But, bigger question is, okay, cool, we need these keys and these pads and all of these things in order for crypto to be secure, we still have to have a way to exchange said keys so that we can communicate securely. And, you know, how might you do that besides meeting up in a parking garage and handing each other actual keys? Well, symmetric cryptography is how you do this. You use a single shared secret key for both encryption and decryption.

It makes it fast, but but does require that secret key distribution. So, we have a method for sharing information very securely, but again, how do we get the keys to each other? We're not going to meet up in a super secret dark parking garage deep throat style. We're instead going to use asymmetric cryptography. So, asymmetric cryptography is kind of the opposite. It uses a public key to encrypt, but a separate private key to decrypt, which allows for you to exchange the key securely. And I know I'm going through this very very fast. I want enough time to get through the mathematics. Um and and I'll share these slides afterward if if you're not super familiar with

symmetric and asymmetric cryptography. Um but yeah, anyway, long story short, asymmetric keys are used to securely share symmetric keys. Okay, cool. All right, but the problem is that asymmetric cryptography is this weird kind of math problem where you want it to be something that's very easy to do in one direction, but super hard to do in the opposite direction. If it's easy to generate keys and then easy to like you share the keys and then you want to reverse engineer the keys. If it's easy to do that, then there's no point to secure communications. We need to be able to generate these keys easily, share them, but then make it hard for them to be reverse engineered. So, this

is a kind of a special type of math problem where it's easy in one direction and hard to do in the other. Kind of like baking a cake. You can bake a cake relatively easily in one direction, but it's really hard to undo it. Um I've never done it. Um yeah, so you need some kind of function to generate public and private key pairs. And one such way to do this, there are many such ways. I'm not going to pretend to be an expert in crypto, but I'm I'm to bring up RSA because it's the one that most people have heard of. To generate an RSA public private key pair, you need two very large prime numbers,

P and Q. You then use these to compute a modulus. So, that's just called N is just called the modulus. Uh you take P and you take Q and you multiply them together. And then there's this one other little function that you do some math with and voila, you have your you have your keys. Um you can use primality tests to test whether a number is prime, but if it's not prime, finding the factors that you multiply together to give you that number is actually the very very hard part. So, testing primality is easy, but it's the finding the N and the P and the Q that's the hard part. Um and if there is

an easy way to kind of reverse engineer P and Q, the cryptography breaks down. So, that's one of the motivators. There are tons of other problems that you can point to uh that may motivate why somebody would be interested in integer factorization, um but this is one such thing. Um so, yeah, the long story short is if you want to break the key, undo cryptography, I mean, I'm glossing over some details, but if you need to break the key, you have to factor N. The most efficient way to do that is something called a number field sieve. And this is where my friend PW crack comes in. Because, as you might be able to tell by his name PW crack, he's a big

fan of cracking things. And he wanted to do some research into cracking some types of ciphers and cryptography schemes. And he said, "Jesse, I was off like Googling all this stuff about crypto, and this thing called the general number field sieve kept popping up. And everything that I read about it was way over my head. And they're like, 'Oh, you need some cool math in order to figure out what the GNFS actually does. Um but I don't understand any of that. Can you explain the general number field sieve to me? Now, my PhD is in mathematics, and I went and I looked up the general number field sieve, and my first question to him was, "What the [ __ ] is

the general number field sieve?" >> [laughter] >> Because again, my PhD is in math It was in PDE theory and like control theory. I don't know anything. I mean, I did some algebra, but when I went and I was looking this up, I was like, "Bro, it's going to take me a while for me to understand it and then be able to explain it." But he was very curious about this because, and I think this is a story we're we're sharing, one of the ways to really truly understand a subject or a topic is at least in the hacker world and in the computer world and the math world, take the proof of it, take the code for it,

and pull it apart. Really truly pull it apart. Pull it apart so that you can understand how this how this concept works. And he wanted, you know, "Why don't I have gnfs.py on my laptop?" Because he wanted to really pull it apart and understand how this algorithm works. And it turns out it was going to be much more complicated than that. So, that's actually the question he came to me with was, "Why don't I have gnfs.py on my laptop?" So, I went off on what I would describe a as a a algebraic and number theory sabbatical for 6 months to try to figure out how do I explain this. And there this was the problem and the question. Spoiler alert,

I may or may not have gnfs.py now running on my computer. Um >> [laughter] >> and Okay, we'll get to that. I have I have a demo that we'll do later. So, again, I'm glossing over a ton of crypto and details. Um again, I've already given a disclaimer that crypto is not my area of expertise. I'm, you know, I do a lot of mathematical modeling for cybersecurity, but crypto is the one area, ironically, of mathematics and and cybersecurity that I've not worked in. So, there are going to be things that I probably say or have said in my talk that you're going to that you're sitting there and be like, "Hmm, that's not actually how that

works." Um, but for the math part, which we're about to transition to, I want to get a show of hands and an understanding of of the math knowledge in my audience first. How many of you would say that you have taken a math class at the calculus level or higher? Show of hands. Sick. Let's go. Okay. Um, how many of you have taken um, maybe an abstract algebra class? All right. All right. Great. Please don't make fun of me uh, because I'm going to be going through a lot of modular arithmetic and I'm not going to be going to be talking about the details in algebraic number fields, polynomial fields. I'm going to demonstrate to the

audience how this algorithm works without saying those big scary words, okay? And we're going to get there together. Um, but thank you. So, uh, so now that I have an understanding of the mathematical knowledge in my in my audience, um, I'm going to spend a little while going over the history of integer factorization because that's worth discussing, the status of it, and then we're going to build some mathematical intuition that's going to help us. Okay. So, yeah, I kind of already went over that. Okay. So, brief history of integer factorization, um, there's going to be sprinkled in here some history of crypto- cryptography and cybersecurity as well so that we can see how the two

fields have kind of evolved over time. Now, in the pre-computer era, we have this thing called the sieve of Eratosthenes. Has anybody ever heard of this? Okay, excellent. So, um, Eratosthenes was this really cool, super smart guy a long time ago and he said, "Okay, I want to factor a a number. I want to figure out how it decomposes into its prime factors. How do I do that?" Well, the naive thing to do is to literally write down a big table and say, "Is it divisible by two?" No. And then you mark [clears throat] it out. And then you go to three. Is it divisible by three? No. And then you mark it out. And you do

all the division. And you do all the division. And at the end of it, you get this really nice big table where everything that you didn't cross out makes up your list of prime factors. Um now, Eratosthenes did a lot of math and a lot of physics, but he's actually more famous for something else. Does anyone know? For a chicken. What else Eratosthenes is actually more famous for? If you've seen Cosmos, you may know. The original one. So, Eratosthenes was the first person to actually, that we know of in recorded history, calculate the circumference of the Earth. Mhm. Yep. So, cool guy. He did a lot of stuff. Dabbled in mathematics. Okay. Um Euclid. Euclid's algorithm is an

algorithm for finding the greatest common divisor of two numbers. It may sound counterintuitive. If you want to find the greatest common divisor of two numbers, you actually don't need the whole list. It's actually very fast to find the greatest common divisor. Um but Euclid, again, is known for something else. Does anyone, for a chicken, know? Yes. Yes, zero. Euclid's Elements. Okay, chicken. Okay. All right. They don't fly. >> [laughter] >> That was That was my experiment. Okay. All right, great. [laughter] So, all right. Euclid's Elements. So, Euclid's Elements was a very famous book of geometry where he wrote down, you know, all the the rules of triangles and the rules of parallel lines. And Euclid's parallel postulate is how we

got hyperbolic geometry and whether we assume it or not and all this stuff. So, Euclid was a very smart guy. He got around. Um Fermat. Fermat came about in in like the 1640s. Uh he came up with this identity. It's technically not an identity, this relation uh around this concept called Fermat squares. Um you don't need to understand what that means, but we're going to figure it out here in a few minutes. Actually, that's going to be kind of important. Um Fermat I'm not going to ask necessarily, but Fermat is actually more famous for another problem called Fermat's Last Theorem. Has anybody heard of that one? Yeah, okay. So, yep. The margin is too small for me to write this down. Like I

mean, talk about a cliffhanger, dude. Um now that theorem wasn't actually proven until relatively recently. Um but you notice there's a huge jump here between like 300 BC and 1643. Some people were doing some algebra and integer factorization stuff, but it's not a priority for these people. They're like, "Who cares? Who cares if we can factor two numbers or not? That's not really a priority. It becomes a bigger deal much later." Okay. And then in the 1800s, a metric [ __ ] ton of linear algebra comes about because of this guy. Who's this guy? Gauss, let's go. All right. So, I won't be able to throw a chicken that far, but if you want your chicken, you can come

and get it. Okay. So, that's Carl Friedrich Gauss. Um >> [laughter] >> there you go. Thank you so much. Yay. All right. So, Gauss is a fame very famous mathematician, probably the second most prolific or arguably the first uh since Euler. Um and he is the father of linear algebra. And this is very important because the general number field sieve and all of abstract algebra is really a generalization of linear algebra. So, if it hadn't been for some of his foundational work, um we wouldn't be able to do the things that we do today. Okay. Now we're jumping ahead again. Uh this dude, Derrick Lehmer, he invented a probably the first example of a mechanical sieve.

This thing is amazing. You can actually go and see one in the uh history of computing over in like Silicon Valley. It's a very mechanical box with with knobs and chains hooked up where he actually can crank set you know, set it up and crank and actually factor integers. It was built specifically for factoring integers. It's like all it did. Um and with the invention of this mechanical device, we actually were finally able to factor something up to like 28 digits efficiently. So, we're now in the 1900s and we're up to 28 digits. This is a hard problem. Remember I said it was a very hard problem. Okay, but we're about to go straight into the computer era.

And although the ENIAC was not used for factoring large numbers, um I feel like I need to mention it because that's the one the one time in history that most people are familiar with. So, ENIAC was 1945. And then, um this guy Pollard came along and he wrote this algorithm called Pollard's rho algorithm. Um it's probably the algorithm most close to a number field sieve and gave rise to the quadratic and the general number sieve. Um but this one got us up to 78 digits. So, we're making some progress. And then, in 1981, okay, again, this is the '80s, okay? The quadratic sieve. All the math for the quadratic sieve was written down by this guy, Carl Pomerance.

Now, my talk is based primarily on the work of this guy. Super brilliant mathematician. There is a paper that I'll cite later that he wrote in um the AMS the notices of the American Mathematical Society where he attempted to explain to regular everyday mathematicians um how his quadratic sieve works. Um so a lot of my talk is based on that primarily because finding examples through which to motivate and explain these algorithms is very hard and he did a great job of finding some good examples um that that we can use to demonstrate things. Okay, around that time 1982 RSA 129 is issued. Um you guys have heard of the RSA problems where they give you a really big number and

they say, "Hey, we would love to see somebody try and factor this." Um and then 1988 uh so it took what? 8 years seven seven eight years for the quadratic sieve to be generalized to the number field sieve. So 8 years of really hard math to finally give us the chance to generalize from the quadratic sieve to the number field sieve. I know you guys don't know what those two algorithms are. We're going to learn today, okay? But it took us 8 years to do this, 7 8 years. And then, you know, it naturally comes up because it's on everybody's mind. Um we're in in the early 90s uh the quantum computing era. So finally

in 1994 RSA 129 is factored. Took took a little bit of time. And then um ironically actually at in the same year some people started asking, you know, there these quantum computers um do we even have or is it is it possible for us to factor a large integer using a quantum computer? Is is there an algorithm for such a thing? And this dude Peter said, "Sure you can." >> [laughter] >> All right. So, um so Peter Shor wrote the uh the modern quantum computing algorithm for uh the quantum equivalent or analog for factoring uh large numbers using quantum computers in the same year that RSA-129 was factored. And then huge leaps here, 2001 a quantum

computer finally factored 15. So, we're making leaps. We're making leaps. But you can kind of see parallels, right? It took us a long time to get from like 28 digits to like 78 digits. So, we're slowly moving ahead. And then in 2020 RSA-250 was factored. And then today, based on the most recent research that I did, quantum computers are up to uh 39 bits, okay? So, we're getting there and it's coming, okay? It's coming. There's a lot of material science. Uh the math is there and it's very solid. Like Shor's algorithm has been around since 1994, but it takes a lot of material science for us in physics for us to get, you know, have the hardware catch up.

Okay. Cool. Um so, now that brings us to the status of factorization. I mentioned that the number field sieve is the most efficient algorithm. There's an asterisk there. It's not the algorithm that you'd want to use for all factorization problems. And here's like a a nice little table for you. Um if you are dealing with integers um like if your numbers of size 10 to the four, you're going to just want to use a lookup table. But if you're in the regime of like 10 to the 100, really big numbers, that's when the number field sieve is going to come in handy. Um and actually, going back to the why don't I have gnfs.py on

my computer, Python actually doesn't have a native integer factorization function. I mean, it lives in SciPy. SciPy does, um but up to like 10 to the 9, I think that says. Yeah, there's actually just a look-up table. Because it's way more efficient. So, this is a very niche algorithm for factoring in the regimes that modern cryptography lives in. Okay. Deep breath. This is your last chance. We're going to do some math. Please hang hang in there with me. Would anybody here say that they probably don't have a favorable view of math? And it's okay to admit it. Okay. All right. It's okay. I'm hoping that I can change your mind, because math is super cool.

And we're going to get there together. And the first thing we're going to talk about is modular arithmetic. So, we're going to start with modular arithmetic, and then we're going to build all the way up to the number field sieve in like 30 minutes. Okay? It's going to be great. How many of you have heard of modular arithmetic before? Okay, great. So, for those of you who haven't, we would say that numbers A and B have the same remainder. If they have the same remainder when divided by a smaller number N, they're congruent modulo N. So, we use equality when two numbers are equal, and we can squint and say that these two numbers are

similar if they have the same remainder. So, it's like a looser form of equality, right? So, it's equal in one sense, in the sense that they have the same remainder. So, everybody in this room has done this. We've all used clocks. And if we operate on a 24-hour time, then we're doing modular arithmetic in our head all the time. Um, so, for example, I have it circled there on the clock, uh, 21 and 9 are equivalent mod 12. Because 21 has a remainder of 9 when you divide by 12. Does that make sense? Okay, great. Okay. So, for a chicken, 16 mod 12. Four. Oh, I have so many chickens. Okay, you definitely get a chicken. If you

want a chicken, come get a chicken. Um I have lots of chickens. So, here. Uh I don't want to say it. Okay. And I heard a four over here. So, come get a chicken. I trust you. Okay. Um there's another way to state this. If you take the remainder and subtract it over to the left side, so you have A minus B, those two things should subtract to give you something that's zero mod N. Because if you take the number, subtract the remainder, well, then you have nothing left when you divide it by 12, so it should be zero. So, this is motivating that a lot of the things that you think should be true in

a modular arithmetic world are actually true. Okay. So, um this is just a little property that's going to pop up later. A is going to be equivalent to A minus N mod N. All that is saying is if you take like that clock and you rotate it around one full circle, you haven't really changed anything. So, 12 21 and nine are zero mod 12. If you subtract that modulus, nothing really changes. All of those numbers are going to be equivalent. Okay. Cool. All right. Um one more fact about modular arithmetic that I'm probably just going to ask you to trust me on. Um I'm not going to prove it for you. If you have two relations like this, so

A is equivalent to B mod N, C is equivalent to D mod N, you have the two relations, multiplication works the way that you think it should. You can take A and C, multiply them, B and D, and multiply them, and it's they're equivalent mod N. So, again, I'm not going to prove that to you, but you would think that this would work. The multiplication would work mod in modular arithmetic and it does. So, just as an example, we just did this. 16 is 4 mod 12, 21 is 9 mod 12. Um if you multiply those two things out, 16 * 21 should be equivalent to 4 * 9 and it actually is. Actually, if you're

paying attention, that last relation, the 28 and 12 and the 3 and 12, that simplifies one more time. Those two things are equivalent to what mod 12? Zero. Yes, because the value on the left side has a 12 in it, the value on the right side has a 12 in it. So, it should be zero because it's e- it's evenly divisible by 12. 12 appears in it. So, when you do the division, there should be nothing left over, right? Very good. >> [clears throat] >> Awesome. All right. I'm going to time out right here. Is anybody absolutely completely lost? All right, Jason. Great. >> [laughter] >> All right. Well, see me after class. Okay. [laughter]

Um you can do clock math, you'll be fine. Yes. Um yeah. Yeah, I think so. Is there another question? Okay. All right. Cool. We're hanging out with the math and now we're going to build up to the Neverfield theorem. Okay. Another hacker thing, mathematicians are hackers, guys. We really are. We don't like solving hard problems. We want to do things to make our problems look easy. There is a trick here. Let's say I asked you to factor 8051. I'm going to pause. Sometimes people see the trick immediately. Well, one is not a prime factor, though. One is not a prime. So, if I want you to find the prime factorization, so that's a also a very hacker thing to do. Um but

uh if I wanted you to find the prime factorization of 8051, I'm going to make it look like a different problem. What if I wrote 8051 like this? Now, does anybody see it? Yeah, let's go, chicken. All right. Okay, that one that one landed. Okay, so they astutely pointed out that this is now a difference of squares. And we know the difference of squares formula. So, now I can write the left side, the 8100 as 90 squared, and I can write 49 as 7 squared. And in algebra, this factors. So nice. Oh my gosh, guys. Look. How cool is that, right? That's a little trick. You know that this this question, factoring numbers like this, this is a common type

of problem in like math Olympiad stuff. They give you a crazy number, and they're like, "Find the prime factorizations." And then they give you like 10 minutes to do it. Shh. No. It's crazy [laughter] stuff. Crazy stuff. Okay so a clever trick. We took a hard problem, and we made it look like an easier one. And now you might be wondering, "Can I do this all the time?" Yes. Every odd integer with a factorization can actually be written as the difference of two squares. What the [ __ ] Talk What? Okay, somebody smarter than me had to prove this. And his name is Fermat. Mhm, we met this guy before, right? So, Fermat did this and he proved that you

can always do this. So, if I do have a number that I'm really trying to factor, a reasonable thing to ask is, "Well, can I write it as the difference of two squares?" Okay? We know how to solve that. Okay? Yeah. So, I might just want to write it this way. So, if I want to factor n, which may be a very large number that I'm interested in factoring, I can write it as a squared minus b squared. So, then I'm really just looking for some a for which a squared minus n is a square. All I've done is just re- rearranged that. I'm just saying a squared minus n is b squared, okay? That's all I'm That's the b we're

looking for. Okay. And you can see this in our previous example. n is 8051, a is 90, b is 7, and look, it worked out. So, we have our um a squared minus n, the 90 minus 8051, and we get 7 squared. Perfect. Awesome. And then we can use those formulas that Fermat came up with, and we get the answer that we got previously just by writing it as the difference of squares. Okay.

Yes. Okay. All right. So, there's one more trick we can do. Remember, we like clever tricks. Um finding those differences of squares is an easier problem, but it's still not the easiest problem. So, maybe I can use these difference of squares that Fermat came up with. Now, Fermat did this for equality, but he also did this, I showed it earlier on the slide. He also did it for modular arithmetic. So, let's investigate what happens there. Okay? I'm going to skip a little bit of math here, but I'm going to rely on your intuition. If you have this difference that's equivalent to zero mod n, that means that it's evenly divisible by n. So, when you split it up

this way, a little bit of n has to be in one part and a little bit of n has to be in the other part. So, all we're kind of doing is taking that modulus, that n, and we're kind of splitting it up into the two factors. Okay? So, intuitively this kind of makes sense that a little bit of n is over here and a little bit of n is over here. Um another thing I'm going to gloss over a little bit. I talked about the greatest common factor earlier, um but I'm going to ask you to take me on faith on this one. That greatest common factor of a minus b and n is actually going to

be a non-trivial factor of n. Um and by non-trivial I mean not one. Uh the gentleman asked earlier about it being one. It's going to actually be a non-trivial factor. So, we this is It takes a lot of mathematical proof actually, but this does give you a an honest-to-goodness prime factor. Okay? So, essentially all I'm saying here is we're going to use modular arithmetic to punt to this greatest common factor. Again, there's some math here. Just take me on faith on this one, okay? The greatest common factor is easy. So, that's the problem we're going to be punting to. Okay. Euclid's over here like, "Say less. I can help you." All right. So, the previous example that I worked with,

a and b were very easy. Now, we know that we can always write an integer as the difference of two squares. Great. Um but for 8051 example, a and b were easy. So, the first question is can we always do this? The second question is how hard is this to do? Yes?

Well, if it's even, then you know one of them. It's two. So, then take two and divide it out, and then you're left with an odd one. So, the two the even ones are easy. Yeah, the even ones are easy. That is an excellent question. You get a cheeky. Okay. They don't fly. That actually is a very good question. Um Does everybody understand that why that why we don't care about the even ones? Because as soon as you just take two out of it, whatever. All we're left with are the odd ones. You pull the twos out until there's only odds left. Okay. So, yes, we can always do this. How hard is it to do?

Now, I was nice. I'm a nice math teacher. I went through and I actually built a table for you showing some of the values. Remember, we want a value of B, we want this A squared minus like 2041, we want that to be a square. Okay? So, I'm short. I apologize for my genetics. Um but here's the table. Here's our A squared minus N. We want this value over here to be a square. All right? You follow me? Do we have any? Huh, we don't. Crap. Oh, no. What are we going to do? Now, that's a small table. There's only five values there, six. I can count. Um yeah. Fermat's over here like, "That's cap, dog. I can't do this. I need a

square." But let's let's take each of these equivalencies and investigate them a a bit further, okay? So, I'm just going to use the modular arithmetic from earlier. 46 squared is um has a remainder of 75 when you divide it by that N value, okay? I'm just writing it out in modular arithmetic, okay? Let's look at maybe another one. 47. 47 squared, if this were a perfect world, we could square 47 and be done, but we're not. But, when you divide it by 2041, you get 168. And so on and so forth. Okay. You can do this for the 46, 47, 49, and 51. Okay. Remember I said we like easy tricks and we like to make things look

like problems that we know how to solve. What happens if I punt to the modular arithmetic multiplication thing from earlier? Okay? I'm going to take this side and I'm going to multiply them together. And I'm going to take this side and I'm going to multiply them together. I I have written the prime factorizations of your remainders for a reason. What happens if I go through and I multiply all of these equations together? Does anyone notice anything about the exponents? YES. YEAH, LET'S GO! OH MY GOD! OKAY. ALL RIGHT. SO, OKAY. SO, when you chicken So, when you multiply all of these together, it gives me chills. You get a square. That's what we were looking for the

whole time. It's a square. So, we know that we can always do this. And the next question is how hard is this? Well, we just did it for 2041. Now, I picked this number for a very particular reason.

So now you have Remember I there was some math that got left over. There's a greatest common factor. We have our a minus b squared 2041. You solve it using the greatest common factor. Some of you are probably familiar with that algorithm, whatever. You're pointing to greatest common factor, but the greatest common factor is 13 and it actually turns out you can factor 2041 as 13 * 157. So I'm going to tell I'm going to hit this one more time to make sure that you understand. We don't just stop at one equivalent. We find all the ones that we need in order to give us a perfect square when we multiply them all together. That's so cool.

That's so cool. Again, some super smart mathematicians figured out that you can do this. Okay. Now, would you believe me if I said Yeah, right. I get that. That is how the quadratic number field sieve works. And everybody in this room just factored their first number using the quadratic number field sieve. >> [applause] >> Tickets for everybody. So these were images that ChatGPT thought were images of people who are celebrating factoring their first number using the quadratic number field sieve. There will be drinks and cake later. We can celebrate together then. Okay, breaking it down one more time. In our algorithm, we had a bunch of remainders who just happened to have as their greatest factor seven.

So, if you look at the how all those remainders factor over there, the biggest one the biggest factor is seven. In the quadratic number field sieve algorithm, this has a definition. It is B, and it is the bound on smoothness. In number theory and algebra, we say that a number is B-smooth if all of its prime factors are less than or equal to B. So, in the previous example, B is seven. And smoothness for me as a mathematician intuitively it kind of makes sense why it would be smooth because you can think of a number almost like breaking down, like it falls apart into these factors, and it's very nice and soft and smooth. It's not like

big and blocky, you know, it's nice and smooth. It has small prime factors. Um we find a sequence of A sub I's that's for which that modular arithmetic works, okay? For us in our example, those were 46, 47, 49, 50. All of them are are seven-smooth, they're B-smooth. Find the prime factorizations, find a subset of these which multiply together to give you a square. We did this. You factor and compute the GCF, and then you profit. That's This is basically exactly how this algorithm works, and we just did it together. Yeah, surprised this works? I was. I was like, "Wow, this is such a cool trick." All these mathematicians come up with all these cool tricks. I encourage

you to go to the Wikipedia page on the quadratic number field sieve and just kind of read it. There's going to be a lot of math there that obviously I didn't go into, but there's special cases, there's optimizations, there's things you can do depending on the subspace of numbers you're working in, but it still blows my mind this that this works. Um the catch and why um this works and why cryptography doesn't break down is that we are on a precipice. These smooth numbers are dense enough in our number field to be present. We can find them. We just did. But they're not so dense that they're super easy to find. They were easy to find in our example

because I engineered it that way. So, we've gone from asking, "Can we always do this? What if we did it this way? How hard is it to do this?" It turns out it's kind of hard. You have a question.

Um so, actually you start with um in the algorithm you set B and then it just goes and finds it like searches that entire space and does all the multiplications and permutations and combinations to find the ones that get you what you need. So, you kind of have to have an intuitive knowledge beforehand of what B should be, which is tricky, right? But yeah, so when I say we live on a precipice, my god, do we live on a precipice. These numbers are smooth, but they're not that or dense, but they're not that dense. And no, I'm not knocking the numbers, they just they're just, you know, they're just like sprinkled through. Okay. Now, you may have also noticed it was

called the quadratic sieve. I thought we were talking about the general number field sieve or the number field sieve. Why is it called the quadratic number field sieve? Well, it's because that polynomial that we solved that B squared and A and A squared and N is quadratic. Um and you generalize this. So, when you go from the quadratic number field sieve to the general number field sieve, you completely yoink and yeet, I guess, the the requirement that this polynomial you're trying you're trying to solve is a quadratic. So, the GNFS pulls that off. If you actually go through and look at papers, they've got all these like big polynomials that you're trying to solve. Um, but nobody ever said it had

to be a quadratic. That was just what we did for our example to motivate the the quadratic number field sieve. Okay. But, as soon as you generalize this, the math gets hard. Uh, it gets crazy hard. Um, and that's one reason why I'm going to probably stop at the quadratic number field sieve and tell you how to generalize. I I'm not going to do it for you. As most most mathematicians would say, the proof is trivial left as an exercise to the reader. >> [laughter] >> The proof is trivial and left as an exercise to the reader. Um, I'm not scarred. Um, anyway, okay. So, um, yeah, so the the And then, okay, why would we

even want to go beyond quadratics? Well, when your numbers are in this regime that they're very very very big, um, the bottleneck isn't the math. It's actually the hunting. Like I said, we kind of live on this precipice. Finding those smooth numbers becomes hard because as n grows, uh, your b kind of has to you're going to be looking for these numbers to multiply together to give you the right combination for a very very very long time. Um, and if you use a higher degree polynomial, um, your output stays small because it takes a smaller number to multiply seven times to get a bigger number. Um, you can find these relations a little bit faster. Uh,

the growth, if you're asking or curious about optimiz- optimization and and and um, uh, operating time, uh, computational time, um, for the quadratic number field sieve, it's on the order of like in the square root of n. Um, when you generalize to other polynomials, it becomes cube root of n, which sounds like it's not a huge optimization, but it is. Um, and no, if you generalize the degree of your polynomial above three, that bound doesn't actually get better because you end up with two competing You have to end up solving a bunch of linear algebra, and the linear algebra becomes the bottleneck then instead of the norm of the polynomial. Anyway, um okay. So, um, I know I'm coming up on time.

Uh, here's a numerical example. I already went over, um, B-smooth. Another mathematician who's super smart actually went through to calculate what's the probability that a random number near M, so where M is just some integer. Let Let's say you had a target and you wanted to search around that, like you grabbed in, you wanted to find a smooth a B-smooth number. Um, it's approximately log of M over log of B. So, um, you can skip the math, just look at the example. So, for the quadratic quadratic the quadratic The quadratic sieve, I didn't come up with that by myself. That was a slip. Um, if your number has 30 digits, and let's say your smoothness bound is like

10,000. So, you're a you have 30-digit number, huge, 10 to the 30, and your bound on smoothness is 10,000. We're working with seven. Like, in the real world, B is huge. Um, only 0.7% of candidate numbers you test are smooth. So, that's one out of every 140 numbers you could pick at random. Um, if you use the general number field sieve, that jumps up to 10%. So, it's a it's a pretty significant gain, but it's still hard to find these numbers. Okay? And then, in a bigger example, this really motivates and brings it home. If your number you're trying to factor is 150 digits and you use that same B um in the quadratic sieve, about one out of

every 10 to the 24 numbers you check will be smooth. That is huge. But if you generalize to the number field sieve, the general number field sieve, it becomes 10 to the 14, which is manageable. So, it finds them about 10 billion times more often. That's crazy. Um so, if you were to use the quadratic sieve to try to factor such a number, you would have to test more numbers than there are atoms in the observable universe. That's why we don't use it. We generalize to something um different. Yeah so anyway. Um and now, just a very quick demo. Again, I know I'm I'm basically up on time, but uh to go back to Bob's

question, minimize this stuff. Um no, not that one. You can see all my cloud. All my clouding. No, it's this. I will find it. All right. So, this organization called Cado, it's um in a university or organization in France, Ferma, France. A lot of factorization work has been done in France. Um these awesome mathematicians, computer scientists have written basically gnfs.py and you can run it on your computer. So, it's hard to see, I know, cuz it's dark dark mode users unite. Um in here is a 65-digit number. We're going to factor it and I built a little front end here to kind of show you what it's doing in the background. Um it's picking a

polynomial. It's going through and starting to sieve and find the smooth numbers. Um let's see. So, it's testing It found some candidate numbers, like 95,000 of them. It's testing them. Um, we'll see how quickly. Oh, boom, there it is. Okay, so a 65-digit number, it took us 21 seconds, and then you take the two factors down there, you multiply them together, check your work. Um, and that indeed does work. So, um, so now you have instead of mathematicians in the 1800s trying to write down all these numbers and figure it out, I can just say, "Hey Claude gnfs.py." And uh, and now you have an algorithm that can run. Now, it is it is kind of

funny, when I was um, I the I didn't use Claude to write Cato Cato NFS. Um, Cato wrote did Cato NFS, uh, but when I was asking Claude, I was trying to find a candidate number that would take a few seconds to factor. Claude misinterpreted me and thought that I was asking it to write a GNFS algorithm, and even Claude was like, "I have to stop you. Do you understand what it is that you were asking me to do?" And I was like, "Whoa, there has been a misunderstanding. I just want you to give me a number. I don't want you to actually write the algorithm." Um, and then I guess, again, I'm up on time,

but the only other thing I would show is um, So, yeah, can we do this? Yes, you can do it in Python, but why would you? Would you write a web browser in Excel? Don't. Don't you do it. Would you write Photoshop on a TI-83? You could. You could, but would you? And other fun questions we ask ourselves regularly. Um, most factorization algorithms are not done in object-oriented uh, programming languages. They are written in like C and Fortran. Um, if anyone is wondering why there's an Audi in the parking lot with a Fortran license plate, that's me. I'm a dweeb. Um Um but anyway, I really appreciate your time. I hope the point of this talk was

not for everybody to leave here an expert in factoring numbers. I wanted to motivate this and give you a little bit of intuition for how the math works and maybe help convince you that there are other cool mathematical topics related to cybersecurity that are worth digging into and it might lead to a cool conference talk. So, thank you to the organizers for having me. Thanks to my husband and Carl Pomerantz for figuring this out. I didn't change the Colonel Con part, but this is that we just presented at Colonel Con like 2 weeks ago. Thanks to Charm. Really appreciate it. Happy to be here and I'm happy to take any questions. >> [applause]

[applause] >> Again, I'm so appreciative to everybody coming for a math talk. I know it probably sounded a little different than other cyber talks here at the Con, but it is related and the math in cyber is so cool. And so, if anybody ever runs across a problem, they're like, "Man, I wish I understood more of the math behind this." Look me up. I'm on the socials. You know, find me. Let's dissect it together. We'll figure it out. Yeah, so thanks a lot. Yeah. Come get your chickens if you didn't already.