est destinée au dépôt

What is the role of visualization in academic research?

• Publications

• The exact representation of data in all their shades • Then people look at the figures first, so they have to be « sexy »

• For posters, orals ,presentations, etc.

• As in any form of communication, the most important is the message.

• Clarity • Efficiency

• Open Science Visualization 1 -How are bakers' practices structured?

• Is there a structure?

• What are the most differentiating practices?

• This is a scientific paper, so it is mendatory to illustrate both methods and results.

Visualization 1 -How are bakers' practices structured?

Visualization 2 -What does structure microbial diversity?

• The type of baker

• The microbial diversity

• The Geography

What's the big deal?

• Translate complex analyses into clear visualizations

• We quickly come across trade-offs

• Complexity/understanding • Variability/Message
• Reproducibility of analyses and graphs

• Here the graphs are 95% made with R -with some finishing under a vectorial drawing software (inkscape or Affinity Designer).

• The diversity of questions and scientific methods force us to always look for the most adequate representation.

•

  Data availability • Reproducibility of scripts for analyses AND graphs The Bakery project • It is a participative project, thus created with and animated by the actors of the field • Sourdough bread • Influence of practices on bread quality and microbial diversity A lot of data !! • Lots of bakers all over France • Several types of flours, different types of practices • Lots of measurements on bread and microbial diversity (yeasts and bacteria)

Data visualization in academic research

Thibault Nidelet

To cite this version:

Thibault Nidelet. Data visualization in academic research. 2020. hal-02963940

Data visualization in academic research

The case of the BAKERY project Thibault Nidelet -UMR Science Pour l'Oenologie thibault.nidelet@inrae.fr @ThibaultNidelet


Madhurima Mukhopadhyay

Palash Sarkar
email: palash@isical.ac.in

Shashank Singh
email: shashank@iiserb.ac.in

Emmanuel Thomé
email: emmanuel.thome@inria.fr

New Discrete Logarithm Computation for the Medium Prime Case Using the Function Field Sieve

Keywords: finite field, discrete logarithm, function field sieve. MSC (2010): 11Y16, 94A60

The present work reports progress in discrete logarithm computation for the general medium prime case using the function field sieve algorithm. A new record discrete logarithm computation over a 1051-bit field having a 22-bit characteristic was performed. This computation builds on and implements previously known techniques. Analysis indicates that the relation collection and descent steps are within reach for fields with 32-bit characteristic and moderate extension degrees. It is the linear algebra step which will dominate the computation time for any discrete logarithm computation over such fields.

Introduction

Let p be a prime and n be a positive integer. Let F p n be the finite field consisting of p n elements. Let g be a generator of the cyclic group of all non-zero elements of F p n . The discrete logarithm problem in F p n is the following. Given a non-zero element h of F p n , find i such that h i = g. The computational difficulty of the discrete logarithm problem forms the basis for the security of cryptographic primitives such as the Diffie-Hellman key agreement scheme [START_REF] Diffie | New directions in cryptography[END_REF] and the Digital Signature Algorithm [START_REF]Digital Signature Algorithm[END_REF].

Let Q = p n and L Q (a, c) with 0 < a < 1 and c > 0 denote the sub-exponential expression

L Q (a, c) = exp (c + o(1))(ln Q) a (ln ln Q) 1-a .
Writing p = L Q (a, c) leads to several cases: a > 2/3 is called the large characteristic case, a = 2/3 is called the boundary case, 1/3 ≤ a < 2/3 is called the medium prime case while a < 1/3 is called the small characteristic case.

There are two major sub-exponential time algorithms for solving the discrete logarithm problem over a finite field, namely the number field sieve (NFS) [START_REF] Daniel | Discrete logarithms in GF(p) using the number field sieve[END_REF] and the function field sieve (FFS) [START_REF] Adleman | The function field sieve[END_REF][START_REF] Adleman | Function field sieve method for discrete logarithms over finite fields[END_REF][START_REF] Joux | The function field sieve is quite special[END_REF]. Both algorithms have seen substantial improvements over time and several variants of these algorithms are presently known. In the present state of the art, the NFS is generally used for large characteristic fields while the FFS is used for small to medium characteristic fields. In this work, we will consider discrete logarithm computation for a medium characteristic prime using the FFS.

For the small characteristic case, there has been a tremendous amount of progress in the FFS algorithm [START_REF] Göloglu | Solving a 6120-bit DLP on a desktop computer[END_REF][START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities -application to discrete logarithms in F 2 1971 and F 2 3164[END_REF][START_REF] Detrey | Relation collection for the function field sieve[END_REF][START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Barbulescu | A heuristic quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF][START_REF] Granger | Breaking '128-bit secure' supersingular binary curves -(or how to solve discrete logarithms in F 2 4[END_REF][START_REF] Adj | Weakness of F 6 6•1429 and F 2 4•3041 for discrete logarithm cryptography[END_REF]. A quasi-polynomial time algorithm has been obtained in [START_REF] Barbulescu | A heuristic quasipolynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]. Record discrete logarithm computations have been made over large fields such as F 2 9234 [START_REF] Granger | Discrete logarithms in GF (2 9234 )[END_REF] and F 2 30750 [START_REF] Granger | Discrete logarithms in GF (2 30750 ). NM-BRTHRY list[END_REF]. [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF] 25 47 1175 20 0.77 Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF] 25 57 1425 20 0.13

There has also been progress in discrete logarithm computation using the FFS for the medium prime case. This progress, however, has not been as remarkable as in the small characteristic case. We briefly summarise the previous works. Important simplification of the FFS was made by Joux and Lercier [START_REF] Joux | The function field sieve in the medium prime case[END_REF]. The next work was by Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF] who introduced the important idea of pinpointing. Later work by Sarkar and Singh [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] performed a detailed asymptotic analysis.

All three of the works [START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] reported discrete logarithm computations. These are summarised in Tables 1 and2. Table 1 compares the various discrete logarithm computations in the medium prime case using the FFS algorithm. For Kummer extensions, the condition n | (p -1) holds. Comparison of previously performed discrete logarithm computations for Kummer extensions are shown in Table 2. In Tables 1 and2, #B is the size of the factor basis. The parameter Λ is a measure of the feasibility of 2-1 descent. The lower the value of Λ, the more difficult it is to carry out a 2-1 descent. We provide the definition of Λ and explain its connection to the difficulty of 2-1 descent later.

The present work represents progress in the discrete logarithm computation for the medium prime case using the FFS algorithm. The challenge was to perform a larger discrete logarithm computation for a medium prime case field than what has been reported earlier. To keep the problem general, we decided not to work with Kummer extensions. We chose a 1051-bit field having a 22-bit characteristic and extension degree 50 as our target. While the size of this field is smaller than the 1175-bit and the 1425-bit fields considered by Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF], the Kummer extension property of the latter two fields make the discrete logarithm computation much easier than the field considered in this work. In particular, for the fields considered in [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF], 20-bit factor bases suffice whereas in our case a 23-bit factor basis is required. Also, the 2-1 descent for the field considered in this work is more difficult than those considered in [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF]. This is indicated by the value of Λ in Tables 1 and2. More details on the 2-1 descent are provided later.

For our computation, the main techniques that were used are from [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]. Applying these techniques to a larger field, on the other hand, created complications, especially in the descent step. This required building on and implementing the alternating walk and branching technique. We considered the feasibility of using the FFS algorithm to solve a discrete logarithm challenge for a field having a 32-bit characteristic and extension degree 17. For this challenge, the relation collection and the descent phases are well within reach. The linear algebra step, on the other hand, will require much more time. The ability to solve the discrete logarithm challenge depends on the feasibility of the linear algebra step.

Function Field Sieve in the Medium Prime Case

We provide a brief description of the FFS algorithm for the medium prime case. For details we refer to [START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]. We will assume that the extension degree n is greater than 1.

Representation of F p n :

The first task is to choose a convenient representation for F p n .

Choose n 1 , n 2 and k to be positive integers less than n. Let g 1 (X) = X -n 1 and g 2 (X) be a polynomial over F p of degree n 2 . Write X k -g 2 (g 1 (X)) = f 1 (X)/X n 1 n 2 , where f 1 (X) is a polynomial of degree n 1 n 2 + k. The idea is to choose g 2 (X) to be a polynomial over F p of degree n 2 such that f 1 (X) has an irreducible factor f (X) of degree n. Since the degree of

f 1 (X) is n 1 n 2 + k, n ≤ n 1 n 2 + k. If n = n 1 n 2 + k,
then experiments show that it is possible to choose g 2 (X) such that f 1 (X) itself is irreducible. In this case, we take f (X) to be equal to f 1 (X).

The field F p n is represented as

F p [x]/(f (x)). Let y = g 1 (x) = x -n 1 . Then x k -g 2 (y) = f 1 (x)/x n 1 n 2 . Since f (x) | f 1 (x)
, the relation x k = g 2 (y) holds in F p n . For k = 1, this method was described by Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF]. In the following, we will assume k = 1, y = g 1 (x) = x -n 1 and x = g 2 (y) since these are the choices we use in our discrete logarithm computation. For other variants of choosing the field representation, we refer to [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF].

Choice of generator:

The non-zero elements of F p n forms a cyclic group under multiplication. Discrete logarithms are computed with respect to some generator. The actual choice of a generator is not important. It usually turns out that one of the polynomials x + a is a generator for some a ∈ F p .

Factor basis: The factor basis is B = {(x + a i ), (y + b j ) : a i , b j ∈ F p }. There are 2p elements in B.

For certain extension fields, by using the action of Frobenius it is possible to reduce the size of the factor basis by a factor of n. Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF] showed this for Kummer extensions, i.e., for fields F p n such that n | (p -1). An advantage of Kummer extensions is that the size of the factor basis reduces by a factor of n, making it possible to perform discrete logarithm computations on larger fields. This can be seen from Tables 1 and2. The condition n | (p -1), however, is very special and is unlikely to hold for general p and n. Due to this reason, we do not consider this condition in our work.

Modulus of discrete logarithms:

The requirement is to compute the discrete logarithm modulo p n -1. In practice, p n -1 is factored and the FFS algorithm is used to compute the discrete logarithm modulo the large prime factors. Let M = (p n -1)/(p -1). The discrete logarithms of elements of F p are equal to 0 modulo M and so in the computation of discrete logarithm modulo a large prime factor of M , one may ignore the discrete logarithms of the elements of F p . See [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] for an explanation.

Relation Collection

For arbitrary elements a, b, c ∈ F p , consider the expression (x + a)y + (bx + c) = xy + ay + bx + c. Using y = g 1 (x) = x -n 1 and x = g 2 (y), this expression can be written in two different ways as follows.

xg 1 (x) + ag 1 (x) + bx + c = (x + a + bx n 1 +1 + cx n 1 )/x n 1 = h 1 (x)/x n 1 ;
(1)

yg 2 (y) + ay + bg 2 (y) + c = h 2 (y). (2)
Note that h 1 (x) is a polynomial of degree n 1 + 1 and h 2 (y) is a polynomial of degree n 2 + 1. Over F p n , we have h 1 (x)/x n 1 = h 2 (y). Suppose that both h 1 (x) and h 2 (y) are smooth polynomials, i.e.,

h 1 (x) = b Π α i (x + α i ) and h 2 (y) = d 1 Π β j (y + β j ) for some d 1 ∈ F p .
Then, over F p n , we have the relation

h 1 (x)/x n 1 = b Π α i (x + α i )/x n 1 = d 1 Π β j (y + β j ) = h 2 (y). (3)
This gives the following linear equation among the discrete logarithms of the elements of the factor basis.

-n 1 log x +

α i log(x + α i ) = β j log(y + β j ) mod M.
Each such linear equation involves n 1 + n 2 + 1 terms. The factor basis contains 2p elements. To be able to solve the system of linear equations arising from linear equations of the above type, a little more than 2p relations are required. The free parameters are a, b and c giving rise to p 3 expressions of the type xy + ay + bx + c. Heuristically, we may assume that the p 3 expressions give rise to p 3 /((n 1 + 1)!(n 2 + 1)!) linear equations. So, for the relation collection phase to succeed, the following condition has to hold.

p 3 (n 1 + 1)!(n 2 + 1)! > 2p. (4)
Pinpointing: The idea of pinpointing was introduced by Joux [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF] to speed up relation collection.

Suppose that for some choice of a, b and c, the polynomial h 1 (x) turns out to be smooth, i.e.,

x

+ a + bx n 1 +1 + cx n 1 = bΠ α i (x + α i ). ( 5
)
Using the transformation x → tx, for t ∈ F p \ {0, 1}, the right side of ( 5) remains smooth, while the left hand side corresponds to the expression obtained from a = a, b = bt n 1 +1 and c = ct n 1 . So, once a smooth h 1 (x) is obtained, by varying t over all elements of F p , it is possible to obtain p -2 smooth h 1 (x)'s without any further smoothness checking.

In [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF], it was shown that the number of trials required for obtaining a single relation which has both sides smooth is

(n 1 + 1)!(n 2 + 1)! p -1 + min ((n 1 + 1)!, (n 2 + 1)!) . (6)
It was shown in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] that the idea of smoothness checking can be combined with a sieving procedure which entirely avoids smoothness checking. Our implementation uses the sieving based pinpointing algorithm.

Linear Algebra

The relation collection phase produces a little more than 2p linear equations involving the discrete logarithms of the elements of the factor basis. Each equation has n 1 + n 2 + 1 terms. Additionally, we include the linear equation log y = -n 1 log x to account for the relation y = x -n 1 between x and y.

The obtained system of linear equations is sparse. Techniques from sparse linear algebra are used to solve the linear system. The standard methods for solving a sparse linear system is either the Lanczos algorithm or the block Wiedemann algorithm. For a factor basis of size B, the cost of both the methods is O(B 2 ). The second method is preferable as it can be parallelised. We have used the block Wiedemann algorithm implemented in the CADO-NFS [START_REF]CADO-NFS, an implementation of the number field sieve algorithm[END_REF] to complete the linear algebra step.

The system of inhomogenous linear equations is given by a matrix M and a coefficient vector b. Before attempting to solve the system, a filtering step is applied. The goal of the filtering step is reduce the size of the matrix and/or make it more sparse. The basic filtering that we applied was to remove duplicate rows and empty columns of the matrix M. It is possible to apply other more sophisticated filtering methods.

It is usually assumed that the relation collection step provides relations involving all elements of the factor basis. There is no proof that this will necessarily be the case. Our computation shows that this assumption need not be true, i.e., there could be elements of the factor basis which are not part of any relation. We provide more details later.

Individual Descent

Let Π(x) be the target element whose discrete logarithm is to be computed. Typically, Π(x) will be a polynomial of degree n -1. After the linear algebra step, assume that we have computed the discrete logarithms of all linear polynomials of the form x+α i and y +β j . So, the goal is to be able to express Π(x) as a rational function where both the numerator and the denominator are products of linear polynomials. This procedure is called descent.

The entire descent is not done in a single step. The target polynomial is successively descended to lower degree polynomials until finally descent to linear polynomials become possible. For the initial descent, a simple randomisation strategy usually works. Suppose we wish to descend from an irreducible polynomial φ(x). Choose a random polynomial D(x) whose factors are of lower degree than that of φ(x). Let N (x) = φ(x)D(x) mod f (x). If the factors of N (x) are also of degrees lower than that of φ(x), then since φ(x) = N (x)/D(x), we have a descent from φ(x) to lower degree factors of N (x) and D(x). If these factors are not linear, then they would require to be further descended. More systematic techniques for descent are known. A method based on computing the kernel of a matrix has been described in [START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | Algorithmic Cryptanalysis[END_REF]. Another method has been used in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] and we provide further details in the next section.

The descent becomes more difficult as the degree of the polynomials become close to 1 with the 2-1 descent (i.e., descent from quadratic to linear polynomials) being the most difficult. A heuristic argument has been used to show that the probability of a successful 2-1 descent in a single trial is 1/((n 1 -1)!(n 2 + 1)!) [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]. The work [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] provides the probability of a successful d-(d -1) descent (i.e., descent from a degree d polynomial to polynomials of degrees at most d) for d ≥ 2. In an asymptotic setting the effect of d-(d -1) descent on the overall time for solving discrete logarithm has been analysed in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]. It has been shown that for d > 2, the asymptotic cost of d-(d -1) descent is always lower than the asymptotic cost of relation collection. On the other hand, for d = 2, there are situations where the asymptotic cost of 2-1 descent is more than the asymptotic costs of the other two phases.

Following the methods of [START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF], using a single degree of freedom, the heuristic probability of success for a 2-1 descent is 1/((n 1 -1)!(n 2 + 1)!). So, the number of trials required for a single 2-1 descent is about

(n 1 -1)!(n 2 + 1)!. ( 7
)
With a single degree of freedom, the number of trials that can be made is p.

Let Λ = p (n 1 -1)!(n 2 + 1)! . (8)
It has been suggested in [START_REF] Joux | The function field sieve in the medium prime case[END_REF][START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF][START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]] that for a 2-1 descent to be possible, Λ ≥ 1 has to hold. Experiments show that while Λ ≥ 1 makes the descent easy, it may be possible to perform a 2-1 descent even when Λ < 1. The parameter Λ does, however, play a role in determining the ease of descent. The higher the value of Λ, the easier is a 2-1 descent, while for lower values of Λ, a direct 2-1 descent may not be possible and one would have to use walk and/or branching techniques (as explained in the next section).

Final Discrete Logarithm Computation

The linear algebra step provides the discrete logarithm of the elements of the factor basis elements modulo the large prime divisors of p n -1. So, once the descent step is completed, it is possible to compute the discrete logarithm of the target element modulo the large prime divisors of p n -1. The discrete logarithm of the target element modulo the smaller factors of p n -1 are computed using the Pollard rho and the Pohlig-Hellman algorithm. Finally, all the discrete logarithms are combined using the Chinese remainder theorem to obtain the discrete logarithm of the target element modulo p n -1.

Sieving Using Partial Smoothness-cum-Divisibility

The technique of smoothness-cum-divisibility and a sieving method based on it was introduced in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF].

Here we provide a brief account of this method based on the relations y = g 1 (x) = x -n 1 and x = g 2 (y).

(This description is somewhat different from the one in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] which was based on y = g 1 (x) = x n 1 and x = g 2 (y).) Let φ(x) be a polynomial of degree d ≥ 0. Let T (x, y) be a bivariate polynomial and let F (x) and C(y) be such that T (x, g 1 (x)) = F (x)/x n 1 and C(y) = T (g 2 (y), y). The polynomial T (x, y) is said to be good for φ(x) if φ(x) divides F (x) and both G(x) = F (x)/φ(x) and C(y) are smooth, i.e., can be factored into linear polynomials. Note that F (x) = Res y (T (x, y), x n 1 y -1), and C(y) = Res x (T (x, y), x -g 2 (y)).

Suppose T (x, y) is a monic polynomial which has a total of ρ + 1 monomials. We assume d < ρ. Let the degrees of F (x) and C(y) be ρ 1 and ρ 2 respectively. The degree of G(x) is ρ 1 -d. Let e = ρ -d which represents the degree of freedom. Let us write

F (x) = φ(x)(x -a 1 ) • • • (x -a e )H(x) (9)
for some polynomial

H(x) of degree h = ρ 1 -d -e. So, G(x) = (x -a 1 ) • • • (x -a e )H(x).
If we can find a 1 , . . . , a e ∈ F p such that F (x) can be written as in [START_REF] Daniel | Discrete logarithms in GF(p) using the number field sieve[END_REF], then we are able to ensure that F (x) is divisible by φ(x) and partial smoothness of G(x). By trying various values of a 1 , . . . , a e , the smoothness of H(x) and the corresponding C(y) has to be ensured. A sieving based method for implementing this idea has been described in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF].

The partial smoothness-cum-divisibility technique is useful for both relation collection and the descent step. In the context of relation collection, we set T (x, y) = xy + ay + bx + c and φ(x) = 1 so that ρ = 3 and d = 0 leading to e = ρ -d = 3. The resulting sieving technique can be combined with pinpointing. We refer to [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] for further details.

For application to the descent step, the 2-1 descent is described in details in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] since it is for such descent that the partial smoothness-cum-divisibility technique was applied. Here we describe how the technique can be used for d-(d -1) descent for d ≥ 2. Let φ(x) be a polynomial of degree d and the goal is to descend to polynomials of degrees less than d. Let ρ = d + 1 so that e = ρ -d = 1, providing a single degree of freedom. With e = 1, we have

F (x) = φ(x)(x -α)H(x) (10)
where degree of H(x) is h. The ρ undetermined coefficients of T (x, y) appears in F (x). As before, let

G(x) = (x -α)H(x).
Consider α to be a symbolic variable. From (10) and using a method described in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF], it is possible to symbolically solve for the coefficients of H(x) and F (x) in terms of α. The symbolic computation is a one-time task.

We provide an example of the symbolic computation. Suppose n = 49 = n 1 n 2 with n 1 = n 2 = 7, T (x, y) = xy + ax + by + c where a, b and c are undetermined elements of F p . Then F (x) = T (x, x n 1 ) is a polynomial of degree ρ 1 = 8. Let φ(x) = q 0 + q 1 x + q 2 x 2 , where q 0 , q 1 , q 2 ∈ F p . So, d = 2, e = 1 and from [START_REF] Granger | Breaking '128-bit secure' supersingular binary curves -(or how to solve discrete logarithms in F 2 4[END_REF], the degree h of H(x) is 5. Symbolic computation using SAGE [START_REF] Stein | Sage Mathematics Software[END_REF] provides 5 where h 0 , . . . , h 4 are as follows.

H(x) = h 0 + h 1 x + • • • + h 4 x 4 + x
h 0 = -(α 5 q 5 1 -α 4 q 0 q 4 1 + α 3 q 2 0 q 3 1 -α 2 q 3 0 q 2 1 + αq 4 0 q 1 -q 5 0 + (3α 5 q 2 0 q 1 -α 4 q 3 0 )q 2 2 -(4α 5 q 0 q 3 1 -3α 4 q 2 0 q 2 1 + 2α 3 q 3 0 q 1 -α 2 q 4 0 )q 2 )/∆(α); h 1 = q 2 0 q 3 2 -α 4 q 5 1 + α 3 q 0 q 4 1 -α 2 q 2 0 q 3 1 + αq 3 0 q 2 1 -q 4 0 q 1 -(3α 5 q 0 q 2 1 + α 4 q 2 0 q 1 )q 2 2 + (α 5 q 4 1 + 3α 4 q 0 q 3 1 -2α 3 q 2 0 q 2 1 + α 2 q 3 0 q 1 )q 2 )/∆(α); h 2 = (2α 5 q 0 q 1 q 3 2 -α 3 q 5 1 + α 2 q 0 q 4 1 -αq 2 0 q 3 1 + q 3 0 q 2 1 -(α 5 q 3 1 + 2α 4 q 0 q 2 1 + 2α 3 q 2 0 q 1 -α 2 q 3 0 )q 2 2 +(α 4 q 4 1 + 3α 3 q 0 q 3 1 -2α 2 q 2 0 q 2 1 + αq 3 0 q 1 -q 4 0 )q 2 )/∆(α); h 3 = -(α 5 q 0 q 4 2 + α 2 q 5 1 -αq 0 q 4 1 + q 2 0 q 3 1 -(α 5 q 2 1 + α 4 q 0 q 1 + α 3 q 2 0 )q 3 2 +(α 4 q 3 1 + 2α 3 q 0 q 2 1 + 2α 2 q 2 0 q 1 )q 2 2 -(α 3 q 4 1 + 3α 2 q 0 q 3 1 -2αq 2 0 q 2 1 + 2q 3 0 q 1 )q 2 )/∆(α); h 4 = -(α 5 q 1 q 4 2 + αq 5 1 -q 0 q 4 1 -(α 4 q 2 1 + α 3 q 0 q 1 )q 3 2 + (α 3 q 3 1 + 2α 2 q 0 q 2 1 + αq 2 0 q 1 -q 3 0 )q 2 2 -(α 2 q 4 1 + 3αq 0 q 3 1 -3q 2 0 q 2 1 )q 2 )/∆(α), where ∆(α) = α 5 q 5 2 -q 5 1 -(α 4 q 1 + α 3 q 0 )q 4 2 + (α 3 q 2 1 + 2α 2 q 0 q 1 + αq 2 0 )q 3 2 -(α 2 q 3 1 + 3αq 0 q 2 1 + 3q 2 0 q 1 )q 2 2 + (αq 4 1 + 4q 0 q 3 1 )q 2 .

Once the polynomial φ(x) in ( 10) is fixed, the coefficients of H(x) and G(x) are functions of α. For each possible value of α, denote the corresponding H(x) and G(x) as H α (x) and G α (x) respectively. Next, for each possible value of α ∈ F p , compute the coefficients of H α (x) and hence obtain G α (x) = (x -α)H α (x). Store all the G α (x)'s in a list L. After G α (x) has been added to L for all α ∈ F p , sort L. If a G(x) occurs h -d + 2 or more times in the list, then at least h -d + 2 roots of G(x) have been encountered in the sieving process. The remaining factor of G(x) has degree at most d -1 and so G(x) is (d -1)-smooth. For such a G(x), construct the corresponding F (x) as φ(x)G(x). Using Proposition 1 of [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF], obtain C(y) and check whether C(y) is also (d -1) smooth. If it turns out that C(y) is indeed (d -1) smooth, then we have

φ(x) = x n 1 C(y) G(x)
where both C(y) and G(x) are (d -1)-smooth. So, it has been possible to descend from the polynomial φ(x) of degree d to the polynomials C(y) and G(x) which are (d -1)-smooth. Note that for d > 2, while aiming for d-(d -1) descent, it might be possible to reach smaller degrees if in the sieving process, a G(x) appears more than h + d -2 times. The above description is for descending from a polynomial φ(x). A similar method works for descending from a polynomial ψ(y).

Suppose the above method is not successful, i.e., the sieving procedure does not result in a suitable G(x) and C(y). At this point, there are several ways to proceed.

The x-x walk: Suppose the sieving procedure results in a G(x) which has h -d + 1 linear factors. Then the other factor of G(x) is of degree d. Let this factor be φ 1 (x). Further, suppose that C(y) turns out to be (d -1)-smooth. Then, in effect, we have moved from a φ(x) of degree d to the polynomial φ 1 (x) also of degree d. Descent may now be attempted from φ 1 (x). Similarly, one may need to move from a polynomial ψ(y) of degree d to a polynomial ψ 1 (y) also of degree d and try to descend from ψ 1 (y). Such a method is called the walk technique.

The x-y walk: Suppose the sieving procedure results in a desirable G(x), i.e., one that has at least h-d+2 linear factors. On the other hand, suppose that the corresponding C(y) turns out to be d-smooth, instead of being (d -1)-smooth. For each factor ψ(y) of C(y) of degree d, one may try to descend to lower degree polynomials.

Similarly, one may define the y-y and the y-x walks. It is possible that neither x-x nor x-y walks succeed for a polynomial φ(x) of degree d. Then the following strategies can be tried.

1. Move from a single degree d polynomial in x to two degree d polynomials in x.

2. Move from a single degree d polynomial in x to one degree d polynomials in x and one degree d polynomial in y.

Analogous strategies hold for moving from a degree d polynomial ψ(y) in y. Since this strategy moves from a single degree d polynomial to two degree d polynomials, it is called a branching strategy. The walk and branching strategies were briefly mentioned in [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF]. Detailed discussion of these strategies in the context of 2-1 descent is given in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF]. The computations in [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF] used these techniques only for 2-1 descent. For the present computation, we needed the walk technique for both 3-2 and 2-1 descent.

For the x-y walk, an important implementation issue is to avoid cycling. Suppose the x-y walk starts from φ(x). It is possible that after a number of steps, the walk again enters φ(x). This is called cycling. In the presence of cycling, the descent fails. By suitably using randomisation, it is usually possible to avoid such cycling. Alternatively, cycle detection algorithms may be used to detect the presence of cycling and abort.

A Concrete Discrete Logarithm Computation

In this section, we present the details of an actual discrete logarithm computation. The prepatory phase, relation collection and the descent steps were done using Magma V2.21-10 on four servers. Out of the four servers, three have the same configuration with each of these three servers consisting of Intel(R) Xeon(R) E7-4890 @ 2.80 GHz (60 physical cores and 120 logical cores) and the fourth server consists of Intel Xeon E7-8890 @ 2.50 GHz (72 physical cores and 144 logical cores). These servers are shared resources and were simultaneously utilised by other users to run heavy simulation programs. We were never able to obtain exclusive access to the servers. The linear algebra phase was run on a cluster of 16 dual-socket Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz connected with Intel 100 Gbps Omni-Path.

In our computation, we chose p = 2111023 and n = 50. Note that log 2 (p) = 22 and log 2 (p n ) = 1051. So, the discrete logarithm computation is over a 1051-bit field having a 22-bit characteristic.

Preparatory phase: We chose n 1 = n 2 = 7. Experimentally we obtained g 1 (x) = x -7 and g 2 (x) = x 7 +1224488 such that x-g 2 (g 1 (x)) = f (x)/x 49 where f (x) = x 50 +886535x 49 +2111022. The polynomial f (x) is irreducible over F p and we represented F p n as F p [x]/(f (x)). Under this representation, x + 11 turned out to be a primitive element and was taken as the base of our discrete logarithm computation.

The factorization of (p n -1)/(p -1) is the following.

p n -1 p -1 = 2 5 • 3 4 • 11 • 31 • 83 • 101 • 131 • 157 • 251 • 6361 • 12241 • 131939 • 839532251 • 896407381 • 3943088101 • 164534375651 • 3062950366849991 • 36244934276573651 • 752902385776306150901 • p 1 • p 2 • p 3
where

p 1 = 2046921610339307301085688032782963272322001; p 2 = 55305981001475132391318117416798532278784706751; p 3 = 92398317305984139450141233089934164938195188756\ 28184706647588814170320419857377117657456062927786722348951.
Note log 2 (p 1 ) = 141, log 2 (p 1 ) = 156 and log 2 (p 1 ) = 353.

Based on the choices of g 1 (x) and g 2 (x), we have y = g 1 (x) = x -7 and x = g 2 (y) = y 7 + 1224488. The factor basis was set to be B = {(x + a i ), (y + b j ) : a i , b j ∈ F p }.

Relation collection:

The relation collection was done using sieving based on partial smoothness-cumdivisibility technique combined with pinpointing. The computation is highly parallelisable. It was distributed on four servers with 90 processes per server. The total time required for the relation collection phase was about 25 hours. Assuming that our jobs were allocated about 75% of the server time, a rough estimate of the number of core-years required for relation collection is 0.53 core-years.

A total of 2p + 100 = 4222146 relations were generated among the elements of the factor basis which includes the relation y = x -7 . Except for (y + 1849709), all elements of the factor basis were involved in at least one relation.

The fact that none of the 2p + 100 relations involved (y + 1849709) seemed peculiar to us. So, we decided to investigate this further. For this we considered applying the partial smoothness-cum-divisibility technique for relation collection from the y-side. The starting point of this technique is to write

C(y) = (y -α 1 )(y -α 2 )(y -α 3 )H 1 (y).
We set (y -α 1 ) = (y + 1849709). This is to ensure that any relation obtained from C(y) and the corresponding F (x) will necessarily involve (y + 1849709). There are two degrees of freedom given by α 1 and α 2 . This allows trying p 2 options. We were surprised to find that no relation could be obtained. It was possible to ensure that C(y) is smooth. However, in each such case, it turned out that the corresponding F (x) is not smooth. This suggests that it may indeed be the case that there is no relation among the factor basis elements which involves (y + 1849709). Conventionally, it is assumed that the relation collection phase will provide relations involving all elements of the factor basis. This particular example suggests that this may not be true.

Since we were unable to obtain any relation involving (y + 1849709), we decided to proceed without this element. The resulting matrix for the linear algebra stage consisted of 2p + 100 relations involving 2p -1 unknowns.

Linear algebra: The linear algebra step was performed for the three primes p 1 , p 2 and p 3 . The block Wiedemann algorithm implemented in the CADO-NFS software was used to complete the linear algebra step. For the largest prime p 3 , the Krylov step took about 1.6 core years, Lingen required negligible time and Mksol required about 0.25 core years. The time requirements for the two smaller sized primes were lesser. In terms of space, for p 1 and p 2 about 29GB each was required and for p 3 about 53GB was required. We used n = 4 distinct sequences for the block Wiedemann algorithm, so that we were able to simultaneously use 16 nodes as 4 groups of 4 nodes, each group working on one sequence.

After the linear algebra step, the discrete logarithms of all the elements in the factor basis other than (y + 1849709) were obtained modulo p 1 , p 2 and p 3 .

Individual logarithm -descent to factor basis elements: As the target for the individual discrete logarithm computation we chose the following element derived from the digits of the real number π. The function 'Normalize' mentioned below makes the input polynomial monic by multiplying with the inverse of the leading coefficient.

Π(x) = Normalize   (n-1) 0 π • p i+1 mod p x i   .
Explicitly Π(x) is given by the following degree 49 polynomial. Note that N (x) is 7-smooth while D(x) is smooth. This decomposition required about 30 minutes using 50 processes.

In the next step, the goal was to reduce to quadratic polynomials using successive d-(d -1) descent for polynomials of degree d > 2. This strategy mostly succeeded, except for three cubic polynomials. For these polynomials, we had to resort to alternating walk, i.e., move from degree 3 polynomials in x to degree 3 polynomials in y, as explained earlier. Using such a walk, we were able to descend to quadratic and linear polynomials. The total number of quadratic polynomials that were generated was 1212, of which 673 were quadratic polynomials in x and 539 were quadratic polynomials in y. The total time required for descending to quadratic polynomials was about 1481 minutes using 50 processes.

Finally we performed the 2-1 descent on all the quadratic polynomials. This was the most time consuming of all the descent steps. We used 50 processes on each of the four servers to perform either direct 2-1 descent or to apply alternating walk and/or branching. The entire 2-1 descent step was automated. The total time for all the 2-1 descents required about 10 days. Assuming that our jobs were allocated about 75% of the server time, a rough estimate of the number of core-years required for all the 2-1 descents is about 4.1 core-years.

Remark:

The descent to quadratic polynomials resulted in a total of 1212 quadratic polynomials. For comparison, we mention the number of quadratic polynomials obtained in previous computations. In [START_REF] Sarkar | Fine tuning the function field sieve algorithm for the medium prime case[END_REF], the numbers of quadratic polynomials were 92 and 59 for the 592-bit and the 728-bit cases respectively. In [START_REF] Joux | Faster index calculus for the medium prime case application to 1175-bit and 1425-bit finite fields[END_REF], the number of quadratic polynomials for the 1125-bit case was 278; the number of quadratic polynomials for the 1425-bit case was not reported.

We note that the descent is a random procedure. So, different runs of the descent procedure may lead to different number of quadratic polynomials. Since the 2-1 descent is the most time consuming of all the descent steps, it would be worthwhile to try and minimise the number of quadratic polynomials that arise from the upper levels of the descent. There is, however, no known method for such minimisation.

Individual logarithm -final discrete logarithm computation: After the completion of the 2-1 descent, the target polynomial Π(x) was expressed as a ratio N 1 (x)/D 1 (x), where N 1 (x) is a product of 147126 linear polynomials in x and 127149 linear polynomials in y, and D 1 (x) is a product of 147164 linear polynomials in x and 126001 linear polynomials in y.

Recall that the relation collection and linear algebra steps were not able to compute the discrete logarithm of (y + 1849709). Fortunately, this element does not appear among the linear factors of N 1 (x) and D 1 (x).

The discrete logarithms modulo p 1 , p 2 and p 3 of the linear factors of N 1 (x) and D 1 (x) had already been obtained after the completion of the linear algebra step. Consequently, after the descent step we were able to obtain the discrete logarithm of Π(x) modulo p 1 , p 2 and p 3 .

We used Pollard rho and Pohlig-Hellman to compute the discrete logarithm of Π(x) modulo the smaller factors of p n -1. The final discrete logarithm of Π(x) to base (x + 11) was computed using the Chinese Remainder Theorem. This value is given below. A short Magma program to verify the discrete logarithm is given in the Appendix A.

Unsolved DLP Challenge for the Medium Prime Case

In [START_REF] Lange | Digital signature: DSA with medium fields[END_REF], the following has been stated.

"For powers of very small primes and for large prime fields the function-field sieve and the number-field sieve are highly optimized; for intermediate fields algorithms with the same asymptotic behavior exist but the actual running times are slower."

To encourage research for intermediate size fields, the following challenge has been proposed in [START_REF] Lange | Digital signature: DSA with medium fields[END_REF]. Solve DLP in F p 17 = F p [x]/(x 17 -2) where p = 2 32 -27897.

This problem can be tackled using the FFS for the medium prime case. For this, we set n 1 = n 2 = 4 so that n = n 1 n 2 + 1 = 17. We estimate the costs of the relation collection, linear algebra and the descent steps.

Cost of linear algebra: For this problem, n | (p -1) which will allow the factor basis to be reduced by a factor of 17. So, the size of the factor basis will be about 2 29 and hence, linear algebra step will require about 2 58 operations in F p .

Cost of relation collection:

Using n 1 = n 2 = 4, from [START_REF] Diffie | New directions in cryptography[END_REF], the number of trials required to obtain a single relation is about 2 6.9 . So, the total number of trials required to obtain about 2 29 relations is about 2 35.9 . Further, the feasibility condition given by ( 4) holds.

Cost of 2-1 descent: Using n 1 = n 2 = 4, from [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities -application to discrete logarithms in F 2 1971 and F 2 3164[END_REF], the number of trials required to obtain a single 2-1 descent is about 2 9.5 . We would expect a few thousand quadratic polynomials would be required to be descended. The feasibility condition given by ( 8) holds.

So, based on the above analysis, we see that while the relation collection and the descent steps are well within reach, the major cost of performing the computation required for solving the challenge lies in the linear algebra computation.

Remark:

The above estimates are rough. For one thing, we have estimated that the time required for the linear algebra step on a factor basis of size N is about N 2 . Secondly, the time for individual operations for the linear algebra step and the times for individual trials of the relation collection step and the 2-1 descent step have been assumed to be equal. To obtain more precise estimates, these issues would be required to be taken into consideration. Nevertheless, even with the rough estimates, the main conclusion that for this particular DLP computation it is the linear algebra step which will be the main challenge, remains valid.

Larger extension degree: The extension degree suggested in the above problem is 17 which is quite low. Let us consider a higher value of n. Suppose n 1 = n 2 = 8 and n = n 1 n 2 + 1 = 65. As in the above problem, assume that p is a 32-bit prime. Also, let us not make the assumption that n | (p -1) holds. So, the factor basis will have about 2p elements. From ( 6), the number of trials required to obtain a single relation is about 2 18 and to obtain about 2 33 relations, about 2 51 trials would be required. From [START_REF] Göloglu | On the function field sieve and the impact of higher splitting probabilities -application to discrete logarithms in F 2 1971 and F 2 3164[END_REF], the number of trials required to obtain a single 2-1 descent is about 2 31 . The feasibility condition (4) and (8) both hold. Since the size of the factor basis is about 2 33 , the linear algebra will require about 2 66 F p -operations. So, it is the linear algebra step which will be the major challenge in any such discrete logarithm computation.

Conclusion

In this paper, we have reported the computation of discrete logarithm in a 1051-bit field having a 22-bit characteristic. For the general medium prime case (i.e., fields for which the condition n | (p -1) does not hold), the computation reported here is the current discrete logarithm record computation. The techniques used in this work can be extended to solve relation collection and descent phases for 32-bit primes and moderate extension degrees. It is the linear algebra phase that will require the maximum time for performing any record discrete logarithm computation for such fields.

RENATER and several universities as well as other organizations. Some of the computational resources used on the Grid'5000/SILECS testbed were also funded by the CPER cyberentreprises project.

Table 1 :

 1 A comparison of the difficulty of computing discrete logarithms for the medium prime case using the function field sieve algorithm.

	Ref	log 2 p	n	log 2 p n	log 2 #B	Λ
	JL [16]	17	25	401	18	3.79
	SS [19]	16	37	592	17	0.11
	SS [19]	19	40	728	20	0.08
	This work	22	50	1051	23	0.07

Table 2 :

 2 A comparison of the difficulty of computing discrete logarithms for the medium prime case using the function field sieve algorithm for Kummer extensions, i.e., for fields F p n satisfying n | (p -1).

	Ref	log 2 p	n	log 2 p n	log 2 #B	Λ
	JL [16]	19	30	556	18	4.29
	Joux

Acknowledgement

The linear algebra part of the reported calculation was carried out on the French Grid'5000/SILECS experimental testbed, supported by a scientific interest group hosted by Inria and including CNRS,

For the initial descent a simple randomisation strategy was utilised which led to

where N (x) and D(x) are as follows. printf "base := %o\n",base; printf "target := %o\n",target; printf "log := %o\n", log; printf "base^log eq target = %o\n",base^log eq target;