mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

3·5 Posts
Smile 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!
Ilya Gazman is offline   Reply With Quote
Old 2016-02-16, 22:11   #2
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2·3·5·7·11 Posts
Default

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

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

348910 Posts
Default

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

1A116 Posts
Default

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
Till is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 04:42.

Fri Oct 30 04:42:47 UTC 2020 up 50 days, 1:53, 1 user, load averages: 1.71, 2.04, 2.15

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.