2016-02-15, 09:11 | #1 |
Feb 2016
3·5 Posts |
Java Quadratic Sieve
Hi,
I am developer and I got pure math knowledge, but I heard about the Integer Factorization problem and got interested. I spent the last few months trying to understand it and implemented the Quadratic Sieve. This is what I came with. How would you suggest me to go on? How can I improve my algorithm and take it to the next level? What would you recommend me to read? P.S This is my first post on mersenneforum.org so hi everyone! |
2016-02-16, 22:11 | #2 |
Bemusing Prompter
"Danny"
Dec 2002
California
2^{4}·5·31 Posts |
There is an ECM factoring applet that also uses the quadratic sieve: https://www.alpertron.com.ar/ECM.HTM
The source code is available. |
2016-02-22, 11:32 | #4 |
"Tilman Neumann"
Jan 2016
Germany
5·101 Posts |
Hi Ilya,
you should consider implementing SIQS. It is a big factor faster than the basice quadratic sieve. (some paper reported factor 17, was it Contini?). MPQS is a good intermediate step because it is already much faster than basic QS but not as complex as SIQS. Knuth-Schroeppel multipliers give another gain of estimated 50% or so on average. Then there is a lot of fine-tuning that can be done... Cheers Till Last fiddled with by Till on 2016-02-22 at 11:32 Reason: typo |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Simple Atkin sieve java example | lucaf | Computer Science & Computational Number Theory | 8 | 2017-10-06 20:56 |
Quadratic Sieve by Hand | Sam Kennedy | Factoring | 20 | 2013-01-09 16: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 |