View Single Post
Old 2011-10-30, 01:18   #4
science_man_88's Avatar
"Forget I exist"
Jul 2009

26·131 Posts

Originally Posted by abhiiitkgp View Post
Sorry if posting for a complete code is wrong.
but this is my last option.
i need to submit code and present a ppt on quadratic sieve method in c++ in 2 days.

anyone who did it before post it,i would be very thankful to them.

i found some codes on internet but they are very big.i need a simple implementation.

Thanks in advace
Originally Posted by
To summarize, the basic quadratic sieve algorithm has these main steps:
1)Choose a smoothness bound B. The number π(B), denoting the number of prime numbers less than B, will control both the length of the vectors and the number of vectors needed.
2)Use sieving to locate π(B) + 1 numbers ai such that bi=(ai2 mod n) is B-smooth.
3)Factor the bi and generate exponent vectors mod 2 for each one.
4)Use linear algebra to find a subset of these vectors which add to the zero vector. Multiply the corresponding ai together naming the result mod n: a and the bi together which yields a B-smooth square b2.
5)We are now left with the equality a2=b2 mod n from which we get two square roots of (a2 mod n), one by taking the square root in the integers of b2 namely b, and the other the a computed in step 4.
6)We now have the desired identity: (a + b)(a − b) = 0(mod n). Compute the GCD of n with the difference (or sum) of a and b. This produces a factor, although it may be a trivial factor (n or 1). If the factor is trivial, try again with a different linear dependency or different a.
The remainder of this article explains details and extensions of this basic algorithm.
gives you steps to solve the code for it.

Last fiddled with by science_man_88 on 2011-10-30 at 01:58
science_man_88 is offline   Reply With Quote