Programming Praxis

We implemented a very basic quadratic sieve in a previous exercise. In today’s exercise we will implement three improvements to the sieving phase of the algorithm.

The first improvement comes from the world of code tuning: we will segment the sieve instead of employing a single monolithic sieve. This allows us to tune the memory footprint of the sieve and keep everything in cache memory, which makes the entire process much faster. The second improvement also comes from the world of code tuning: we will use logarithms base 2 instead of base e, because they keep the entire calculation within the realm of integer arithmetic instead of floating-point arithmetic, and we will define an error factor on the sum of the logarithms based on the size of n.

The third improvement is algorithmic. Sometimes when checking a possible smooth number, a number is found that is almost smooth, with a single large prime factor between f and f²; such relations are called partial relations. If the large primes of two partial relations are equal, they can be multiplied together to form a match, which can then be treated like any other relation in the exponent vector. By the birthday paradox, matches are more common than you might think. Thus, sieving produces two lists, a list of relations and a list of partials, then the partials are sorted on their leading prime and a simple scan through the list of partials identifies the matches. The effect is to find more usable relations with the same amount of sieving.

Your task is to modify the quadratic sieve of the previous exercise to incorporate these changes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2