20111029, 09:50  #1 
2·3^{2}·449 Posts 
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 
20111029, 18:36  #2 
Tribal Bullet
Oct 2004
DFA_{16} Posts 
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 lowlevel libraries for handling large integers and numbertheoretic 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 34 months to get something working. 
20111030, 00:25  #3 
Dec 2010
Monticello
5×359 Posts 
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 34 days to write, assuming you are a toplevel 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 powerpointless, since that is what your audience will see. 
20111030, 01:18  #4  
"Forget I exist"
Jul 2009
Dartmouth NS
5·13·131 Posts 
Quote:
Quote:
Last fiddled with by science_man_88 on 20111030 at 01:58 

20111031, 13:22  #5  
"Bob Silverman"
Nov 2003
North of Boston
2×3×31×41 Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Base method of montgomery polyselect implementation  csg  Homework Help  2  20171213 07:04 
Specialq method for Quadratic Sieve  mickfrancis  Factoring  3  20160503 08:50 
Possible improvement of quadratic sieve  Random Poster  Factoring  4  20100212 03:09 
Factoring in the Quadratic Sieve  ThiloHarich  Factoring  47  20070108 14:12 
Quadratic Sieve in wikipedia.de  ThiloHarich  Factoring  5  20060714 09:51 