From: Pierrick Gaudry
Date: Fri, 20 Mar 2015 15:33:15 +0000 (+0100)
Subject: update a bit the doc for the descent
X-Git-Tag: 2.2.0-rc1~719
X-Git-Url: https://scm.gforge.inria.fr/anonscm/gitweb?p=cado-nfs%2Fcado-nfs.git;a=commitdiff_plain;h=def92d90637f67bda360ea4522fe49a7be9b2fb1
update a bit the doc for the descent
---
diff --git a/scripts/descent.py b/scripts/descent.py
index b257972..6832ad0 100755
--- a/scripts/descent.py
+++ b/scripts/descent.py
@@ -31,6 +31,31 @@
# 24@0 0.0038 0.9945 I=11 50000,22,24,1.2 100000,24,45,1.5
+# Algorithms
+# UpperClass:
+# This is the initialization of the descent. An extended gcd is
+# done between the target and p to get two "rational
+# reconstructions", and then a sieving procedure is done to find a
+# linear combination of these that is smooth (idea taken from
+# Joux-Lercier). This sieving is done with las, with two linear
+# polynomials.
+# At the end, we have target = num/den, where num and den are
+# smooth, with a smoothness bound that is large than the one that
+# was used in the sieving / linear algebra.
+# MiddleClass:
+# For all the primes dividing num and den that are larger than the
+# large prime bound, a "special-q descent" is performed, in order
+# to rewrite them in terms of smaller and smaller elements, until
+# everything is known. This is done with the las_descent program.
+# LowerClass:
+# This step is just putting everything together.
+# In practice, this means computing appropriate Schirokauer maps
+# and propagating the known logarithms in relations in order to
+# deduce the unknown ones. The main tool for that is the
+# reconstructlog program. Some ugly modifications of input files
+# are necessary.
+
+
# TODO: do we want to have default values, as done here, for the --init-*
# arguments ? I would say no.
diff --git a/sieve/README.descent b/sieve/README.descent
index 22d0aac..48d777e 100644
--- a/sieve/README.descent
+++ b/sieve/README.descent
@@ -1,6 +1,11 @@
Using las for the descent
=========================
+NOTE: there is now a general script that can compute the logarithm of a
+given target. See scripts/descent.py . The documentation below is still
+important, since, for instance, it describes how to create a hint file.
+
+
The 'las' binary can be used not only for generating relations in the
factorization or dlp context, but also to "descend" elements in order to
compute the logarithms of elements that are not in the factor base.