mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2006-09-04, 09:35   #1
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default MPQS: choosing a good polynomial

Hi,

in MPQS we generate locations via a polynomial a*x + b;
In MPQS we choose a = d^2 (=p_1 * p_2);
In SIQS we choose a = p_1 * ... * p_k ; p_i different factors of the factor base.
Since this increases k, the possible values for b (|b| = 2^(k-1)) increased as well. So the number of locations generated by one polynomial increases.
What about choosing p_i as a small Factor of the Factor Base like:
First polynom: p_i = 2,
Second polynom: p_i = 3, ..
So k is increased again, and so the number of locations generated by one polynomial increases.
ThiloHarich is offline   Reply With Quote
Old 2006-09-04, 13:58   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110100012 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Hi,

in MPQS we generate locations via a polynomial a*x + b;
In MPQS we choose a = d^2 (=p_1 * p_2);
In SIQS we choose a = p_1 * ... * p_k ; p_i different factors of the factor base.
Since this increases k, the possible values for b (|b| = 2^(k-1)) increased as well. So the number of locations generated by one polynomial increases.
What about choosing p_i as a small Factor of the Factor Base like:
First polynom: p_i = 2,
Second polynom: p_i = 3, ..
So k is increased again, and so the number of locations generated by one polynomial increases.
k is not chosen to be large in order to make the sieving faster. k is large to allow the sieve interval to stay small (increasing the chance that random sieve values will be smooth), while putting off as long as possible the need to fully initialize for the next polynomial. Full initialization requires lots of modular arithmetic, and could dominate the cost of sieving if it happens too often.

The larger k is, the more auxiliary storage you need for switching polynomials. Also, the larger k is the smaller p_i must be. The problem here is that any p_i chosen to be a factor of 'a' values only gets one sieve root and not two, cutting its average contribution to sieve values in half. Selecting p_i too small means that the probability that random sieve values are FB-smooth actually goes down.

In practice, k is chosen to be a compromise between initializing too often and using large p_i. If you can get p_i to be 10-11 bits in size then you can essentially make k anything, but for the largest factorizations you have to increase both k and p_i to avoid huge amounts of auxiliary storage.

jasonp
jasonp is offline   Reply With Quote
Old 2006-09-04, 23:57   #3
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

Since we use a = p^k and p is small, can't we solve the equation b^2 = n mod p^k by solving the equation b^2 = n mod p and lifting the solution via Hensels Lemma? This is what the MPQS does with k=2.
Doing so computing the solutions for a = p^k should be cheap, and changing the polynomial should be cheap as well.
ThiloHarich is offline   Reply With Quote
Old 2006-09-05, 01:45   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33×131 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Since we use a = p^k and p is small, can't we solve the equation b^2 = n mod p^k by solving the equation b^2 = n mod p and lifting the solution via Hensels Lemma? This is what the MPQS does with k=2.
Doing so computing the solutions for a = p^k should be cheap, and changing the polynomial should be cheap as well.
You can do that, but would it let you self-initialize? With different p_i, the chinese remainder theorem lets you build different b values by adding together different combinations of +- F(p_i), for some function F. If all the p_i are the same, wouldn't their F values be identical? I can't see how you would get more than one b value from a particular p.

jasonp
jasonp is offline   Reply With Quote
Old 2006-09-05, 07:51   #5
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

You are right.
Theory tells us that there is only one solution for x^2 = N mod 2^k (if 2 is in the FB).
ThiloHarich is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Good air-cooler good enough for overclocked i7-5820K RienS Hardware 17 2014-11-18 22:58
Choosing the best polynomial wombatman Msieve 123 2013-08-27 11:27
The MPQS differs from the QS Sam Kennedy Factoring 3 2012-12-22 15:41
Implementing MPQS: SOS! smoking81 Factoring 10 2007-10-02 12:30
Linear algebra in MPQS R1zZ1 Factoring 2 2007-02-02 06:45

All times are UTC. The time now is 20:32.

Fri May 7 20:32:18 UTC 2021 up 29 days, 15:13, 1 user, load averages: 9.04, 7.49, 4.73

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.