Java Quadratic Sieve

Ilya Gazman · 2016-02-15, 09:11

Hi,

I am developer and I got pure math knowledge, but I heard about the Integer Factorization problem and got interested.
I spent the last few months trying to understand it and implemented the Quadratic Sieve.
This is 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 mersenneforum.org so hi everyone!

ixfd64 · 2016-02-16, 22:11

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

The source code is available.

jasonp · 2016-02-19, 17:38

See here 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

2016-02-15, 09:11	#1
Ilya Gazman Feb 2016 15₁₀ Posts	Java Quadratic Sieve Hi, I am developer and I got pure math knowledge, but I heard about the Integer Factorization problem and got interested. I spent the last few months trying to understand it and implemented the Quadratic Sieve. This is 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 mersenneforum.org so hi everyone!

2016-02-22, 11:32	#4
Till "Tilman Neumann" Jan 2016 Germany 13·41 Posts	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 Last fiddled with by Till on 2016-02-22 at 11:32 Reason: typo

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Simple Atkin sieve java example	lucaf	Computer Science & Computational Number Theory	8	2017-10-06 20:56
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

2016-02-16, 22:11	#2
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 5×499 Posts	There is an ECM factoring applet that also uses the quadratic sieve: https://www.alpertron.com.ar/ECM.HTM The source code is available.

2016-02-19, 17:38	#3
jasonp Tribal Bullet Oct 2004 3²×5×79 Posts	See here for another Java effort.