Dmitry Khovratovich - Factoring Integers

So, I'll talk today about um modern methods of factoring. Uh well, unfortunately, they are not very modern because the main advances in this uh direction were in '80s and beginning of '90s. And just the recent factorization records that we have seen are just application of these uh methods to uh increasing computer power computing power that is in hands of researchers, like academicians, and so on. So, I'll try to give some overview without going deep into math, just a bit deep so that if you later would like to learn a bit more, uh this material may uh serve like a basis. But, I will also publish uh some uh additional material uh on the Google Drive with some simple explanations of number field sieve and similar methods uh which can be helpful if we in the future decide to um explore uh this harder perspective of these things in more details.

Okay. So, feel free to ask uh questions in uh in between. So, uh what's actually the problem of factoring? Let's formulate it. And it is So, suppose we have uh a big number, capital N, uh which has n bits, uh small n.

And uh the problem of factoring is to find its prime decomposition. So, find its uh factorization into prime powers, and this factorization for integers is known to be unique up to the order of factors, but there cannot be different decompositions uh with the same order. Uh this is actually the property that factorization is unique is important because it doesn't exist everywhere. And for example, in fields it's of course not the case because in fields every element is divisible by anything else and in fields every field element can be present and have like multiple infinite number of representations. But it's property of the ring of integers of the ring of polynomials and of some other so called Dedekind domains which includes some funny algebraic fields which are basically the fields where you extension fields where you add some roots of certain polynomials or some square roots of negative numbers and so on.

There are some fancy sets where factorization is unique and this is used some extent in factoring methods but not everywhere. That's because and because of that many well even though for example discrete logarithm problem is related but in the sets where there is no unique factorization many methods do not really apply there. Okay. Let's go on. So if the number cannot be factored it's called prime number and it's relatively easy so it's there exist deterministic algorithms which are polynomial in the number of bits that determines if number is prime.

Factoring is of course NP problem because you can quickly check that if factorization is correct but it's not known to be NP hard and I think as far as I understand many people believe that it's not NP hard. And due to that algorithms faster than just pure exponential exist but on the other hand purely polynomial algorithms do not exist so we do not know where where it's really is this factoring problem. Uh oh, how how can we simply factor? So, we just go over all uh numbers up to the square root of n, and if number is prime, we test if it divides uh n, and uh of course, when we exhaust all the numbers up to the square root, we exhaust all the uh all the uh numbers, all the factors. And what what remains, it can be bigger than square root of n, but it it must be prime.

Uh it must be a single prime that remains. And complexity of this is about square root of n. That's trivial methods. Uh um a bit more interesting method that related to um methods I will discuss is the following. So, suppose you generate uh two numbers, x and y, and then you test if x squared equals y squared modulo the number that you're going to factor.

Why is this equation interesting? Because if this happens, if this holds, then if we like put y squared to the left side and apply the simple formula, then we see that there is a product of numbers that equals zero modulo uh the modulo n, so modulo the number we try to factor. And there is certain chance, actually quite high chance, that if we that uh either of this is uh actually not n itself, but some factor of n. And if we compute the GCD of x minus y and n or x plus y and n, then it's very likely that we actually get a factor of n. Otherwise, uh so if this doesn't hold, then we go to step one and generate a new numbers.

But in general, if if this holds, then we almost win. Uh with probably usually with probability more than 1/2, so if these numbers are small enough. And by proper arranging X and Y, we can make the complexity about square root of N again. Why is this important? This is important because I will show how we can generate X and Y in much more interesting way.

And that's actually how factoring becomes easier than square root. How exactly? Okay. So, we generate X and Y so that the equation is more likely to hold. And this is in the advanced factoring methods.

Now, there is some interesting stuff. Suppose that for some number X, XI bigger than the square root, it happens that if we compute the square of X and take it modulo N, and we have some number Z, then it factors into powers of 2, 3, and 5. Just 2, 3, and 5. So, some 2 to the some power of A, AI, 3 to some power of BI, and 5 to some power of CI. So, we can actually factor Z.

So, we try for every Z that we compute this way if it factors into this into 2, 3, and 5. And what's interesting interesting that if we collect sufficiently many of such numbers and So, if you have three factors, then if you Yeah, then I need four such relations. Why is that? Because if I collect four different relations like this with sufficiently big X, bigger than square root, then what happens if I have four such relations? I can compose a matrix where the powers of uh uh this prime factors are in the matrix.

And then I seek for linear combination mode two. Modulo two. Uh, why modulo two? Because this basically means if uh, some for example if some column uh, if we sum up uh, for example some rows and there is zero modulo two, this basically means that this uh, numbers sum to some even number. And this basically means that if I multiply uh, this ZI, ZJ, ZK together if I multiply them up then uh, this uh, exponents uh, they will add up this will be even number and this means that this will become a square.

Uh, and the same will happen um, for three. So if uh, this we uh, collect sufficiently many elements in this matrix uh, then uh, with big chance there is of course a linear dependency modulo two uh, and uh, there exists uh, a sum of rows with alpha, beta, gamma and delta uh, zero or one so that uh, this uh, linear combination gives 000 uh, modulo two. If this happens then uh, for example yeah this there exists this alpha, beta, gamma, delta uh, then we know that if we take uh, XI to the alpha, XJ to the beta, X gamma to uh, XK to the gamma, XL to the beta to delta then the square root of this guys uh, the the the square of this product if we put this here then uh, it will translate to some when everything sums up so in this vector we'll get so some U2 here, 2 U2 here, 2 U3 here, 2 U5 uh, basically here and if modulo 2 this all gives all zeros and then uh, this means that uh, we have now uh, the product of squares into some uh, power. So instead of having uh, 2 to the something 3 to the something 5 to the something I have 4 uh, to the something and so on and this basically means that this is the square and this is the square. Both are squares and we we get this V and W this way and uh, uh, we get this equation that uh, we were looking for.

So there for example uh, for example suppose that we uh, would like to factor number 143. Uh, and I take uh, square root of 143 which is uh, smaller than uh, 12 and I uh, compute powers of uh, this number so I slightly increase and compute uh, 14 squared 15 squared and 16 squared they do not they're not divisible by 2 3 and 5 but 17 squared is just 3 19 squared is 75 uh, 21 squared is uh, if I take all this modulo 133 and 21 squared is uh, uh, yeah 441 equal 12 uh, which is 2 * 3 squared and so on and uh, if we note uh, then uh, so if you look at this then uh, if we uh, Uh, multiply 17 by 19, then uh, their squares for their squares will happen that we'll have 3 by 3 and 5 squared, too. So, 17 * 19 squared equal to 3 squared 5 squared. Uh, which basically means that 30 if we take this modulo 143, we have that 37 squared equal 15 squared. We put this to the left side.

Uh, apply simple formula and see that there is indeed equal equal zero modulo 143. We compute GCD and we have 11. And 11 is the factor of 143. Uh, any questions so far? Well, this is super cool because super simple.

Um, one question I have is is it still the case that the probability that the V and W kind of won't be equal? Or like the GCD just doesn't give you any prime? Yes, there is a chance that GCD doesn't give you, but in practice it's it's quite low. So, I think with probability this 1/2. Uh, if you get this like equation with random V and W, if they are both sufficiently small, then I think with with very high probability you have you get an actual factor.

And are are these like provable things or like heuristics? Yeah, I think this is provable. I think for for sufficiently small V and W for which this happens, you can rigorously prove that the probability is very high. And what do you mean by sufficiently small? Uh, sufficiently small I think smaller than N.

Uh, some Well, if they are like close to square root or if one of them is closer to square root uh, then I think you can bound this. I I've seen some estimates how you can compute it. I think it's widely assumed that the probability is about 1/2 that you get correcting because actually it may happen that uh, this you you don't get uh, you don't get the answer only if uh, only if uh, one of this is uh, bigger is uh, uh, multiple of n, right? So, if if this is n or if it's 2n or 3n, but if x and y are both smaller than n, then probability of this is small, right? I see.

Okay. Okay. So, this method is very nice, but the problem is that the number the fraction of numbers uh, divisible by 2, 3, and 5 is very small. And we have to adjust this method somehow to to benefit from this. So, the matrix part that we like looked for linear dependency is very simple because only three factors, but we have tested.

So, if you see that I for example tested uh, 20 numbers and only in four cases I got nice uh, decomposition. Uh, so the smart method of factoring uh, introduced what's called uh, smoothness. And we call number zero B smooth if all its factors are smaller than B or like smaller or equal to B. Uh, and in in our case if we say that it's like smaller than B, then clearly the previous case when we consider only 2, 3, and 5, we talk about uh, 6 smoothness. But of course, we can consider bigger uh, smoothness value.

So, how this is how this works, we take some X. I'll tell later how we take this X. We compute X squared modulo Z and test if it's B smooth. So, we select some number B and test if it's B smooth. If yes, we add it to our table, and this is called sieving.

If we find uh, about B, well, B over logarithm of B, uh, to be formally. Uh, then if you find about B such X, then we have a matrix with uh, so if you can so if it's B smooth, then in our table of exponents, uh, there are at most uh, B uh, columns because every column correspond to exponent of some prime. And there are at most B primes here in this interval, so in our matrix, there will be uh, B columns. B over ln B. Uh, and if you find about B such X, then after applying, for example, Gaussian elimination to the matrix, then we can find some linear dependency.

And basically, it will see that uh, pretty much the same way that some product of squares, so product of squares gives you uh, another square. And uh, when we aggregate these guys and take it modulo N, then we have X squared equal Y squared, and we are uh, done. Um, so what's the complexity of this uh, principle? So, basically, the matrix step, uh, we work with matrix B * B, but interesting that we don't need B cube uh operations to find linear dependency, to find basically an element of the kernel, because the matrix is very sparse. And interesting that there are special algorithms called block Wiedemann or block Lanczos algorithms for sparse matrices that find uh uh elements of care of kernel of uh sparse matrix.

And usually um so, this algorithms works in about B square times well, the sparsity somehow. So, it's about B square and this is one step that of course can be improved in hardware. So, so there will be improvement to sieving, but the matrix step I can already tell that there are several suggestions how to make this this thing much faster and much more efficient in hardware. So, this can be considered independently of the sieving part, the very complex part of number field sieve, but this thing is theoretically very simple and can be explored I think relatively easy how fast it can be on custom hardware to run this algorithm or modifications of this algorithm that are suitable for multiple cores or something like this. So, what about sieving step?

The sieving step, of course, all depends on this number Z. Because uh the smoothness probability for a number, it depends how big the number is. Because clearly the if the number is smaller than B, then probability that it's B smooth is one. But when it increases, there is a very big chance that it has a big prime factor, and because of that uh more and more numbers are not B-smooth. So, the probability decreases significantly uh with the grow as that grows.

And uh we have to take this into account. So, um the sieving for sieving, we need uh B uh such numbers. And uh to now basically the uh complexity to find one number is uh the fraction of B-smooth numbers uh I among our outputs. Uh for given that, and uh multiplied by the complexity of test. Uh so, how how expensive it is to test that that is smooth.

But actually, uh what's really interesting that uh the modern sieving methods, they are quite fast in a smooth test, and they uh may take into account the benefit of the fact that uh we created Z in very special way, and the amortized cost of smoothness uh test is is very low. So, what's what's really really important here is this probability. Uh the probability that this number is smooth, and the smaller we can make this number, the bigger probability it is that it is B-smooth. And uh of course, since the magic step is about of B square, we would like that this be of B square uh to uh so that both steps are balanced. And uh if we uh make the test complexity uh almost one or close to one, uh then the trade-off is where the smoothness probability is uh one over B.

But it of course depends how big Z is. So, uh the smaller Z is, the bigger we can take this uh B, and the bigger numbers we can uh basically factor. Uh questions so far? Yeah, so actually um I like to stress that this smoothness uh property is very very important thing. It's uh actually why uh factoring is uh much faster than brute force uh factoring that's square root of n is because we can uh in integers there is this exist this notion of uh uh smoothness and there are uh numbers that factor uh this way.

So in in other sets we don't have this notion and because of that uh problems similar to factoring like discrete log are much uh harder there. So this is the crucial property uh for factoring. And what's a typical size of uh B that we're talking about if we want to factor like uh 800-bit number or something? Uh so you see that we make uh both uh we we would like for a trade-off we would like that uh the time of both steps is O of B squared. So if you can spend 2 to the 60 uh 2 to the 60 uh time uh then your B is 2 to the 30 clearly.

All right, okay. Now I understand why the matrix is sparse. Yes, so um numbers are like uh 30 uh 2 to the 30 so it's 30 bits and of course uh uh they have don't have too many prime factors so they can have like average number I think in recent records like 50 or 100 or something. Uh not terribly many. So, compared to the size of the matrix, uh the number of uh non-zeros is very small, like one.

Yeah, you can mention like 100 over 2 to the 30. Very small. So, you mentioned that there was some suggestions to use ASICs for the the matrix step. What about the sieving step? Yeah, so what about the sieving step?

I'll have to go how exactly sieving uh works uh in uh some in two algorithms in quadratic sieve and number field sieve, and then I will explain so how uh hardware will help there. So, about the smoothness, uh how we get actually this uh faster factoring this than faster than square root. Uh it's uh for example, if uh B is constant, like six we have used, then probability that uh the number is B smooth is uh uh one over n to the uh uh logarithm of B. Uh but uh if uh if B is uh this big, like uh exponent of square root of logarithm, so which is not like logarithm by half, but square root of logarithm, then the probability that the number smooth is one over square root of B. And because of that, uh if we uh to find B such numbers, we spend B to the 3 over 2 time, and the matrix step is B squared.

So, by further tuning this number, we can arrange that uh numbers are factored with about this complexity. Uh how uh I will be a more precise in the uh, next algorithm, which is called quadratic sieve. So, what's interesting about quadratic sieve is it can be explained relatively uh, trivially compared to number field sieve. So, what's in the quadratic sieve, what we are doing? So, the first nice step is how we select our X.

If we select X close to square root of N, so square root plus some epsilon. So, of course this is the uh, integer part of square root. Then, if we compute X square modulo N, then if we took N square modulo N, so this will become almost zero. And what remains is uh, epsilon square and two epsilon uh, times square root of N. This makes uh, our number Z uh, of size about square root of N.

And because of that, it's much more likely that it's B smooth uh, compared to random Z modulo N, because number that is uh, half of digits of N uh, is much more likely to be B smooth. So, uh, we're going to find uh, all of B over logarithm B such X. We construct our equality of square quotients and we are done. But, uh, how to test smoothness? And for smoothness test, it's uh, interesting.

So, we basically uh, try X and we have arithmetic progression here. So, if we test B square, then we take uh, square root of N uh, plus one, square root of N plus two and so on plus B square. And how we work with that? So, why it's called quadratic sieve? Uh, we test bit smoothness as follows.

So, suppose that let take some prime uh, smaller than B. Uh then we solve an equation that X square minus N equals zero modulo Q. Uh and for X somewhat closer to square root. And uh we can solve it because uh in uh if it's prime, then such equations uh solved easily. There are polynomial algorithms to do that.

And if we solve that, then for any K, we have that if we add to X Q or 2Q or 3Q, then modulo Q, there will be all the same, meaning that if Q of X divisible by Q, that means that Q of X plus KQ is also divisible by Q. And coming back to uh the previous slide, so remember we constructed uh X uh square minus N of four X, which is arithmetic progression. And this means that for some first element, so how to find smooth numbers here? We uh take one number uh one prime, and we find here uh the root. Uh we find we solve for some X in the beginning this equation X square minus N equals zero modulo Q.

We solve it. And then, so suppose this this this true for this number. Uh and uh and then this means that if this is divisible by Q, then we can add to the argument any multiple of Q, and with uh like an arithmetic progression in equal gaps, the outputs of our polynomial will be divisible by Q. And we can divide it by Q like Eratosthenes sieve, and eventually, if we repeat this many, many times for different Q, some numbers will boil down to zero to one because we factor out all the prime numbers of them. So, how this sieving works is that we in in a very long array, we find some number to start with, and then every Q's number we divide by Q.

Uh and we know it will be divisible. And we repeat this for for all the prime numbers, and eventually what remains uh are uh there must be about B numbers out of this square that are ones, and these guys will be uh B-smooth. Questions? I wasn't really able to follow the last few steps. Okay, so uh do you want me to repeat, or you want later to uh take a look into the following?

I think I get it. I think uh the idea here is basically that instead of like just sequentially trying random numbers, what you do is you sequentially try numbers that are multiples of some uh smooth number, and so that way you have a uh of like some small and medium-sized uh smooth number, and that way you have a higher chance of hitting something where the entire number Uh yes, that's more or less the case. Uh so, to summarize it shortly, we find one number here that is divisible by prime by solving an equation. And then we know that clarify, we do that for each prime less than B. Yes.

That Oh, I see. Mhm. For each prime less than B. Okay. And then So, we have the list we have the list of all these numbers that are squares of root n plus one up to root n plus b squared.

Yes. Mhm. Okay. And among them some some of them are divisible by by a prime. We know that we we have found uh one such number.

So, we we solve this modulo and uh we find such x. So, this is easy to find such x. Mhm. This means that for any prime it's easy to find in this sequence which ones are divisible by this prime. So, So, this is like Eratosthenes sieve basically.

Yes, it's it's the same Eratosthenes sieve but you do it in a bit different way. So, Mhm. Eratosthenes sieve you you have like prime three and you you cut out three, six, nine and so on. But here you cut not three, six, nine but you have to start from somewhere in between from like 47. Uh for example, you figure out that uh Q of 47 uh is divisible by seven.

And then uh you divide Q 47, then Q of 47 plus seven, 54, 61, 68 and so on. So, in equal gaps you find numbers that are divisible by this prime. And you divide. So, you basically like override and then you repeat with another prime. It will give you another arithmetic progression.

So, so all of this And you divide um you divide until it's not divisible. So, if it's divisible by 49, you will divide by 49. Yeah, well, 49 is not a prime. So, you it's Right, right. But if you if it's divisible by seven, right?

So you find all the ones but some of them might be divisible by seven squared, seven cubed, and so on. Yes, I think they recommend to divide to try dividing further. Okay. So you you need to divide it until then you do that for all the primes and find all the numbers that you free to reduce to one. Yes.

Okay. Okay. And because of that the amortized cost of testing one number for smoothness is not that high. So how does it compare to the kind of trivial constructive method where you just try random Z? Uh it's much better because the num- this numbers are relatively small, so this they about square root of n.

Right. And because of that, uh the probability for them being B-smooth is much higher. And this basically means that we can uh we can take this smoothness bound uh with with the same smoothness bound as before, we can attack much bigger numbers. Uh so because if uh in in regular method uh if Z if for example you can spend like 2 to the 60 time and then uh for random Z uh the probability to be a smooth is 2 to the minus 30, for example, and you can break I don't know 200-bit numbers with this complexity, then since in the new method Zs are uh size square root of n, this basically means you cannot attack twice bigger numbers, roughly. Right, but there's kind of two tricks, right?

One trick is to make sure that your Z has half the bit size, and then there's the other trick, which is the sieving trick. Presumably, you could keep the first one, but not do the sieving. Yes, so the sieving gives just kind of amortizes the test cost, but I think even trivially the test cost is not that high. Well, if you do it like stupidly, uh then you have like B numbers. Uh if you have like B smoothness, you you have B squared numbers, and you test everyone uh for B smoothness, you have to try B factors, right?

So, you have you spend B fact- B divisions, trial divisions for this, B trial divisions for this, and so on. So, eventually, you spend like B cubed. So, there's a time-memory trade-off here, right? So, like basically, um if you if you do what Justin said and not do the second step by sieving, but with a trivial way, then you can probably do it with much less memory and more locally. Yes, yes.

Uh that's uh that's definitely true. Uh there are even faster methods in the very end of this like an extra method called elliptic curve factoring that allows you to find small factors faster. Uh it allows you to like if you know that your factor is small, then you can find it whatever it is faster than by just trial division. So, you can optimize using this trick as well. Uh so, there are of course very quite many optimizations here, and uh the fact that uh so, how how you can exploit this in hardware.

So, you recall what I said about arithmetic progression, that we uh do the sieving using arithmetic progression, so we access memory in a very predictable way. So, we we take this number, then we step by this prime that we divide by, then again and again. So, all these steps are pretty predictable and it's possible to to share this task among several cores. And there this is quadratic sieve the modern methods called what use what's called lattice sieve, but they all share pretty much the same strategy and memory access is here are very predictable and I think after you have generated this numbers, you can probably share them among your smaller computer. So, like everyone can do their task to filter out uh the to find smooth uh outputs.

That makes sense. Uh this is the second crucial point I wanted to make that the sieving step is very predict even though it requires quite certain amount of memory, it's it's very predictable and of you can even compute this guys on the fly and you can divide this into segments and do this process and of independently for different segments. Just you lose into the total complexity, but uh you can save a lot of memory for every single core. Right. Okay.

Uh so, uh the So, we proceed. And uh yes, interestingly so the optimal B is uh E to the uh half E to the square root of half logarithm of N. Uh I will not compute it directly right here. So, because of the square root, this all this uh complexity estimates are a bit odd and not uh trivial to state. Um but the thing is, so since B is this way, then uh the total complexity is B squared.

Uh this basically means that when you square this, uh you have uh uh two instead of 0.5 uh under the square root. Basically, that's complexity of quadratic sieve. And uh the next advanced method is uh called number field sieve. And number field sieve uses very sophisticated algebraic tricks to make uh this number even smaller.

So, all the rest is almost the same, but they managed to have this uh Z even smaller than square root of n. They make it like uh some root of n, which is not like square root, but something in between like 2.5 or cubic root, it depends. But, uh after they if they can if they make it like smaller, the smoothness probability greatly increases. And because of that, you can attack bigger numbers.

That's the core advantage of the number field sieve. And how they do it, so this unfortunately involves uh quite a bit of algebra. Um uh let me just state the main points here, and maybe later if you would like to understand a bit better, you can return to this. But, uh what's important here is that algebraic part doesn't play almost any role into the like computing this in hardware. So, pseudo code doesn't change significantly from the number from the quadratic sieve.

And the properties of uh architecture needed uh to break the number with number field sieve is almost the same as the for the quadratic sieve. So, you can have understanding of quadratic sieve and build a sieve for quadratic sieve it will be quite efficient for number field sieve as well. So, how number field sieve works? First, they take some polynomial of small degree. Concrete numbers about five or six.

So that it has or some root that we know modulo n. And this polynomial actually can be derived rather trivially. So we can imagine so this number say if this is five then clearly this number should be about five fifth root of n. And we can imagine that if we take a digital representation of n and divide it into five segments and have this m a representation of n then we can find such polynomial. So such polynomials are relatively trivial to find and there are many of them.

Um Suppose also that if we consider not modulo n but just over integers that it has some root which we denote by alpha. So by default it's probably not divisible. I don't have any real roots. And actually if it does then it probably we can find a factor of n trivially. So we assume it doesn't.

And then what we can do is that if we have any polynomial which are built over alpha as variable and if we substitute into this polynomial number m we actually get a homomorphism from the set of polynomials to integers. And this nice homomorphism it has very nice properties that basically if Um if for some uh set of uh numbers A and B, we consider simultaneously uh AI uh minus BI alpha, where alpha is this root, uh and we consider A minus BM. So, we try to find A and B such that this thing is So, this thing is smooth, and because of that, we can find that some product of these guys equal Y square. In parallel, we do the same, but in the algebraic number in the algebraic number field. And we try to find a smooth uh numbers of this kind.

And if they are smooth, then this product is uh uh we can find it We're using the same linear algebra, we can find it's equal to beta square. And if it is equal to some beta square that we know, but uh we haven't computed it yet, then it's possible So, there are some sophisticated algorithms that compute the square root in uh Q of alpha, but not for every number, but only for numbers only for the elements that are squares. So, it's not like in a field where you can compute square root, but uh it's uh in some uh ring of algebraic integers, where you can compute square root when it exists. And if these two things hold, then uh basically, you can apply our homomorphism to beta square, and you will have X square. And so, on the other hand, if you apply homomorphism to uh this product, then you will have uh product of AI minus BIM, and if and we know that we have found that A and B so that they equal to Y square, so that eventually, you have X square equal to Y square.

And what nice here is that well, we have we search for A and B so that this number is smooth and this number is smooth as algebraic number. And we can make them rather small. So that's the the main trick that uh if A and B are small enough then M is also small enough. We remember that it's some root of N. So this guy is small and this guy is also rather small.

So even when the even though we needed both of them are smooth, this probability is much higher than for the Z that we searched before that is smooth. And if both of them are smooth, uh then uh and if you sufficiently find sufficiently many that A and B, then using the same linear algebra trick, we find x² and y². So this is basically the core of uh number field sieve. So uh to summarize, even if you don't understand anything like I did many like first 10 times I read about that. So uh the main property is that uh we work in two uh areas simultaneously in integers and in algebraic integers and we manage to have our numbers both like smooth in both places.

And sorry, algebraic integers, should that be Q of alpha or Z of alpha? Oh, this are rational, but uh Rational, okay. Yes. I think that well, the most I think this we can view them as uh actually Z of alpha because uh well, these guys are always integer in our case, I believe. So actually this all probably should be I think this Q should be So here the homomorphism is uh uh works for Q, but I think uh uh it's uh all the further uh explanations, they are over Z over alpha.

Yeah, thank you for that. Um uh so, basically we just to find smooth uh elements of this set in the top Z over alpha is not not trivial because we cannot divide that easily in that uh field, but what we can do is we can again map this number to integers uh using simple formula. So, we substitute this to the polynomial that we have. This is called the norm. And fortunately, the norm is multiplicative, so if this guy is a square, uh then so is uh the norm.

So, what we basically do is uh we uh find uh a norm uh which is B-smooth, and uh after composing sufficiently many norms, we find the product of elements that is a square, and because of that, there is very high chance that the product of uh algebraic elements is also a square. Oh, yeah, I think I will I'll skip these details. Uh Yes, so there are some uh explanations why uh these numbers are uh small. Uh basically, they are encouraging D about like N to the 0.4, and this is actually sufficient to give us this increase in the the length of the number we can factor.

Um if we go to some concrete complexity, so we can translate these ideas into concrete complexity, and there is a very well, bit uh weird thing. So, uh if N is the number of bits, then this is the uh the formula. Then we have take the square the cubic root of the number of bits. We also have to take logarithm of the number of bits and take power of 1 over 1.5.

Uh multiply all this by 2.4 and deduct 16. And this gives you the complexity in the way that the square root of this is the smoothness bound. So practically for recent factorizations, this is about like 2 to the 30 and this is about 2 to the 60. The 60 what?

That's of course a good question. But if we translate it into core years using the recent factorization records, then we will see that uh this is about 50. Uh so each element is about 50 CPU cycles. So it's some kind of basic uh integer operation, big integer operation. Uh which gives you like I think about 50 CPU cycles.

So um this is the complexity of number field sieve. Uh this is just the complexity complexity, the number of operations. But this doesn't tell us so far what's the complexity to break it in dollars. But that's actually of course very interesting for us what's the actual complexity to break this thing in dollars. We know uh from recent factorization records uh how many core years they have spent.

But these core years are very well uh but but weird core years. So these are not GPU years. These are mainly uh cluster years and clusters of different sizes in different countries. People are run by different people and so on. So these numbers are just aggregation of something.

And this is not very precise. But what's interesting that the architecture here is uh well, IBM PC to the big extent. And yeah, just normal clusters. Uh what we can do is we try we can try to translate the cost of the various cost of factoring this 900 core years into the electricity cost. So how we do this?

We uh take uh number of years and we calculate how many hours, we calculate how much one core consumes energy and we calculate how much one kilowatt hour costs. And eventually what I get is that this seven 795 bit number, it costs only well only $8,000 worth of electricity. $8,000 worth of electricity. So electricity is not the dominating cost here, but we know from the mining that actually for very big competition efforts electricity becomes to dominate. And this actually means that this numbers from the electricity perspective, this numbers are very small.

So from the electricity this cost like $8,000 and this cost $30,000 of electricity. That's for from practical point of view is not is not really big. And of course we can expect that if proper amount of if proper funding is spent into that we could see like if you one decides to spend $1 million, then even on regular clusters he can easily factor 900 bits or something. And on proper hardware even probably more. What I mean by the way any questions so far?

Yeah, I mean I think this is very interesting. Maybe we should go through the numbers one by one so that we can properly understand them because I Yeah. Okay, so basically I take number 900. This is 2 to the 9.8.

Mhm. Then how many kilo hours in the year? Kilo hours mean thousands of hours. It's eight. Because we have like 25 hour 24 hours per day, uh 300 days, and so on.

So, it's about like 8 kilo hours in the year. And then I take a rough estimate that one core in the cluster consumes about uh 30-50 W. This is of course not very precise. Uh so, it can go up and down a bit, like maybe a factor of two or something. And then I take uh that 1 kilowatt hour ends up in uh rich places, well, places where uh electricity is cheap, for example, like near hydro plants.

There are numbers published by some hydro plants in the US that they can spend like four uh cents. Uh they can sell you uh kilowatt hours for cents by four cents each. And this basically means that uh four three that's uh you know, it's about 2 to minus five uh about like 1/3 of USD. Okay. Yeah.

If you multiply this together, you get this number. Yeah, that sounds very reasonable. Okay. Um So, uh how uh what we can expect from number field sieve in this regards. So, there are two main points here.

So, one thing is about sieving that on one hand we test all these square integers for B smoothness. Uh and there are methods that do this uh using all of B of memory and all of B squared time. So, all of B of memory is because we uh need uh well, we store result in B numbers. But, fortunately, we don't have to store much more than that. So, using a bit of parallelism and uh uh processing uh segment by segment, we can uh do this with all of B memory.

But, that memory access is not random, can be parallelized, and memory is used predictably, and that's why I think that and there are some kind of theoretical designs how circuits can be constructed for NFS. The problem here is that the current algorithms current code for NFS may be rather sophisticated because there are like tons of improvements by factor of two or three how exactly we go over these integers because there are pairs of them and and so on what we store what we do not store so some something optimized for cluster and so on. So there is a ton of bell and whistles here when we can we might have to like dig up to figure out how this can be properly implemented on hardware. But I'm pretty sure that with certain amount of research this can be figured out how you should do this on hardware probably. And want to comment here like I mean we know that basically the computations itself we can probably expect a factor of a thousand to a million reduction in the electricity, right?

From mining and so on. So Yes. So that means that what we should look at is actually not the power consumption of the CPU because that will go almost to zero but maybe just the power consumption of the memory and memory controllers. Yes. And also another another thing is that we now have extrapolations from this amount of core years.

But the thing is the actual amount of computation so this is not the amount of computation that they have done is that how how much they have spent. But probably big fraction of this core years were spent on I don't know cash misses or memory accesses or whatever. So, it's not it doesn't mean that the number of operations is exactly this number. So, it's maybe because of x86 architecture this number can be reduced significantly in terms of the number of operations that is being done. So, this complexity estimate that is here is based on the that this core years were spent entirely on computation.

So, if if like only one thousandth of them were spent for computation, then there should be subtraction of another 10 here in the when we calculate the worth of electricity and so on. Mhm. Um Yeah, and then the second very important thing is in linear case, so basically we find a kernel element for matrix with all be non-zero elements and currently we spend it all be squared time. But the thing is and all be memory, but the thing is there are suggestions to have for like multi-core algorithms that using the same amount of memory can do this in much smaller time. Maybe with the expense of more random memory access, but still if we can spend less time on the linear step.

This basically means that we can increase to balance these guys again, we can say if if this step becomes much cheaper for some reason, then we can balance them by increasing the smoothness bound. And so that and with increasing the smoothness bound we can break bigger integers. Even using the same algorithms just by proper balancing these things together. Do you see the point? So, currently both take B squared, but if this takes not B squared by but B to the 1.

5, then clearly we can balance them together and use some different B so that they again use the same. So, maybe we should uh test more integers so that the the smoothness probability is different so that they have they spend again the steps spend the same time. But where does the B to the 1.5 come from? B to 1.

5 comes from uh parallel algorithms that works with the sparse matrices. So, there are suggestions by DGB by Daniel Bernstein who suggested some parallel algorithms for this block Wiedemann and block Lanczos. Existing algorithms which are not very much parallel, but he has some suggestions. They are mostly theoretical ones, but it I think there are others which can be made practical. So, it's very Right.

Interesting. But how would how would parallelism help though? Because if we say what we estimate is the amount of electricity, then parallelism itself doesn't reduce that. Well, do you see as as currently uh the uh we spend B squared time and B memory. Uh so, that the electricity here spent for this is more like B cubed.

Uh but if we spend the same memory but B to the 1.5 time, the electricity will not be B cubed but B uh to the 2.5. So, he basically suggests replacing some memory with cores and because of that reduce the overall computational time and thus reducing the overall electricity consumption. Wait, so you're assuming that the memory is always turned on?

Is that the assumption? Because I I think there's memories now where you basically only pay an electricity cost when you want to access them. Yes, yes, there are static and dynamic RAM and it's of course very right and very interesting question. So, which one should be used here? I think it depends on the algorithm which kind of memory you use because some I think the one that you pay only for you can turn it on and off.

It I think it's bigger. Uh and by itself it requires a bit more space and chip and so on. I mean, SRAM is crazy expensive. I don't expect anyone would use it. Yes, it's also expensive but if you run it for a year, maybe it's worth it.

I mean, my impression is you literally can't get gigabytes of SRAM at the moment. It's so crazy. Like it's it's several orders of magnitude in between. Several orders? I heard it differently but I'm not sure.

Okay. Well, I think that there uh But I mean, I don't think that's such a big deal because even even DRAM the cost when you don't use it is actually not that high. You have to refresh it but I mean it is very low. I mean like a good laptop doesn't really significantly drain its battery in standby and it still refreshes its DRAM. Yeah, I remember there is like fraction of 10 or something which you need.

Um much higher than that I think. I think we're talking much much more than that. Okay, I'm totally not an expert here but I would really love to talk with some experts about all this. I mean one thing to consider maybe is like this this memory from Intel called obtain memory and from what I understand it doesn't need any refreshing. Um so it's like persistent memory but works a bit like like RAM.

Okay, it is but it's still a lot slower than RAM as well. Well, it's like between SSD and RAMs. Right, but it's not that much slower it's like a small constant. Um more more than 10, right? That's small constant.

Uh I thought it was less than 10. I thought it was something like five but I need to check I guess. Okay, uh should we go on maybe? Sure. And one question I had you know you mentioned the extrapolation from the existing numbers.

Yes. How much variance is there in the run time? I can you get super lucky and just complete your algorithm really quickly or or not? I don't think so because uh basically you you have to collect uh uh quite many relations quite many uh smooth integers here Right. and so, your only chance is to find some sub metrics that is linearly dependent.

So, like so that you actually does you don't need all the B numbers, all the B prime numbers to give you the solution. Like what I had in my example. In my example, I had that I need only three and five, so I didn't need two. But the chance for for this to happen is not so high, I think in in real numbers. Uh And there are actually it's much more likely that you will have some parasitic solutions or pseudo solutions that you have to filter out.

So, that as far as I know, people even create numbers matrices with much more rows than needed because otherwise there are they get some solutions that they that don't really don't really work. Right. Okay. So, what else interesting? That I I tried to make some estimates.

For example, in one case as I just extrapolated from the current CPU factorization record. And in other cases I I tried to figure out what the maximum ASIC advantage could be. So, I got that if we talking about cores, cluster cores that spent like 30 W, then the biggest advantage I think would be about about 1,000. Um in the electricity advantage I mean. There are some more detailed calculations in my in my paper in my report.

I will send the link soon for the ones who haven't seen it. So, I also I computed um So, I for some conservative uh scenario, I I added some small advances like to the two to the three into the uh uh algorithms improvement and uh uh some variant of Moore's law and so on. Uh so, they don't uh differ significantly, but there was uh there was also super conservative scenario where uh I analyzed uh the case when uh we we have found this uh uh beta to the 1.5 time uh algorithm for for for matrices. And then I tried to estimate the security in bits.

So, how I did that? I I took ATBTAS key and I tried to figure out so, if you take the current Bitcoin hash power, uh how much it would cost uh if the same if we don't run a SHA-256 there, but AES, how much it would cost in terms of electricity uh to break ATBTAS. And I actually got that you would have to spend uh $50,000 for this uh using current mining uh before the fall. 500,000? 500,000, yes, but it was for Bitcoin price a month ago.

Um and then the 128-bit security, uh it's reasonably that it's cost of 128-bit uh covering which is about $67 which is of course beyond our capabilities. Uh and but what is 256-bit security? 256, I say that uh the system has 256-bit security if it becomes 128-bit secure if you cut out half of uh the key or if all algorithms get quadratic speed up. That's actually the same. So, and in this uh circumstance, uh I analyze the perspective of different moduli sizes.

And here are the numbers. So, you see that in this metric, if we stick to CPUs, to the clusters on which the most recent numbers are broken, then 80-bit security is 950 bit. And 128-bit security is 2,850 bit. But if you consider a conservative scenario where you have some advances in ASICs bringing 1,000 reduction, 1,000 factor in the reduction of electricity cost, then 80 bits is not 900 bit number, but 1,500 bit. And 128-bit security is 1,000 uh bits more for the number to be broken.

This is the RSA moduli that have both prime numbers. A super conservative scenario is if you found this advanced hardware algorithm for matrices, then we basically have all our moduli sizes increased by a bit, 30, 20%. Or something. Also, there's this table is in the report for the ones. I have two extras.

There is a slide about elliptic curve factoring method, and there is a slide about discrete logarithm. Basically, yeah, I'll skip elliptic curves. And for discrete logarithm, the principle is quite similar. So, what they basically do, if if you want to find discrete logarithm of some number, of some element of a prime field, if you talk about prime fields, Uh, you want to logarithm H with to the base G, then you generate uh many uh he, many uh exponents he, and we test if the number is B-smooth with the same saving principle. And after you find sufficiently many such B-smooth numbers, you compose the same linear system, and basically for every you you get the discrete logarithm for every uh number in this uh factoring base.

For every you you logarithm every prime number smaller than B. And um after you're done that, so how to fact how to discrete logarithm this guy, you uh take different taus. do you do that? How do you compute the logarithm? Uh well, uh you uh if you find B uh such guys, then you have your the same matrix actually.

But you uh you column the columns, so you compute your uh linear dependency not modulo 2, but modulo pi P minus 1. So, if uh the prime field is P, then basically means that uh all the exponents that they wrap around uh P minus 1. And uh if you have uh uh different if you have uh all of B B-smooth exponents with the different he, then basically uh you can uh uh solve linear system, and uh well, this linear system the unknowns will be uh actually these guys, and uh you will find it by uh Gaussian elimination. Okay. So, you compute the logarithms of all your primes.

Now, this is actually the last slide. Right, you compute the logarithms of all the primes and then you just keep on randomizing agents until you make make HP smaller than then you you figure out what is the discrete logarithm. Yes. Any questions? On the entire talk.

I mean as as Dankrad said, I imagine the electricity costs for for ASICs will be somewhere between a thousand and a million. A thousand being like kind of the the less conservative estimates. As opposed to the conservative one. Um Yeah, I mean I think one interesting exercise would be um that we could do trivially now um would be to just look at the consumption the electricity consumption of memory. Uh yes, you can.

Uh, but I I think that will give you effect of 2 to the 5 already. Because I suspect it's about 1 watt or something like that instead of 2 to the 5 watt. So, what I for example I have calculated myself uh, that there is this proof of work Equihash uh, which requires for Zcash about 200 megabytes of RAM. And if you take ASICs for them and RAM again? 200 megabytes?

200 megabytes. Mhm. Yes. Uh, and uh, basically what you do with the RAM is sorting. So, you just kind of radix sort your your RAM several times.

That's how Mhm. uh, this in general works. And uh, the advantage uh, in terms over a regular CPU, over a laptop, is about 1,000. Okay. Yeah.

I mean, another question is does it all have to be in the same memory? Like because the problem is if you need high bandwidth, then you probably have quite a bit of power consumption. If you can lower your bandwidth requirements, that would be less. What if you could split it across 1,000 different memories with all much lower bandwidth requirements and can merge it all together? Like for example, do all the sieving steps for different primes on different hardware and merge the results together at a later step.

Is that possible? Yeah, that's possible. I think that's what's actually been done uh, by all these uh, factorization teams. Because in that case, you can probably like lower your bandwidth requirements uh, extremely and go with much lower power requirements for memory. And I think you will end up with something very low.

Already like in normal computers, memory isn't actively cooled, right? By that you know it doesn't really consume that much power. And in laptops already much less. So, I think yeah, yes. I mean factor of thousands seems easily possible there.

But even outside of the the hardware question is like the algorithmic question that it it is very scary, you know, that maybe some sort of I receive algorithm comes out and has a slightly better asymptotic complexity and that completely changes everything. Well, that's a good point. I think as far as I understand in the factoring of integers, not much progress has been made in the last 20 years. But in discrete logarithms, there have been many different approaches because there are different algorithms for prime fields. There are other types of algorithms for extensions of prime field of prime fields, which are important for pairing based crypto.

Uh there are algorithms for fields of characteristic two and so on. So, there are like several groups of discrete logarithms and they all follow this number field sieve and one on another guard. So, I think that if they have found some something really, really important, that would be translated probably to the number field sieve. On the other hand, this the algorithm is itself pretty uh complex. I think it's uh the fact why it works, it requires significant uh algebraic background.

So, the code itself is not that that difficult, but uh as far as I understand, the authors they spent uh several years uh just to uh make all assumptions uh realistic. So, they they basically had to add a few more components to uh to the to the procedure before it start it starts at working for every integers. In the beginning, it worked only for very specific types of integers like two to the two to the n plus one or something like this. And to make it for all integers, they uh have to go through sufficiently many obstacles. So, it's a really difficult problem and yeah, I think no one can estimate if there is a breakthrough in the upcoming years regarding that.

When when when did this happen? When was this kind of Uh from '90 to '93. Okay. And uh one of the prominent guys in this uh research was uh Leonard Adleman. You might remember that in RSA, there are Rivest, Shamir, and Adleman.

And some people say that Adleman did the minimal amount of work, uh but still is included into the RSA uh list of authors, but I think as far as I understand, this has been very well compensated by by his contribution to the the factoring. So, he is one of the people uh like of very few people who made this NFS really possible. So, I I would also be really interested in your judgment as a cryptographer. So, we know that kind of it seems like the progress has slowed there. And I guess there's the two different competing theories.

One is, oh yeah, we are kind of at the edge and there isn't that much more improvement possible. And the other theory is like the bar by NFS is set so high that like it would be crazy for a young cryptographer now to go into factoring because like they would have to spend so much time just getting there and it wouldn't be that likely that they find a new algorithm. I wonder what your judgment on that is. Yeah, I think that's even it's not a cryptographer actually programming problem. Uh in fact, so I think it's much more a mathematical problem because there is almost no cryptography involved in that and there are like some deep uh mathematics things involved.

Like when you for example when you try to read about this imaginary uh quadratic groups, it's it's pretty much uh similar. So you would have have like really deep understanding of algebra before you figure out how all this works and I think just improve that it's really an ambitious task and we don't have that many mathematicians these days, right? So as far as I understand the number of working mathematicians is a bit decreasing. So many people go into more applied science, whereas this factoring is is actually more theoretical. So my gut feeling is that we shouldn't expect uh real uh advances from the theoretical side, but we definitely should expect some advances in practical side.

So when I see this uh sparse linear algorithms and this sieving done on uh regular CPUs, I feel that it can be much much more sped up. If So if if some person who is confident in uh number field sieve talks to person confident in a silicon design. I think they within a few days they will quickly figure out how to make this you know on hardware much much faster. That's my gut feeling. Okay, interesting.

But the the other question is basically so you said you don't expect huge progress right now, but it sounds like that's not because you think there's there is nothing out there to be discovered, but there's nobody who's going to work on it now. Yeah. Yeah, something like this. I think people who are closer to the discrete logarithm research could give a more better better answer because there there are some advances there. There were there have been some advances.

Maybe not in this particular case, but in some in some like sister algorithms there there was advance maybe they can they can tell a little bit better about like the unexplored area and some potential to use them in NFS factoring. So one question I have is that you seem to have focused a lot on the cost of electricity. Are you is the claim that this totally dominates relative to the cost of hardware? Oh yeah, I think so because uh well the hardware itself so if we if we talk about numbers like what was that? 3,000 core years.

So what's the what's like if it's a month uh this means like uh uh I know 30 30,000 cores and uh Yeah, so it's uh Uh I don't know, 30,000 cores what it is. $3 million maybe. Think even cheaper. Uh so of course the well it's it's more expensive than this this course this cost of electricity, but when we talk about custom hardware, I think uh if we uh make a chip of some moderate size, I don't know, 10 by 10 cm or something, and imagine constructing, I don't know, million of these chips for fracturing, I I'm pretty sure that their cost will be smaller than the cost of running time. If we talk about millions of dollars spent for that.

So the design will be, I don't know, several millions. And the chips themselves maybe also several several millions, but the amortized cost will be small, I'm pretty sure, and uh the electricity consumption can be really huge if we talk about, I don't know, hundreds of millions of dollars for electricity. Mhm. I'm I don't know. I'm not totally convinced.

Um Cuz I mean for the the power consumption that can really go down a very significant amount, let's say between 1,000 and a million. But then the area, which is going to be your cost, um that is less clear that it would go down significantly. Area will not go down, but if we can live with the rather small chips, then we can uh put significant amount of them on a die, and then we can live with the reasonable failure probability. So, if they're not like meter by meter, uh then uh I think their production can be uh amortized significantly. But, I I'm I'm not an expert on that, of course, so that's just I mean, I guess just a thought.

I mean, I think asymptotically you are certainly right depending like if we assume that um that you have a reasonable like assume you're okay with factoring it in 1 year. I would say like if you want to factor it in 1 week or 1 month, like ASAP, and you only have one number to factor, I would say very likely the cost of hardware will actually dominate. Because you're basically only running all your hardware for that amount of time. But, like Also, because you won't be able to design proper hardware within this time frame. Right.

Because if if you know what number to factor, you can optimize your hardware already for that number significantly, I think. Mhm, that's also good good point, yeah. Wait, so that is our our situation. So, what is the speed up if you already if you design your hardware specifically for this number? Where do you get gains?

That's a good question. I think this well uh we all have this model reductions. Right? So, I think the the model where this number is used in in in model reductions. And if model reduction circuits can be optimized given a particular number, then we can win there.

So, all these factorization records that of course they knew which number to broke to break, but I think they couldn't really exploit it because they just use a CPUs. But on custom hardware, I think if you can uh hardcode uh the the number into the modular reduction circuit, you should get some benefit. Okay, if it's only the modular multiplication, then I think you get roughly a 2x advantage. For hardcoded versus programmability and both in terms of area and in terms of electricity consumption. Yeah, of course some constant factor.

Yeah. And so wait, but I mean the numbers you square are of a very specific form. Like it's like root n plus epsilon. Uh for quadratic sieve, yes. Oh, I see.

Uh but not for the number field sieve. Uh there I think it'd be different. So you don't not sure you square there. Hm. Um I mean anyway, I think that would not be my sort of main worry.

I mean another way to look at these uh security assumptions is just to because you know, we talk in terms of dollars, but but maybe like the bottleneck is actually just how much electricity the world could produce. Um so I'd be curious to know like how how much electricity is the world producing? And if it was 100% of the electricity dedicated to this problem, how much time would it take to factor? And is that more or less than 10 years? And if it's more than 10 years, then you know, we're definitely safe.

Unless there's some sort of Well, but I mean like please always these are always estimates. Like you always need a Right. level of security. 10 Of course, yeah, yeah, yeah. No, 10 is not enough for margin of security.

I mean, 10 years and a factor of 1,000, I would say. And a factor Whatever factor you want, yes. Because the dollar amounts are always very kind of difficult to reason about, I guess. But, you know, energy and time is more kind of physical. Okay.

So, 21 trillion kilowatt hours. A trillion is 10 to the 12th. So, 2 * 10 to the 13th kilowatt hours per year. This is kind of worldwide electricity consumption. Okay.

Anyway, we can do the do these estimates as well later. Yeah. Okay. Anyway, all of this is pointing me towards the 3,000 bits and avoiding That's my gut feel. Yeah, I mean, thank you, Demetri.

This was very, very well prepared and very understandable. Very good. At least for me. And I think I I understand it much, much better now. Yeah, same here.

Yeah, thank you for your time, guys.