Discussion related to cado-nfs

[Emmanuel.Thome@inria.fr]

You've encountered a polynomial whose Galois group is Z/2*Z/2. In this
group, there is no element of order four, and by the Artin map it is
impossible to find a prime p that remains prime in the number field
defined by your polynomial f (a so-called "inert prime").

This is a known trap. E.g. in the README file:

    The default square root algorithm does not work in some very rare
    cases that could possibly occur with SNFS polynomials (a degree 4
    polynomial with Galois group $Z/2 \times Z/2$ is the only reasonable
    example, next case is for degree 8). The CRT approach is a
    workaround. See [`sqrt/crtaglsqrt.c`](sqrt/crtaglsqrt.c) .

Admittedly, the reporting by the binary is substandard, since an infinite
loop only leaves you with so much to think about. But on the other hand,
it's rare enough.

Depending on your familiarity with cado-nfs log files, you may find it
either very easy or very hard to use crtalgsqrt and finish your
factorization. In the latter case, please let us know.

Best regards,

E.

On Mon, Aug 03, 2020 at 05:29:24PM +0200, eric.jeancolas@free.fr wrote:
> Hello, 
> 
> 
> I've got a problem similar to some entries under sqrt freeze. Indeed, it's 
> more a loop than a freeze in my case, as CPU is running 100% of available 
> CPU, and Mem is frozen to a definite number, rather low. 
> The number I wanted to factorize is 10^264-8. After some trivial factors, 
> the remaining number to factorize is a c172. 
> 
> 
> If I use the SNFS polynomial 
> 
> 
> n: 
> 1076055610553953428313175224895622605776266517453622003185124607239702147806998665691043128308871002453406792063013816554039512762019541169887659794258167262084104506520897
>  
> skew: 0.14 
> type: snfs 
> c0: 1 
> c2: 50 
> c4: 2500 
> Y0: 10000000000000000000000000000000000000000000 
> Y1: -1 
> # f(x) = 2500*x^4+50*x^2+1 
> # g(x) = -x+10000000000000000000000000000000000000000000 
> 
> 
> I get a loop in the step 2 of the sqrt process. 
> 
> 
> If I use the SNFS polynomial 
> 
> 
> 
> n: 
> 1076055610553953428313175224895622605776266517453622003185124607239702147806998665691043128308871002453406792063013816554039512762019541169887659794258167262084104506520897
>  
> skew: 0.58 
> type: snfs 
> c0: 1 
> c3: 5 
> c6: 25 
> Y0: 100000000000000000000000000000 
> Y1: -1 
> # f(x) = 25*x^6+5*x^3+1 
> # g(x) = -x+100000000000000000000000000000 
> 
> 
> the factorization is done ok. 
> 
> 
> So, of course, there is an answer : use degree 6 polynomial instead of 
> degree 4 ;-) 
> 
> 
> But I think it may be helpful to understand what's going on, and maybe to 
> issue an error exit with an error message instead of the loop. 
> 
> 
> I made tests in cado-nfs-2.3.0 and cado-nfs-3.0.0 (one I downloaded at 
> least one year ago), with 2 different computers, one with 8Gb of RAM and 
> one with 16Gb of RAM. But with tasks.sqrt.threads=1, the memory usage in 
> TOP display is frozen at 2.2 % when the loop occurs on my 16Gb computer... 
> 
> 
> I can PM you whatever you need. You may also compute it if you have 
> available computer power, both SFNS polynomials are rather efficient, deg 6 
> being even more efficient than deg 4. It takes roughly 1 day of computation 
> time on a 4-core computer. 
> 
> 
> Best regards. 

> _______________________________________________
> Cado-nfs-discuss mailing list
> Cado-nfs-discuss@lists.gforge.inria.fr
> https://lists.gforge.inria.fr/mailman/listinfo/cado-nfs-discuss