Quadratic Sieve

March 19, 2013

As an example, we will factor 87463 using f = 30 and m = 32. The factor base primes are 2, 3, 13, 17, 19 and 29, and b = 296, so we will sieve from 264 to 328. Then soln1 is the list 1, 1, 15, 7, 9 for the odd primes in the factor base, soln2 is the list 2, 4, 1, 16, 14 for the odd primes in the factor base, and l is the list 1, 1, 3, 3, 3, 3 for the primes (including 2) in the factor base.

Now we sieve. For factor base prime 2, add 1 at the odd-numbered indices in the sieve; 2 is weird, since it doesn’t have a square root, so you’ll have to compute g(x) for the lowest value of x then sieve based on its parity. For factor base prime 3, add 1 at indices 1, 4, …, 64 for soln1 and 1 at indices 2, 5, …, 62 for soln2. For factor base prime 13, add 3 at indices 1, 14, 27, 40, 53 for soln1 and 3 at indices 4, 17, 30, 43, 56 for soln2. For factor base prime 17, add 3 at indices 15, 32, 49 for soln1 and 3 at indices 1, 18, 37, 52 for soln2. For factor base prime 19, add 3 at indices 7, 26, 45, 64 for soln1 and 3 at indices 16, 35, 54 for soln2. For factor base prime 29, add 3 at indices 9, 38 for soln1 and 3 at indices 14, 43 for soln2. Once that is done, the sieve will contain the values in the “Sum” column:

i x g(x) 13 17 19 29 Sum Factors
0 264 -17767 0 0 0 0 0 0 0  
1 265 -17238 1 1 3 3 0 0 8 -1,2,3,13,13,17
2 266 -16707 0 1 0 0 0 0 1  
3 267 -16174 1 0 0 0 0 0 1  
4 268 -15639 0 1 3 0 0 0 4  
5 269 -15102 1 1 0 0 0 0 2  
6 270 -14563 0 0 0 0 0 0 0  
7 271 -14022 1 1 0 0 3 0 5  
8 272 -13479 0 1 0 0 0 0 1  
9 273 -12934 1 0 0 0 0 3 4  
10 274 -12387 0 1 0 0 0 0 1  
11 275 -11838 1 1 0 0 0 0 2  
12 276 -11287 0 0 0 0 0 0 0  
13 277 -10734 1 1 0 0 0 0 2  
14 278 -10179 0 1 3 0 0 3 7 -1,3,3,3,13,29
15 279 -9622 1 0 0 3 0 0 4  
16 280 -9063 0 1 0 0 3 0 4  
17 281 -8502 1 1 3 0 0 0 5  
18 282 -7939 0 0 0 3 0 0 3  
19 283 -7374 1 1 0 0 0 0 2  
20 284 -6807 0 1 0 0 0 0 1  
21 285 -6238 1 0 0 0 0 0 1  
22 286 -5667 0 1 0 0 0 0 1  
23 287 -5094 1 1 0 0 0 0 2  
24 288 -4519 0 0 0 0 0 0 0  
25 289 -3942 1 1 0 0 0 0 2  
26 290 -3363 0 1 0 0 3 0 4  
27 291 -2782 1 0 3 0 0 0 4  
28 292 -2199 0 1 0 0 0 0 1  
29 293 -1614 1 1 0 0 0 0 2  
30 294 -1027 0 0 3 0 0 0 3  
31 295 -438 1 1 0 0 0 0 2  
32 296 153 0 1 0 3 0 0 4 3,3,17
33 297 746 1 0 0 0 0 0 1  
34 298 1341 0 1 0 0 0 0 1  
35 299 1938 1 1 0 3 3 0 8 2,3,17,19
36 300 2537 0 0 0 0 0 0 0  
37 301 3138 1 1 0 0 0 0 2  
38 302 3741 0 1 0 0 0 3 4  
39 303 4346 1 0 0 0 0 0 1  
40 304 4953 0 1 3 0 0 0 4  
41 305 5562 1 1 0 0 0 0 2  
42 306 6173 0 0 0 0 0 0 0  
43 307 6786 1 1 3 0 0 3 8 2,3,3,13,29
44 308 7401 0 1 0 0 0 0 1  
45 309 8018 1 0 0 0 3 0 4  
46 310 8637 0 1 0 0 0 0 1  
47 311 9258 1 1 0 0 0 0 2  
48 312 9881 0 0 0 0 0 0 0  
49 313 10506 1 1 0 3 0 0 5  
50 314 11133 0 1 0 0 0 0 1  
51 315 11762 1 0 0 0 0 0 1  
52 316 12393 0 1 0 3 0 0 4 3,3,3,3,3,3,17
53 317 13026 1 1 3 0 0 0 5  
54 318 13661 0 0 0 0 3 0 3  
55 319 14298 1 1 0 0 0 0 2  
56 320 14937 0 1 3 0 0 0 4  
57 321 15578 1 0 0 0 0 0 1  
58 322 16221 0 1 0 0 0 0 1  
59 323 16866 1 1 0 0 0 0 2  
60 324 17513 0 0 0 0 0 0 0  
61 325 18162 1 1 0 0 0 0 2  
62 326 18813 0 1 0 0 0 0 1  
63 327 19466 1 0 0 0 0 0 1  
64 328 20121 0 1 0 0 3 0 4  

You can see now why sieving is so fast; for example, for factor base prime 29 we touched only 4 items in the sieve. In fact, a common optimization for the quadratic sieve is to ignore small factor base primes, on the theory that they take a lot of work and contribute only a small amount to the sum of the logarithms, then reduce the target sum at which you perform trial division.

From the sieve, we pick all the locations with sum greater than or equal to four for further examination; normally we would take a somewhat larger target, but since n is so small, that calculation is distorted. Note that location 52 has a small sum because our sieving method ignores prime powers; in practice, such locations, useful though they are, are often missed, which is uncomfortable but not usually a problem, since we can always sieve for more relations. For each item selected, we calculate g(x) and then perform trial division over the factor base primes. The following g(x) are smooth over the factor base, forming six relations:

265    -1, 2, 3, 13, 13, 17
278    -1, 3, 3, 3, 13, 29
296    3, 3, 17
299    2, 3, 17, 19
307    2, 3, 3, 13, 29
316    3, 3, 3, 3, 3, 3, 17

Since there are six primes in the factor base and six smooth relations, we are at the cusp of having a sufficient number of relations to complete the factorization. We won’t discuss the linear algebra stage here, as we have done that previously in the exercises for Dixon’s method and the continued fraction method. But we do note that the linear algebra gives us two sets of smooth relations:

(296 × 316)2 = (34 × 17)2 (mod 87463)
935362 = 13772 (mod 87463)
gcd(93536 − 1377, 87463) = 587

(265 × 278 × 307 × 316)2 = (-1 × 2 × 36 × 132 × 17 × 29)2 (mod 87463)
71468740402 = -1214761862 (mod 87463)
gcd(7146874040 − -121476186,87463) = 87463

Of those, the first gives a factorization, but the second gives only a trivial factor. So we see that 87463 = 149 × 587. Code is given on the next page.

About these ads

Pages: 1 2 3

One Response to “Quadratic Sieve”

  1. […] Quadratic Sieve (programmingpraxis.com) […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: