mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2011-10-29, 09:50   #1
abhiiitkgp
 

112618 Posts
Unhappy 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
  Reply With Quote
Old 2011-10-29, 18:36   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67218 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2011-10-30, 00:25   #3
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

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.
Christenson is offline   Reply With Quote
Old 2011-10-30, 01:18   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
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
Quote:
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.

Last fiddled with by science_man_88 on 2011-10-30 at 01:58
science_man_88 is offline   Reply With Quote
Old 2011-10-31, 13:22   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Base method of montgomery polyselect implementation csg Homework Help 2 2017-12-13 07:04
Special-q method for Quadratic Sieve mickfrancis Factoring 3 2016-05-03 08:50
Possible improvement of quadratic sieve Random Poster Factoring 4 2010-02-12 03:09
Factoring in the Quadratic Sieve ThiloHarich Factoring 47 2007-01-08 14:12
Quadratic Sieve in wikipedia.de ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 08:17.

Sun May 9 08:17:42 UTC 2021 up 31 days, 2:58, 0 users, load averages: 3.20, 2.91, 2.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.