20180321, 16:19  #1 
Apr 2012
136_{8} Posts 
Easiest working Quadratic Sieve code?
Where can I find the easiest possible source code able to factorize numbers using the quadratic sieve method (or even SIQS)?
I mean something selfcontained maybe in Python or Mathematica, Fortran, Julia or any common easy to use scientific language... not depending on external libraries nor anything too complex. It's just to play with, try some modifications and better understand the method. I guess it will be limited to deal with small numbers except if its made for Mathematica. Also a graphical simulator with all the processes involved would be great. Last fiddled with by skan on 20180321 at 16:47 
20180321, 17:10  #2 
"Tilman Neumann"
Jan 2016
Germany
2·11·19 Posts 
You can have a look at my PSIQS package at http://www.tilmanneumann.de/psiqs.html
It is not small (~900 kb source code), but that's due to the following reasons: * many comments * different implementations of the same tasks (e.g. sieving, trial division) * contains several "smaller" factoring algorithms * contains all the basic algorithms required for a fast SIQS It should be rather easy to understand. Start with class SIQS and subsequently pick the simplest member of each subalgorithm. E.g. at the beginning you might want to see SimpleSieve instead of DoubleBlockHybridSieveU... Btw. I'ld bet that there is no Fortran implementation that is easy to understand ;) 
20180322, 00:06  #3  
Apr 2012
2×47 Posts 
Quote:
Last fiddled with by skan on 20180322 at 00:06 

20180322, 00:27  #4 
Apr 2012
2·47 Posts 
Besides the code in Java yo suggested I've also found these...
A simple one: https://github.com/alexbers/quadratic_sieve This multipolynomial: https://github.com/lukemarch23/py_mpqs One selfinitialized https://github.com/skollmann/PyFacto...r/factorise.py All the above with python. And this one with Julia. https://github.com/hamukazu/quadrati...b/master/qs.jl Thera are a lot of too long codes in Fortran here: https://github.com/daoudclarke/wartonlegacy I'm unable to find anything with R, because the word "R" is too common and I guess R too slow. Now I have to find which of the works well and it's simple and clear. 
20180324, 09:54  #5 
"Tilman Neumann"
Jan 2016
Germany
2·11·19 Posts 
Have fun ;) I would be interested in your evaluation.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Quadratic Sieve by Hand  Sam Kennedy  Factoring  20  20130109 16: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 