Easiest working Quadratic Sieve code?

skan · 2018-03-21, 16:19

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.

Till · 2018-03-21, 17:10

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 ;-)

skan · 2018-03-22, 00:06

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

skan · 2018-03-22, 00:27

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.

Till · 2018-03-24, 09:54

Have fun ;-) I would be interested in your evaluation.

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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Java Quadratic Sieve	Ilya Gazman	Factoring	3	2016-02-22 11:32
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

2018-03-21, 17:10	#2
Till "Tilman Neumann" Jan 2016 Germany 2×3×71 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: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 652₈ Posts	Have fun ;-) I would be interested in your evaluation.