Illustrate the quadratic sieve, as was done in Figure 3.3 (page 157), by sieving prime powers up to B on the values of F(T) = T2 N in the indicated range. (a) Sieve N = 493 using prime powers up to B = 11 on values from F (23) to F (38). Use the relation(s) that you find to factor N. (b) Extend the computations in (a) by using prime powers up to B = 16 and sieving values from F(23) to F(50). What additional value(s) are sieved down to 1 and what additional relation(s) do they yield?

3.7. Smooth numbers and sieves 155 2 35 34 103 70 179 110 263 154 355 202 455 254 563 310 679 1 35 17 103 35 179 55 263 77 355 101 455 127 563 155 679 Next we move on to p = 5 . The congruence t2 221-1 (mod 5 has two solutions, 5 = 1 and 5-4 modulo 5, The first t value in our list that is congruent to 1 modulo 5 is 16, so starting with F(16), we find that every fifth entry is divisible by 5. Sieving out these factors of 5 gives 1 35 17 103 35 179 55 263 77 355 101 455 127 563 155 679 1 7 17 103 35 179 11 263 77355 101 91 127 563 155 679 Similarly, every fifth entry starting with F(19) is divisible by 5, so we sieve out those factors 1 7 17 103 35 179 11 263 77 355 101 91 127 563 155 679 1 7 17 103 7 179 11 263 77 71 101 91 127563 31 679 To conclude our example, we sieve the prime p 7. The congruence t2 221-4 (mod 7) has the two solutions 7 2 and 7-5. We can thus sieve 7 away from every seventh entry starting with F(16), and also every seventh entry starting with F(19). This yields 1 7 17 103 7 179 11 263 7771 101 91 127 563 31 679 1 1 17 103 7 179 11 263 11 71 101 91 127563 31 97 1 1 17 103 1 179 11 263 11 71 101 13 127 563 31 97 Notice that the original entries F(15-4, F(16) = 35, and F(19) = 140 have been sieved all the way down to 1. This tells us that F(15) 152-221, F(16) = 162-221, and F(19) 192-221 are each a product of small primes, so we have discovered several squares modulo 221 that are products of small primes