Quadratic sieve method implementation..

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

[jasonp]

Many people here have written QS code, but if the code must be simple in order to look like you wrote it, then I don't think we can help you. Further, if you're starting from scratch now, then 2 days isn't nearly enough to figure out the details of the low-level libraries for handling large integers and number-theoretic functions that you will need to get a working implementation. The smallest C code I've seen for QS was about 1500 lines of C, and that doesn't include the code for the large integer arithmetic.

Doing everything from the beginning, it took me about 3-4 months to get something working.

[Christenson]

If you've got to go for speed of implementation (as opposed to speed of running), perl is the best language, as all the data structures (lists, hashes, functions returning multiple values, etc) are built in.

In your shoes: I'd present the basic algorithm, and write a main(). Assume lots of functionality. Jasonp's 1500 lines will take at least 3-4 days to write, assuming you are a top-level coder. And plan further ahead in the future! There's no way you have time to learn perl.

Stop writing code in 24 hours, and write power-pointless, since that is what your audience will see.

[science_man_88]

Originally Posted by abhiiitkgp

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 http://en.wikipedia.org/wiki/Quadratic_sieve

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.

[R.D. Silverman]

Originally Posted by jasonp

Many people here have written QS code, but if the code must be simple in order to look like you wrote it, then I don't think we can help you. Further, if you're starting from scratch now, then 2 days isn't nearly enough to figure out the details of the low-level libraries for handling large integers and number-theoretic functions that you will need to get a working implementation. The smallest C code I've seen for QS was about 1500 lines of C, and that doesn't include the code for the large integer arithmetic.

Doing everything from the beginning, it took me about 3-4 months to get something working.

Add to this:

One also needs a good understanding of the algorithm itself; in detail,
as well as knowing enough number theory; one can't code the algorithm
without knowing e.g. what a quadratic residue is, and how/why the Jacobi
symbol works.