mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Programming (https://www.mersenneforum.org/forumdisplay.php?f=29)
-   -   Easiest working Quadratic Sieve code? (https://www.mersenneforum.org/showthread.php?t=23177)

skan 2018-03-21 16:19

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.

Till 2018-03-21 17:10

You can have a look at my PSIQS package at [url]http://www.tilman-neumann.de/psiqs.html[/url]

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=Till;482986]You can have a look at my PSIQS package at [url]http://www.tilman-neumann.de/psiqs.html[/url]

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 ;-)[/QUOTE]

OK, thanks. I'll have a look, though I would prefer anything not in Java :confused:

skan 2018-03-22 00:27

Besides the code in Java yo suggested I've also found these...

A simple one:
[url]https://github.com/alexbers/quadratic_sieve[/url]

This multipolynomial:
[url]https://github.com/lukemarch23/py_mpqs[/url]

One self-initialized
[url]https://github.com/skollmann/PyFactorise/blob/master/factorise.py[/url]

All the above with python.

And this one with Julia.
[url]https://github.com/hamukazu/quadratic_sieve/blob/master/qs.jl[/url]

Thera are a lot of too long codes in Fortran here:
[url]https://github.com/daoudclarke/wartonlegacy[/url]

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.


All times are UTC. The time now is 20:15.

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