Go Back > Factoring Projects > Factoring

Thread Tools
Old 2016-02-15, 09:11   #1
Ilya Gazman
Feb 2016

3·5 Posts
Smile Java Quadratic Sieve


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?

This is my first post on so hi everyone!
Ilya Gazman is offline   Reply With Quote
Old 2016-02-16, 22:11   #2
Bemusing Prompter
ixfd64's Avatar
Dec 2002

1001010011102 Posts

There is an ECM factoring applet that also uses the quadratic sieve:

The source code is available.
ixfd64 is offline   Reply With Quote
Old 2016-02-19, 17:38   #3
Tribal Bullet
jasonp's Avatar
Oct 2004

353810 Posts

See here for another Java effort.
jasonp is offline   Reply With Quote
Old 2016-02-22, 11:32   #4
Till's Avatar
"Tilman Neumann"
Jan 2016

22·109 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...


Last fiddled with by Till on 2016-02-22 at 11:32 Reason: typo
Till is offline   Reply With Quote

Thread Tools

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 ThiloHarich Factoring 5 2006-07-14 09:51

All times are UTC. The time now is 23:44.

Tue May 18 23:44:39 UTC 2021 up 40 days, 18:25, 0 users, load averages: 1.17, 1.30, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.