View Single Post
Old 2021-04-01, 00:02   #12
charybdis's Avatar
Apr 2020

2×7×19 Posts

Originally Posted by swishzzz View Post
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 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
charybdis is offline   Reply With Quote