20070910, 09:16  #1 
Sep 2007
C_{16} Posts 
Implementing MPQS: SOS!
Hello everybody!
I'd kindly like to ask some help with the implementation of MPQS (it's a university project) algorithm.. I have been reading several papers (as well as this forum) and I wanted to move now to the implementation phase of the MPQS (the time goes fast!:( ) but I think I have still some problems getting a deep understanding of the several issues to be considered.. I read (with different level of understanding) the following papers: C. Siebert, P.S. Contini, M. Kechilbar, B. Kurowski, E. Landquist, N. E. Egge and the book "Prime numbers" by Pomerance and maybe something else I forgot... Actually, it seems that every paper quotes the paper written by R. Silverman (who is a member of this forum, isn't it?) which I couldn't find online and, unfortunately, nor in the national library (means that there isn't a copy of "Math. of Computation n°48 available in Italy, where I live).. Maybe in this essay this is explained better, but I honestly didn't understand how should I select b in the poly.. Contini just says that b can be quickly evaluated by using a modular sqrt alg. and using the Hensel's lifting, Egge says that in [Silverman] it's showed an efficient way to compute b, and it seems that just Kurowski tries to give a formula for this computation (pg. 13).. There, he speaks about "Hegel's theorem", maybe meaning Hensel's lemma? Is this a good way to compute be according to you? Another thing I cannot understand is how to compute efficiently B (the cutoff for the FB).. The formula proposed by Pomerance seems to be just a starting point which in practice doesn't help.. I understood (please tell me if i'm wrong) that evaluating a good cutoff is "an art" due to several factors and it can be increased also to compensate the exclusion of some small primes (e.g p=2) from the Factor Base, isn't it (I read this in the forum)? Since in the paper by Egge are quoted the values (for P (=#FB), M and T) evaluated by Silverman for n having up to 66 digits, I was wondering whether it could be an idea to interpolate these values for n having an intermediate number of digits (e.g. I know an optimal P for n having 54 and 60 digits, can I use an intermediate value for n having 57 dgts)? I'd really appreciate any kind of help, suggestions, links you'd like to give me! Many thanks since now!Bye! Last fiddled with by smoking81 on 20070910 at 10:03 
20070910, 13:46  #2  
Tribal Bullet
Oct 2004
3×1,181 Posts 
Quote:
Quote:
Quote:


20070910, 13:49  #3 
"Ben"
Feb 2007
2×1,789 Posts 
I've also found a good description of the method to compute b in a paper by Johannes Buchmann and Volker Muller called Algorithms for factoring integers. A google search for: johannes buchmann algorithms for factoring integers turns up a link to citeseer where you can download it. This was really helpful for me when implementing MPQS.
 ben. 
20070910, 16:36  #4  
Nov 2003
7460_{10} Posts 
Quote:
http://links.jstor.org/sici?sici=002...3E2.0.CO%3B29 

20070911, 07:06  #5 
Sep 2007
2^{2}×3 Posts 
thank you very much for all of your tips!
i began coding... later i'll try to execute and inform you about my progresses! bye 
20070911, 15:33  #6  
Sep 2007
2^{2}×3 Posts 
Quote:
i decided to use the interpolation of experimental values.. do you know some function in java which performs such an interpolation? Usually, what kind of interpolation is better to use? Linear, polynomial or another kind? thanks! 

20070911, 15:39  #7 
Tribal Bullet
Oct 2004
110111010111_{2} Posts 
You're not going to have many values tabulated, and QS is not very sensitive to the choice of factor base bound as long as you are not far from the optimal value, so an ordinary linear interpolation should be more than sufficient. It's trivial to code up manually.

20070911, 15:44  #8 
Sep 2007
2^{2}·3 Posts 
yes i was thinking the same.. thx!

20070911, 19:39  #9 
Sep 2007
2^{2}·3 Posts 
sorry again for my (very) stupid questions (i don't study mathematics unfortunately! ), but when they advise to use M=50000 to factor n having 42 digits, is this number to be used as the M S.P.Contini speaks about in his paper (e.g. I should use a sieve array of size 2M+1=100001) or I should instead use this M as Contini's M/2 (and hence initialize the sieve with 50001 positions)? Maybe I am getting confused by the tons of papers i have on my desk (and lots of hours spent at the PC)!:)
Another question I have in the mind is about what you wrote here: http://www.mersenneforum.org/showthread.php?t=7212 but I think I'll reply there! many thanks again! 
20070912, 02:47  #10  
Tribal Bullet
Oct 2004
6727_{8} Posts 
Quote:


20071002, 12:30  #11 
Sep 2007
14_{8} Posts 
Hello everybody!
I did my examination today and I passed it with a very good vote (the maximum!). I wish to thank all of the users of this forum for your help and suggestions with MPQS! It was really amusing to work at this project and very helpful to have mersenneforum and its users! Thanks again! Good bye! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
The MPQS differs from the QS  Sam Kennedy  Factoring  3  20121222 15:41 
Implementing Factoring Algorithms  Raman  Hobbies  45  20090511 05:11 
[URGENT] Pain: troubles on implementing SIQS sieve  Hermes  Factoring  27  20081014 13:54 
Implementing Chinese Remainder Theorem in C  ShiningArcanine  Software  3  20071117 05:55 
Implementing algorithms, did I do this right?  ShiningArcanine  Programming  18  20051229 21:47 