Go Back > Factoring Projects > Msieve

Thread Tools
Old 2021-04-01, 00:02   #12
Apr 2020

223 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
Old 2021-04-01, 13:42   #13
Jan 2012
Toronto, Canada

3916 Posts

Appreciate the detailed response! That was exactly what I wanted to find out
swishzzz is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Estimating the number of primes in a partially-factored number CRGreathouse Probability & Probabilistic Number Theory 15 2014-08-13 18:46
Estimating time needed for GNFS CRGreathouse Factoring 16 2014-03-10 03:40
Estimating time needed for GNFS CRGreathouse Factoring 0 2014-03-02 04:18
Estimating the number of prime factors a number has henryzz Math 7 2012-05-23 01:13
Estimating minimum relations 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

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.