-   Factoring (
-   -   Java Quadratic Sieve (

Ilya Gazman 2016-02-15 09:11

Java Quadratic Sieve

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=""]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?

This is my first post on [URL=""][/URL] so hi everyone!

ixfd64 2016-02-16 22:11

There is an ECM factoring applet that also uses the quadratic sieve: [url][/url]

The source code is available.

jasonp 2016-02-19 17:38

See [url=""]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...


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

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