mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-09-10, 09:16   #1
smoking81
 
smoking81's Avatar
 
Sep 2007

C16 Posts
Default 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
smoking81 is offline   Reply With Quote
Old 2007-09-10, 13:46   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by smoking81 View Post
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.
jasonp is offline   Reply With Quote
Old 2007-09-10, 13:49   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

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.
bsquared is offline   Reply With Quote
Old 2007-09-10, 16:36   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by smoking81 View Post
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
R.D. Silverman is offline   Reply With Quote
Old 2007-09-11, 07:06   #5
smoking81
 
smoking81's Avatar
 
Sep 2007

22×3 Posts
Default

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 is offline   Reply With Quote
Old 2007-09-11, 15:33   #6
smoking81
 
smoking81's Avatar
 
Sep 2007

22×3 Posts
Default

Quote:
Originally Posted by jasonp View Post
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!
smoking81 is offline   Reply With Quote
Old 2007-09-11, 15:39   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110101112 Posts
Default

Quote:
Originally Posted by smoking81 View Post
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.
jasonp is offline   Reply With Quote
Old 2007-09-11, 15:44   #8
smoking81
 
smoking81's Avatar
 
Sep 2007

22·3 Posts
Default

Quote:
Originally Posted by jasonp View Post
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 is offline   Reply With Quote
Old 2007-09-11, 19:39   #9
smoking81
 
smoking81's Avatar
 
Sep 2007

22·3 Posts
Default

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!
smoking81 is offline   Reply With Quote
Old 2007-09-12, 02:47   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67278 Posts
Default

Quote:
Originally Posted by smoking81 View Post
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.
jasonp is offline   Reply With Quote
Old 2007-10-02, 12:30   #11
smoking81
 
smoking81's Avatar
 
Sep 2007

148 Posts
Default

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

Thread Tools


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

All times are UTC. The time now is 05:55.


Thu Oct 21 05:55:26 UTC 2021 up 90 days, 24 mins, 1 user, load averages: 0.76, 1.04, 1.11

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.