mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   Java Quadratic Sieve (https://www.mersenneforum.org/showthread.php?t=20997)

Ilya Gazman 2016-02-15 09:11

Java Quadratic Sieve
 
Hi,

I am developer and I got pure math knowledge, but I heard about the [B]Integer Factorization problem[/B] and got interested.
I spent the last few months trying to understand it and implemented the [B]Quadratic Sieve[/B].
[URL="https://github.com/gazman-sdk/quadratic-sieve"]This is[/URL] what I came with.

How would you suggest me to go on?
How can I improve my algorithm and take it to the next level?
What would you recommend me to read?

P.S
This is my first post on [URL="http://www.mersenneforum.org/"]mersenneforum.org[/URL] so hi everyone!

ixfd64 2016-02-16 22:11

There is an ECM factoring applet that also uses the quadratic sieve: [url]https://www.alpertron.com.ar/ECM.HTM[/url]

The source code is available.

jasonp 2016-02-19 17:38

See [url="http://mersenneforum.org/showthread.php?t=20827"]here[/url] for another Java effort.

Till 2016-02-22 11:32

Hi Ilya,

you should consider implementing SIQS. It is a big factor faster than the basice quadratic sieve. (some paper reported factor 17, was it Contini?).

MPQS is a good intermediate step because it is already much faster than basic QS but not as complex as SIQS.

Knuth-Schroeppel multipliers give another gain of estimated 50% or so on average.

Then there is a lot of fine-tuning that can be done...

Cheers
Till


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

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