Implementing the Quadratic Sieve

 

To factor 629287, we started by considering only 29-smooth numbers. We first look at the polynomial Q(x) = x² - 629287. In order for a prime p to divide a value of Q(x), it is necessary that x² = 629287 (mod p). We computed

 

Mod	629287	Roots
2	1	1
3	1	1, 2
5	2	None
7	1	1, 6
11	10	None
13	9	3, 10
17	15	7, 10
19	7	8, 11
23	7	None
29	16	4, 25

Homework problem 9 asks you to carry out this process for 42448001.

 

Now we use the facts from this table to speed up the factoring of Q(x) = x² –629287. Below I’ve listed values of x from 783 to 802 (these values chosen to be roughly centered about 793.27..., the square root of 629287). We went from 780 to 810 in class, but it didn’t fit on the page and you have all this in your notes already – right? We mark which primes divide Q(x) for each value of x

x	2	3	5	7	11	13	17	19	23	29
783	X			X		X
784		X
785	X	X		X
786
787	X	X						X		X
788		X
789	X						X
790		X		X		X		X
791	X	X
792				X			X
793	X	X
794		X
795	X
796		X				X
797	X	X		X
798
799	X	X		X
800		X
801	X
802		X

Next we started to factor Q(x) = x² - 629287 for each value of x, using the table to tell us which primes will factor Q(x). Since most of the entries in the table are blank (81.5% to be precise), we save a lot of work by using the “sieving” methods of building the table to tell us which primes we need to consider. For larger numbers, the savings are even greater (much greater). We just had time for one example in class, but I will list two examples here.

 

  x                      Q(x)               Factorization of Q(x)

790                  -5187              -1 ´ 3 ´ 7 ´ 13 ´ 19

791                  -3606              Not smooth

 

So we have found our first smooth Q(x). The goal is to find enough different smooth values so that we can complete Kraitchik’s method. Homework problem ten asks you to compute eleven entries in such a table for 42448001, and locate any smooth values.

 

Process for today:

 

1.      Find all smooth values of Q(x) for 780 <= x <= 810. Divide into groups of two or three. Split up the different values of x among your groups. For the values of x that your group is considering, use repeated division by the possible prime factors (consult the table) to find the factorization (or – more often – discover the value is not smooth). Write any smooth values on the front board to share with other groups.

 

2.      Next we look at the polynomial Q₂(x) = x² - 2´629287. We repeat the process of finding which primes from 2 to 29 might divide Q₂(x) just as we found which primes might work for Q(x). Divide the ten primes from 2 to 29 among your groups and have each group determine whether 1258574 = 2´629287 is a square mod the prime that group is considering. If it is a square, list the roots.

 

3.      Now build a table of possible factors for Q₂(x) for 1110 <= x <= 1130 similar to the table we built for Q(x) above (the values for x are chosen to be roughly centered about 1121.8… which is the square root of 1258574).

 

4.      Use the table of possible factors to find any smooth values of Q₂(x). Divide up x values among the groups for factoring and write any smooth values on the front board to share with everyone.

 

5.      Repeat the process for Q₃(x) = x² - 3´629287, Q₄(x), etc. for the remainder of the hour.

 

On Monday, I will expect the class to have a list of smooth values to show me.