Discussion related to cado-nfs

[Emmanuel Thomé <Emmanuel.Thome@inria.fr>]

Hi,

On Mon, Feb 27, 2017 at 09:31:06PM +0300, Христофор Бобров wrote:
> Hello! In some cases, the computation of an individual logarithm takes
> a very long time. The descent In the file.you receive a stream of
> output to stdout # to walk the path: 20@0 -> loop (#1) 0 980963
> 334145... It's related in the fact that the found correlations not
> found the logarithm of the target ? When reducing tasks.sieve.qmin this
> problem does not occur. I would like to know what caused this problem
> and how to solve it. To the letter attach 4 files with examples. Target
> p60_1 is present this trouble.

Thanks for your report.

This is apparently stuck in an endless loop, and will never finish,
unfortunately.

I've been able to reproduce this behaviour.

What happens is that when trying to descend some ideal q1, the program
picks a relation involving an ideal q2, and when it tries to descend q2,
all it gets is a relation involving q1. Since the program is not
satisfied with this looping behaviour, it tries harder on q2, increasing
the lpb, to see whether a better relation can be found.

This approach has several shortcomings.

 - First off, it's admittedly rather simple-minded. One may consider
   backtracking to q1 instead, for example. It's not clear that this
   backtracking approach would be a way to go, though: the inherently
   hairy logic that would go with it would be error-prone, at best.

 - "Trying harder" by just increasing lpb is also very crude. It could
   make sense to increase I as well (which governs the size of the
   sieving area). This stuff happens around line 3144 in las.cpp. I would
   give a try to adding the line:
    current_config->logI += next_todo->iteration / 4;
   for instance, but currently this does not work (see later).

 - The size of the sieving area, again, is controled by I (actually,
   tasks.descent.init_I). One expects a sieving area of size roughly
   2^(2*I-1). In some cases though, it can be much much less, depending
   on the ideal basis depending on q. This is a misbehaviour of cado-nfs
   which we should fix. To diagnose this, it would be interesting if you
   could send the file /home/user/dlp/60_ok/p60.descent.4.middle.rels ; 

For more serious computations, one would counter the "I is too small"
effect by crafting a "hint file", which decides on sieving parameters (I,
factor base bounds, large prime bounds) which depend on the size of the
special-q. It is not anticipated that going to such trouble is necessary
for a p60, though. A stub p60.hint can be found in
parameters/dlp/p60.hint. It seems to me that that file could be improved,
although the mechanism to really make it useful has been inadvertently
castrated (a failing assert in the code).

Short of any better suggestion for now before we look at how to fix this,
you can adjust the parameters as in the attached patch. But it's really a
quick and dirty fix.

E.

diff --git a/parameters/dlp/p60.hint b/parameters/dlp/p60.hint
index 44d4f0274..6cda55bda 100644
--- a/parameters/dlp/p60.hint
+++ b/parameters/dlp/p60.hint
@@ -1,5 +1,9 @@
-22@0 0.0038 0.9940 I=11 100000,22,24 100000,22,24
-22@1 0.0038 0.9995 I=11 100000,22,24 100000,22,24
-23@0 0.0038 0.9945 I=11 100000,22,24 100000,23,25
-23@1 0.0038 0.9990 I=11 100000,22,24 100000,22,24
-24@0 0.0038 0.9945 I=11 100000,22,24 100000,24,45
+20@0 0.1 1 I=12 200000,19,3 200000,20,3
+20@1 0.1 1 I=12 200000,19,3 200000,19,3
+21@0 0.1 1 I=12 200000,20,3 200000,21,3
+21@1 0.1 1 I=12 200000,20,3 200000,20,3
+22@0 0.1 1 I=12 200000,21,3 200000,22,3
+22@1 0.1 1 I=12 200000,21,3 200000,21,3
+23@0 0.1 1 I=12 200000,22,3 200000,23,3
+23@1 0.1 1 I=12 200000,22,3 200000,22,3
+24@0 0.1 1 I=12 200000,22,3 200000,24,3
diff --git a/parameters/dlp/params.p60 b/parameters/dlp/params.p60
index 895075b04..ffa9b2e32 100644
--- a/parameters/dlp/params.p60
+++ b/parameters/dlp/params.p60
@@ -77,16 +77,16 @@ tasks.reconstructlog.partial=false
 # Individual log
 ###########################################################################
 
-tasks.descent.init_I = 11
+tasks.descent.init_I = 12
 tasks.descent.init_ncurves = 10
 tasks.descent.init_lpb = 24
 tasks.descent.init_lim = 100000
 tasks.descent.init_mfb = 48
 tasks.descent.init_tkewness = 200000
-tasks.descent.I = 11
-tasks.descent.lim0 = 100000
-tasks.descent.lim1 = 100000
+tasks.descent.I = 12
+tasks.descent.lim0 = 200000
+tasks.descent.lim1 = 200000
 tasks.descent.lpb0 = 22
 tasks.descent.lpb1 = 22
-tasks.descent.mfb0 = 44
-tasks.descent.mfb1 = 44
+tasks.descent.mfb0 = 45
+tasks.descent.mfb1 = 45