Implementing MPQS: SOS!

smoking81 · 2007-09-10, 09:16

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!

jasonp · 2007-09-10, 13:46

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.

bsquared · 2007-09-10, 13:49

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.

R.D. Silverman · 2007-09-10, 16:36

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

http://links.jstor.org/sici?sici=002...3E2.0.CO%3B2-9

smoking81 · 2007-09-11, 07:06

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

smoking81 · 2007-09-11, 15:33

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!

jasonp · 2007-09-11, 15:39

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.

smoking81 · 2007-09-11, 15:44

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!

smoking81 · 2007-09-11, 19:39

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!

jasonp · 2007-09-12, 02:47

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.

smoking81 · 2007-10-02, 12:30

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!

2007-09-10, 09:16	#1
smoking81 Sep 2007 2²·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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The MPQS differs from the QS	Sam Kennedy	Factoring	3	2012-12-22 15:41
Implementing Factoring Algorithms	Raman	Hobbies	45	2009-05-11 05:11
[URGENT] Pain: troubles on implementing SIQS sieve	Hermes	Factoring	27	2008-10-14 13:54
Implementing Chinese Remainder Theorem in C	ShiningArcanine	Software	3	2007-11-17 05:55
Implementing algorithms, did I do this right?	ShiningArcanine	Programming	18	2005-12-29 21:47

2007-09-10, 13:49	#3
bsquared "Ben" Feb 2007 3513₁₀ 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-11, 07:06	#5
smoking81 Sep 2007 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

2007-09-11, 19:39	#9
smoking81 Sep 2007 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!

2007-10-02, 12:30	#11
smoking81 Sep 2007 2²×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!