mersenneforum.org Estimating number of relations needed
 Register FAQ Search Today's Posts Mark Forums Read

2021-04-01, 00:02   #12
charybdis

Apr 2020

223 Posts

Quote:
 Originally Posted by swishzzz Am I correct in understanding from this is that this is due to smooth relations being harder to find in the algebraic ring extension of Z that include a root of poly 2 compared to that for poly 1, and if so is there a good way to estimate the "difficulty" of these polynomials without actually doing the sieving?
Correct. Poly 1 has a lot more roots modulo small primes than poly 2, so there are more possible small factors for the norms, making them more likely to be smooth. You can compare the difficulty of polynomials of the same degree by looking at their Murphy E scores - this is the "combined" score output by msieve, and the "optimal skew" calculator at cownoise.com also tells you the E score. I get a score of 1.240e-11 for poly 1 and 8.189e-12 for poly 2.

In more detail: if p is not 1 mod 5 (or 2), then 16x^5 + n has exactly one root mod p, because 5 is coprime to p-1 and so x -> x^5 is a bijection mod p (ie every element has a unique 5th root). If p is 1 mod 5, then either 16x^5 + n has 5 roots (with probability 1/5) or no roots (probability 4/5).

So 16x^5 + n will be easier if a lot of small p = 1 mod 5 happen to give the full set of 5 roots. Your poly 1 is very lucky in that it has 5 roots mod 11, 31 and 61, whereas the first prime to which poly 2 has 5 roots is 181. In addition, poly 2 does not have roots mod 9 or 49 (since the coefficient 198345 is divisible by 3 and 7 but not 9 or 49), whereas poly 1 does.

Last fiddled with by charybdis on 2021-04-01 at 00:05

 2021-04-01, 13:42 #13 swishzzz   Jan 2012 Toronto, Canada 3916 Posts Appreciate the detailed response! That was exactly what I wanted to find out

 Similar Threads Thread Thread Starter Forum Replies Last Post CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46 CRGreathouse Factoring 16 2014-03-10 03:40 CRGreathouse Factoring 0 2014-03-02 04:18 henryzz Math 7 2012-05-23 01:13 bchaffin Factoring 24 2012-03-24 18:37

All times are UTC. The time now is 21:11.

Sun Apr 11 21:11:04 UTC 2021 up 3 days, 15:51, 1 user, load averages: 1.36, 1.74, 1.92