mersenneforum.org Easiest working Quadratic Sieve code?
 Register FAQ Search Today's Posts Mark Forums Read

 2018-03-21, 16:19 #1 skan     Apr 2012 2·47 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 self-contained 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 2018-03-21 at 16:47
 2018-03-21, 17:10 #2 Till     "Tilman Neumann" Jan 2016 Germany 13×37 Posts You can have a look at my PSIQS package at http://www.tilman-neumann.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 ;-)
2018-03-22, 00:06   #3
skan

Apr 2012

9410 Posts

Quote:
 Originally Posted by Till You can have a look at my PSIQS package at http://www.tilman-neumann.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 ;-)
OK, thanks. I'll have a look, though I would prefer anything not in Java

Last fiddled with by skan on 2018-03-22 at 00:06

 2018-03-22, 00:27 #4 skan     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 self-initialized 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.
 2018-03-24, 09:54 #5 Till     "Tilman Neumann" Jan 2016 Germany 13·37 Posts Have fun ;-) I would be interested in your evaluation.

 Similar Threads Thread Thread Starter Forum Replies Last Post Ilya Gazman Factoring 3 2016-02-22 11:32 Sam Kennedy Factoring 20 2013-01-09 16:50 Random Poster Factoring 4 2010-02-12 03:09 ThiloHarich Factoring 47 2007-01-08 14:12 ThiloHarich Factoring 5 2006-07-14 09:51

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

Thu Jan 20 17:50:12 UTC 2022 up 181 days, 12:19, 1 user, load averages: 1.63, 1.88, 1.73