20051102, 14:33  #1 
Nov 2005
101 Posts 
Understandable QS java Implementation
Hi I’am a novice and I’have got a few novice questions:
1) Is there a java Implementation which is understandable? I know http://www.alpertron.com.ar/ECM.HTM and a less advanced try http://wwwfs.informatik.unituebing...r/QuadAlg.html. These Implementations consist basically of one big static method. I wrote an OOImplementation of QS. So the implementation of LPQS was just overriding a few methods. Now I want to switch to SIQS. But I’m still trying to understand it. 2) I wrote a variant which stops after sieving with all factors except the last k (say 35). Then only if the length of the remaining y (after the subtracting of factor length) is greater then a certain threshold (the QS threshold + k +3), sieving with the remaining factors is done. After sieving with a factor the length will be checked again (k has changed). In http://www.math.dartmouth.edu/~carlp/PDF/paper52.pdf a similar idea is mentioned. In http://aux.planetmath.org/files/papers/235/mpqs.ps it is written that this idea only saves 20% Time. In my Implementation it saves 50% at 30 Digit numbers, while LPQS only saves 30%. I know that DLPQS will be fast only for very huge N. Does LPQS reach its advantages of saving over 50% only at bigger numbers? 
20051102, 14:57  #2  
Tribal Bullet
Oct 2004
3×1,181 Posts 
Quote:
Quote:
The savings you get from LPQS will depend heavily on parameter choices in your implementation. For msieve the 50% figure happens at ~70 digits; for smaller sizes 40% faster is common. The tiny QS implementation above uses parameters that save 3045% when using large primes for inputs of ~116 bits jasonp 

20051102, 15:31  #3 
Nov 2005
1100101_{2} Posts 
Thank you jasonp,
I just downloaded the sources. In the papers I read so far I havent found how much faster the SIQS/MPQS is compared to the standard QS. But since the MPQS very often hits a smooth number compared with the standard QS it might be more then a linear factor. Are there any resluts? 
20051102, 17:25  #4  
Tribal Bullet
Oct 2004
110111010111_{2} Posts 
Quote:
If performance is a concern you basically have to use multiple polynomials. jasonp 

20051102, 17:40  #5  
Nov 2003
1D24_{16} Posts 
Quote:
My 1987 paper in Math. Comp. "The Multiple Polynomial Quadratic Sieve" will give a novice all the information needed to implement the single large prime version of the algorithm. The paper does require knowing a little bit of elementary number theory (e.g. you need to know what a quadratic residue is) I also gives a comparison to the single polynomial version. Mathematics of Computation is widely distributed. Any college library will carry it. 

20051103, 07:38  #6 
Nov 2005
101 Posts 
I left the town were i have been studying. I only got bad access to paper libraies.
Is there still no proof on the deterministic runtime of QS? 
20051103, 11:23  #7  
Nov 2003
2^{2}×5×373 Posts 
Quote:
the range of a quadratic polynomial have the same statistical smoothness properties as random integers. The same obstacle applies (although for higher degree polynomials) for NFS. 

20051103, 11:36  #8 
Aug 2002
Buenos Aires, Argentina
10101010110_{2} Posts 
In my factoring applet the #1 design objective was speed. All other features were secondary, including program readability if that was against running time.
That's why the applet is not OOPoriented. In this way no objects have to be created and destroyed, which takes a lot of time. Of course you can do an OOPoriented factoring applet, but I think that it will run two or three times slower than a program that uses arrays to store data. OOP in Java is great for serving Web pages but totally wrong for this kind of programs. 
20051103, 11:44  #9  
Nov 2003
2^{2}·5·373 Posts 
Quote:
AMEN!!!! 

20051103, 13:12  #10  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
47×229 Posts 
Quote:
I can think of two reasons for writing an OOP implementation of MPQS. The first is if you are trying to learn how to write nontrivial OOP programs and need to code some algorithm for practice. Almost invariably it's better for a student to code something they find personally interesting than some arbitrary exercise from a book. The second is if you intend your program to be used for pedagogical purposes. As alpertron says, production code is frequently optimised to the point of incomprehensibility. A clearly written though not particularly fast reference implementation of anything nontrivial is of great value. Remember the original post which started thus: Quote:
Paul 

20051103, 13:21  #11  
Aug 2004
202_{8} Posts 
Quote:
:) Chris 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PSIQS java package discussion  Till  Factoring  74  20210724 15:19 
Java applet alternative  a1call  Programming  19  20191108 22:31 
Simple Atkin sieve java example  lucaf  Computer Science & Computational Number Theory  8  20171006 20:56 
Java Quadratic Sieve  Ilya Gazman  Factoring  3  20160222 11:32 
Java based program  GordonBM  Information & Answers  11  20120424 08:27 