Discussion related to cado-nfs

[eric.jeancolas@free.fr]

Ah ok, as you mentionned, I thought this situation was rare enough not to 
encounter it!
As the deg 6 polynomial gave me the result, I will not proceed on this case.
At least, I've got the answer, and it is shared on the group.
Thank you for that.
Best regards.
Eric
----- Mail original -----
De: "Emmanuel Thome" <Emmanuel.Thome@inria.fr>
À: cado-nfs-discuss@lists.gforge.inria.fr
Envoyé: Lundi 3 Août 2020 17:44:00
Objet: Re: [Cado-nfs-discuss] Infinite loop in sqrt

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

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