Self-Initializing Quadratic Sieve Continued

In these weeks most of my time spent was on Linear Algebra Stage of QS. I implemented fast gaussian elimination over modulo 2. Then i implemented find proper factor function. This function try to write the dependent rows of the reduced gaussian form of smooth relations matrix into the combination of the dependent rows. This way we can make the combination a perfect square and we will obtain our desired relations of the form X^2 = Y^2 moduloN. And finally we can a proper factor by taking gcd(X - Y, N).

In these two weeks i worked on making the quadratic sieve more efficient. I made several optimizations like: (i) Include -1 into factor_base as it increase the probability of finding smooth relation (ii) Partial relations

PARTIAL RELATIONS

Out of these the most important optimization was to include the partial relations. This increase the speed to 2X times. A while checking for smoothness if we encounter a number having only one prime factor outside the factorbase then this will be called a partial relation and we will store it.

In QS we are trying to find relations of u**2 = v modN where v is a B smooth number and a square. Let the factorbase bound be 10000 and v can be p1**2 * p2**8.... a square where pi are primes. But while seiving if v is p1*2 * p2**10.... * p5 here v is a square * a large prime number > 10000 so here v can be written as v1 * P where v1 is a B smooth number but P is a prime number > B. SO we will collect these and if we find a pair of 2 relations where they have a common Large prime. Like RELATION 1 : u_1 ^ 2 = v_1 * P modN and RELATION 2 : u_2 ^ 2 = v_2 * P modN here they both have same Large Prime factor P. So, they can be combined such that (u_1 * u_2) ^ 2 = (v_1 * v_2) * (P ^ 2) modN now multiply mod_inverse(P, N) ^ 2 both sides. Then it will become (u_1 * u_2 * mod_inverse(P, N)) ^ 2 = (v_1 * v_2) modN which can be rewritten as u_3 ^ 2 = v_3 modN thus forming a smooth relation. Here RELATION 1 & 2 are partial relation.