mersenneforum.org Implementing MPQS: SOS!
 Register FAQ Search Today's Posts Mark Forums Read

 2007-09-10, 09:16 #1 smoking81     Sep 2007 22×3 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 2007-09-10 at 10:03
2007-09-10, 13:46   #2
jasonp
Tribal Bullet

Oct 2004

DD916 Posts

Quote:
 Originally Posted by smoking81 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)..
Do you know anyone that has subscription access to jstor.org? I know they have digitized Math. Comp. issues going back forever.
Quote:
 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?
You mean Hensel's Lemma (Hegel was a philosopher). You use this because b^2 has to equal a number modulo a^2 (for prime a) but the ordinary algorithms for finding square roots modulo p break down when p is a power. The formula you need is somewhat difficult to find. I found it on p. 17 of these slides; in general, Hensel lifting looks like Newton's method with modulo computations thrown in.
Quote:
 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)?
The theoretically optimal value of the factor base bound is very conservative for the size of numbers that MPQS is useful for; the bound chosen for an input N should be much smaller. How much smaller is highly implementation dependent and usually determined via tabulation of experimental results, with interpolation to input sizes not in the table, as you suggest. The bounds used in the literature can be either very large or very small.

 2007-09-10, 13:49 #3 bsquared     "Ben" Feb 2007 3,617 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.
2007-09-10, 16:36   #4
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by smoking81 Hello everybody! I'd kindly like to ask some help with the implementation of MPQS (it's a university project) algorithm.. 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
It is available on-line from the AMS. Try

 2007-09-11, 07:06 #5 smoking81     Sep 2007 22·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
2007-09-11, 15:33   #6
smoking81

Sep 2007

22·3 Posts

Quote:
 Originally Posted by jasonp The theoretically optimal value of the factor base bound is very conservative for the size of numbers that MPQS is useful for; the bound chosen for an input N should be much smaller. How much smaller is highly implementation dependent and usually determined via tabulation of experimental results, with interpolation to input sizes not in the table, as you suggest. The bounds used in the literature can be either very large or very small.
hello again!
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!

2007-09-11, 15:39   #7
jasonp
Tribal Bullet

Oct 2004

5·709 Posts

Quote:
 Originally Posted by smoking81 hello again! 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!
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.

2007-09-11, 15:44   #8
smoking81

Sep 2007

148 Posts

Quote:
 Originally Posted by jasonp 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.
yes i was thinking the same.. thx!

 2007-09-11, 19:39 #9 smoking81     Sep 2007 22·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!
2007-09-12, 02:47   #10
jasonp
Tribal Bullet

Oct 2004

5·709 Posts

Quote:
 Originally Posted by smoking81 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)!:)
Who is 'they'? It's traditional to mean that a sieve interval of length M takes on values up to +-M in size, i.e. to use Contini's definition.

 2007-10-02, 12:30 #11 smoking81     Sep 2007 22·3 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post Sam Kennedy Factoring 3 2012-12-22 15:41 Raman Hobbies 45 2009-05-11 05:11 Hermes Factoring 27 2008-10-14 13:54 ShiningArcanine Software 3 2007-11-17 05:55 ShiningArcanine Programming 18 2005-12-29 21:47

All times are UTC. The time now is 02:22.

Fri May 27 02:22:29 UTC 2022 up 43 days, 23 mins, 0 users, load averages: 1.55, 1.53, 1.42