Special primes. In case of lattice sieving, we simulate the relations as described in either Case I or Case II and add a special prime to each relation in the following way. From the relations in the sieving test we compute the average number of relations per pair (special prime, root). Then we divide the number of relations we want to simulate by this average and this gives the total number of special primes in our simulation. We select an appropriate interval for the special primes from which they are chosen as follows. Divide the interval in a (small) number of sections: per section select randomly the special primes and add one special prime to each of the relations. By dividing in sections (and simulating the same amount of relations per section) we make sure that each part of the interval of special primes is well presented, and by choosing randomly in each section, we get enough variation in the amount of relations per special prime. If the interval of the special primes is very large, it might become necessary to decrease the number of relations per section. A sieving test, of which the special primes are uniformly distributed over the interval, will indicate a suitable choice of sections and the number of relations for each section. It is possible to use different factorbase bounds for the rational primes and the algebraic primes, bound the product of the two large primes on the same side, etc. All these details in the sieving influence the relations, but once the general model is known, it is relatively easy to adjust it to match the details.
