## 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) | 2 | 3 | 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} = (3^{4} × 17)^{2} (mod 87463)

93536^{2} = 1377^{2} (mod 87463)

gcd(93536 − 1377, 87463) = 587

(265 × 278 × 307 × 316)^{2} = (-1 × 2 × 3^{6} × 13^{2} × 17 × 29)^{2} (mod 87463)

7146874040^{2} = -121476186^{2} (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.

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