mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-03-21, 16:19   #1
skan
 
skan's Avatar
 
Apr 2012

2×47 Posts
Default 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
skan is offline   Reply With Quote
Old 2018-03-21, 17:10   #2
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3·139 Posts
Default

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 ;-)
Till is offline   Reply With Quote
Old 2018-03-22, 00:06   #3
skan
 
skan's Avatar
 
Apr 2012

10111102 Posts
Default

Quote:
Originally Posted by Till View Post
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
skan is offline   Reply With Quote
Old 2018-03-22, 00:27   #4
skan
 
skan's Avatar
 
Apr 2012

1368 Posts
Default

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.
skan is offline   Reply With Quote
Old 2018-03-24, 09:54   #5
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

3×139 Posts
Default

Have fun ;-) I would be interested in your evaluation.
Till is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 09:19.

Fri Oct 23 09:19:26 UTC 2020 up 43 days, 6:30, 0 users, load averages: 1.25, 1.45, 1.63

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.