The first problem we encountered with Kraitchik's method was that we wasted time trying to factor numbers like -277, which we weren't going to use to build a square anyway. We get rid of this problem by looking only at smooth numbers. We define a number to be p-smooth if all of the prime factors of the number are less than or equal to p. So for example, 4235 is 13-smooth, since 4235 = 5 ´ 7 ´ 11² so all its prime factors are less than or equal to 13. On the other hand, 87 is not 13-smooth since 87 = 3 ´ 29 and 29 > 13. When building the table for Kraitchik's method, we will first decide on how smooth the numbers have to be. After we decide to work only with p-smooth numbers, we will just check prime factors up to p. If the number isn't factored yet, we will throw it out and ignore it. For example, in building the table for 2041, if we decided to use only 7-smooth numbers, then the table we built last time would look like this.

Note that we have tossed out four numbers. We never used them in any of the ways we built squares, so this hasn't actually cost us much, and it has saved us time on the factoring. It is a tricky problem to pick the most efficient amount of smoothness. There are algorithms for picking how smooth you want to insist the numbers be, but we won't go over how to do this in this class, I'll just let you know how smooth to take each problem.

The next problem with Kraitchik's factoring method is that it is difficult to program a computer to "play with the numbers" to build a square. But once we have restricted ourselves to smooth numbers, we can find a way around this also. Every 7-smooth number has a factorization in the form

(40^a₁)² ´ (41^a₂)² ´ … ´ (53^a₁₀)²

        =-1^(e_1,1a₁+e_1,2a₂+…+e_1,10a₁₀)

             ´ 2^(e_2,1a₁+e_2,2a₂+…+e_2,10a₁₀)

             ´ 3^(e_3,1a₁+e_3,2a₂+…+e_3,10a₁₀)

             ´ 5^(e_4,1a₁+e_4,2a₂+…+e_4,10a₁₀)

             ´ 7^(e_5,1a₁+e_5,2a₂+…+e_5,10a₁₀)

             (mod 2041)

where a_j is 1 if we are including the j^th number in the product and 0 if we aren't. In order for the right hand side of this expression to be a square, we need to pick a₁, … , a₁₀ so that all the exponents are even, i.e. so that

This is a system of 5 linear equations in 10 unknowns, so we can certainly find solutions. In fact we can find a lot of solutions so we can keep trying different solutions till we find one that produces non-trivial repeated squares which will let us factor 2041. What's more, there are good algorithms for finding such solutions quickly on a computer. We won't go over these algorithms in this class (they are covered in Math 551). What I do want you to remember from this part of the handout is that it is possible to program the computer to build squares out of smooth numbers by reducing the problem to solving systems of linear equations.

We now have an algorithm for factoring that can be programmed into a computer. There is one more major enhancement to be made. Most of the time in this algorithm is spent on building the table, in particular on factoring the Q(x). Restricting to a finite number of factors by looking only at smooth numbers helps some, but we can do better. You may have noticed that none of the Q(x) were divisible by 11 when we built our original table. We can see that Q(x) = x² - 2041 is never divisible by 11 as follows. If 11 | x² - 2041, then x² = 2041 (mod 11). But 2041 = 6 (mod 11) and 6 has no square root mod 11, i.e. there is no x with x² = 6 (mod 11). So 11 can never divide Q(x). Of course, 7 can divide Q(x) as we see in the table. This makes sense since 2041 = 4 (mod 7) and 2² = 5² = 4 (mod 7). This information still lets us cut down how much checking we have to do, because it tells us 7 will divide Q(x) only for x = 2,5 (mod 7). We can build a new table of which of the primes 2, 3, 5, 7 might divide Q(x) by repeating these calculations for each prime. This yields the table

So from the table we can immediately see that neither x = 42 nor x = 48 could give us a smooth Q(x), since they won't be divisible by any of the primes 2, 3, 5, or 7. In factoring Q(40), we see we only need to divide out by 3 and 7, since neither 2 nor 5 will divide Q(40). In fact, with this table we will never test a prime that doesn't divide the number, since the table tells us exactly which primes divide and which don't. This simple table doesn't tell us how many times each prime divides into Q(x) of course. There are tricks for doing that (which are built into the UBASIC program mpqsx), but for us it will be sufficient just to try dividing until it no longer works.

With this last enhancement we now have built the full Quadratic Sieve factoring method. This method was introduced (with a few more enhancements we haven't covered) in the early 1980s. Our next two classes will be spent on actually carrying out the quadratic sieve factoring method to factor 629287. You also have two homework problems on carrying out different parts of the Quadratic Sieve method for factoring 42448001.