Jérémie Detrey
email: jeremie.detrey@loria.fr

FFS Factory: Adapting Coppersmith's "Factorization Factory" to the Function Field Sieve

Keywords: Discrete logarithm, Function field sieve, Cryptanalysis

In 1993, Coppersmith introduced the "factorization factory" approach as a means to speed up the Number Field Sieve algorithm (NFS) when factoring batches of integers of similar size: at the expense of a large precomputation whose cost is amortized when considering sufficiently many integers to factor, the complexity of each individual factorization can then be lowered. We suggest here to extend this idea to the computation of discrete logarithms in finite fields of small characteristic using the Function Field Sieve (FFS), thus referring to this approach as the "FFS factory". In this paper, the benefits of the proposed technique are established thanks to both a theoretical complexity analysis along with a practical experiment in which we solved the discrete logarithm problem in fifty different binary fields of sizes ranging from 601 to 699 bits.

Introduction

Initially introduced in 1994 by Adleman [START_REF] Adleman | The function field sieve[END_REF], the Function Field Sieve (FFS) has been for almost twenty years the most efficient algorithm known for computing discrete logarithms in the multiplicative subgroup of finite fields F q k , with a subexponential asymptotic complexity of L q k (1/3, 3 32/9) 1+o (1) , where the notation L q k designates the usual function L N (α, c) = exp c(log N ) α (log log N ) 1-α , with 0 ≤ α ≤ 1 and c > 0.

However, the year 2013 was marked by several successive major theoretical improvements on this algorithm by Göloğlu et al. [START_REF] Göloğlu | On the function field sieve and the impact of higher splitting probabilities[END_REF], Joux [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF], and finally Barbulescu et al. [START_REF] Barbulescu | A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF], which eventually brought the asymptotic complexity of solving the discrete logarithm problem over fields of small characteristic down to quasi-polynomial time. These breakthroughs were accompanied by many computations of discrete logarithms in record-sized binary and ternary fields [START_REF] Joux | Discrete logarithms in GF(2 1778 ). E-mail to the NMBRTHRY mailing list[END_REF][START_REF] Göloğlu | On the function field sieve and the impact of higher splitting probabilities[END_REF][START_REF] Joux | Discrete logarithms in GF(2 4080 ). E-mail to the NMBRTHRY mailing list[END_REF][START_REF] Göloğlu | Solving a 6120-bit DLP on a desktop computer[END_REF]22,[START_REF] Granger | Email to the NMBRTHRY mailing list[END_REF][START_REF] Adj | Computing discrete logarithms in F 3 6•137 and F 3 6•163 using Magma[END_REF]. Nevertheless, finding the exact crossing point between FFS and these recent algorithms, especially when it comes to fields of prime extension degrees, is still an active research topic [START_REF] Barbulescu | Discrete logarithm in GF(2 809 ) with FFS[END_REF].

Furthermore, software implementations of FFS (or at least of the descent step) are now publicly available, either as standalone software packages such as in the cado-nfs distribution [START_REF] Bai | cado-nfs, an implementation of the Number Field Sieve algorithm[END_REF], or as part of computer algebra systems such as Magma [START_REF] Bosma | The Magma algebra system. I. The user language[END_REF]. Therefore, providing such software with the precomputed discrete logarithms of factor bases for various finite fields should definitely make their job easier when computing individual logarithms in these fields. For instance, the release notes of Magma V2.20 state that "The database of logarithms is continually being extended and now includes data for larger fields. In particular, the fields GF (2 d ) are now covered for all prime degree d ≤ 509 and most degrees up to 500" [START_REF] Bosma | Summary of new features in Magma V2.20[END_REF].

Bearing in mind this motivation of computing discrete logarithms in several finite fields, we propose in this paper the so-called "FFS factory", whose key idea is to share as much of the computation as possible amongst the considered finite fields in order to decrease the overall computation cost when compared to running as many independent instances of FFS. This approach is directly inspired from Coppersmith's "factorization factory" [START_REF] Coppersmith | Modifications to the Number Field Sieve[END_REF], which can be used to accelerate the factorization of many integers of the same size using the Number Field Sieve (NFS), thus bringing the original complexity of NFS from L N (1/3, 1.923) 1+o (1) down to L N (1/3, 1.639) 1+o (1) for each integer N to be factored. A similar modification of NFS, known as the "discrete logarithm factory", was later presented by Barbulescu in order to batch discrete logarithm computations over finite fields of large characteristic [6, Section 7.2].

However, since both of the above cases are based on NFS, they can only share the computations on the so-called rational side of the algorithm. What we propose here is to leverage the fact that the polynomial selection is far less constrained in the FFS setting in order to share the computations on the algebraic side instead. It is to be noted that this idea was first suggested by Kleinjung in the context of factoring using the Special Number Field Sieve (SNFS) [24], which is in many ways quite similar to FFS.

Roadmap. This paper is organized as follows. After a presentation on the Function Field Sieve in Section 2, with a special emphasis on its complexity analysis, Section 3 details the algorithmic and complexity aspects of the proposed FFS factory approach before discussing its applicability. A practical experiment, involving the computation of discrete logarithms in 50 binary finite fields of size between 601 and 699 bits, is then presented in Section 4, before some concluding remarks in Section 5.

Remainder on the Function Field Sieve

In the following, we let q be a prime power and k a positive integer, and assume that we want to compute discrete logarithms in the multiplicative subgroup of the finite field F q k . In other words, for any two elements g and h ∈ F × q k , with g primitive, we want to find the integer λ ∈ Z/(q k -1)Z such that h = g λ .

Note that, in order to fall into the domain of applicability of FFS, we further require that q = L q k (α, c) with 0 ≤ α < 1/3 and c > 0. In practice, q will usually be a small prime (such as 2) or a small power thereof.

As the Function Field Sieve belongs to the family of index calculus algorithms for computing discrete logarithms, it follows the same basic three steps:

-The relation collection step, whose goal is to find many multiplicative equalities, or relations, involving only elements from a predefined subset of F q k , called the factor base. Taking the logarithm, each such relation becomes a linear equation modulo q k -1, whose unknowns are the discrete logarithms of the factor base elements. -The linear algebra step, which solves the linear system once enough such relations have been found, and therefore recovers the value of the discrete logarithms of the factor base elements. -The individual logarithm step, which computes the discrete logarithm of an arbitrary element h ∈ F × q k by finding a multiplicative relation involving only h and factor base elements.

Further details on how these three tasks are achieved in FFS are given in the following paragraphs, before a careful complexity analysis in Section 2.4. However, we do not claim here to give an exhaustive nor comprehensive description of FFS, but rather to focus on a few key points which will prove useful in the rest of this paper. For more information on this topic, we refer the interested reader to the original theoretical foundations of FFS by Adleman and Adleman & Huang [START_REF] Adleman | The function field sieve[END_REF][START_REF] Adleman | Function field sieve method for discrete logarithms over finite fields[END_REF] along with the later improvements by Matsumoto and Joux & Lercier [START_REF] Matsumoto | Using C ab curves in the function field sieve[END_REF][START_REF] Joux | The function field sieve is quite special[END_REF].

Relation collection

Let d > 1 be an integer, and let f (x, t) ∈ F q [t][x] be a monic, bivariate polynomial of degree d in x. Note that, for our purposes, the degree in t of f can be made as small as possible 1 . Let now g(x, t) ∈ F q [t][x] be a linear polynomial such that its resultant in x with f has an irreducible factor ϕ(t) of degree k. Since, by construction, f has coefficients of small degree in t, this implies that deg t g ≈ k/d.

In the following, we denote by

F (X, Y, t) = Y d • f (X/Y, t) and G(X, Y, t) = Y • g(X/Y, t)
the homogenizations in x of the polynomials f and g, respectively.

Given the above choice of polynomials, the target finite field F q k is therefore isomorphic to the extension field F q [t]/(ϕ(t)), and the following diagram is commutative:

F q [t][x] F q [t][x]/(f (x, t)) F q [t][x]/(g(x, t)) F q [t]/(ϕ(t)) ∼ = F q k
The core idea behind the relation collection step in FFS, also known as the sieving step, is to consider elements of F q [t][x] and to map them down to F q k through both sides of the diagram, factoring the corresponding principal ideals in the ring of integers of the function fields F q (t)[x]/(f (x, t)) and F q (t)[x]/(g(x, t)) along the way.

In this sieving step, we then consider all the pairs of polynomials (r(t), s(t)) ∈ (F q [t]) 2 where r is monic and both are of degree at most e, where e is a parameter called the sieving bound. Given a second parameter b, referred to as the smoothness bound, we then push each polynomial r(t) -s(t)x ∈ F q [t][x] through the above diagram, and try to factor the corresponding principal ideals in the ring of integers of the function fields F q (t)[x]/(f (x, t)) and F q (t)[x]/(g(x, t)) as products of prime ideals whose norms are of degree at most b. If such a factorization succeeds on both sides, then the pair (r, s) is called doubly-b-smooth. Mapping both factorizations to F q k thanks to the two lower maps of the diagram then yields a relation, that is a multiplicative equality between elements of the factor base, which is defined as the set of those elements of F q k that correspond to prime ideals whose norms have degree at most b in the function fields above.

On the left-hand side of the diagram (also known as the algebraic side), the principal ideal corresponding to an element r(t) -s(t)x factors as a product of prime ideals whose norms have degree at most b in the ring of integers of the function field F q (t)[x]/(f (x, t)) if and only if the norm of this principal ideal itself factors as a product of irreducible polynomials of degree at most b. The same obviously holds for the right-hand side as well (also known as the rational side). Therefore, checking if a pair (r, s) from the sieving domain if doubly-b-smooth is tantamount to checking if the norms of the corresponding principal ideals, namely the polynomials F (r, s, t) and G(r, s, t) ∈ F q [t], both factor as products of irreducible polynomials of degree at most b.

Therefore, collecting relations in FFS is just a matter of enumerating all pairs (r, s) in the sieving domain, computing their norms F (r, s, t) and G(r, s, t), and marking each of them as a valid relation if both norms are indeed b-smooth. Of course, the parameters d, e and b should be carefully chosen so that this step finds enough relations in order to solve the corresponding linear system.

Linear algebra

All the relations collected in the previous step form a large linear system modulo q k -1, the order of the multiplicative subgroup of F q k . However, this linear system is very sparse, thus allowing for efficient methods such as Lanczos' or Wiedemann's algorithms [START_REF] Lamacchia | Solving large sparse linear systems over finite fields[END_REF]: given a sparse matrix of N rows and columns, with an average of ω non-zero coefficients per row, such algorithms can indeed solve the corresponding linear system in time O(ωN 2 ), which is more efficient than classical Gaussian elimination algorithms running in O(N 3 ).

Individual logarithms

Let h be an arbitrary element of

F × q k . Since F q k ∼ = F q [t]/(ϕ(t)
), h can be seen as a polynomial in t of degree less than k. The discrete logarithm of h then can be computed in two main steps:

-The smoothing step, in which one tries to find an element of the factor base, whose norm we denote as θ(t), along with an exponent m such that the polynomial θ(t

) m h(t) mod ϕ(t) is b 0 -smooth, with b 0 = √ kb.
-The special-q descent: given a prime ideal q (on either the algebraic or the rational side of the diagram) whose norm is of degree d q , with b < d q ≤ b 0 , we denote by Λ q the set of (r, s) pairs in (F q [t]) 2 such that the principal ideal corresponding to r(t)-s(t)x (on the same side of the diagram) is divisible by q. It can be remarked that Λ q forms an F q [t]-lattice of dimension 2. A basis of Λ q is then obtained thanks to Gaussian lattice reduction, which yields two vectors (r 1 (t), s 1 (t)) and (r 2 (t), s 2 (t)), the degree of whose coefficients r 1 , s 1 , r 2 and s 2 is approximately d q /2.

Similarly to the sieving phase, we fix a parameter e ′ and enumerate all pairs of polynomials (i(t), j(t)) ∈ (F q [t]) 2 where i is monic and both are of degree at most e ′ . For each such pair, we then consider the element (ir 1 + jr 2 , is 1 + js 2 ) ∈ Λ q and try to factor the corresponding norms F (ir 1 + jr 2 , is 1 + js 2 , t) and G(ir 1 + jr 2 , is 1 + js 2 , t) as products of irreducible polynomials of degree at most b ′ , with the smoothness bound b ′ = λd q and the descent parameter λ < 1. One such doubly-b ′ -smooth pair will then give us a linear relation between the discrete logarithm of q and that of several prime ideals whose norms have degree at most b ′ . We finally iterate the process recursively until we end up considering only prime ideals whose norms have degree at most b, that is, elements of the factor base, whose discrete logarithms were already computed in the linear algebra step.

Complexity analysis

In order to lay the groundwork for the study of the proposed FFS factory algorithm in Section 3.2, we recall here the complexity analysis of the Function Field Sieve presented in the previous subsections, following the notations of Barbulescu [6, Section 7.5], which are also that of Coppersmith [START_REF] Coppersmith | Modifications to the Number Field Sieve[END_REF] in the case of the Number Field Sieve.

To that intent, let us first introduce the positive constants δ, ε, and β so as to define the degree d of f (x, t), the sieving bound e, and the smoothness bound b as follows:

d = δ k log q log k 1/3 , e = ε k 1/3 (log k) 2/3
(log q) 2/3 , and b = β

k 1/3 (log k) 2/3 (log q) 2/3 .
Sieving and linear algebra. Given a pair (r, s) of polynomials in the sieving range (i.e., both of degree at most e and r monic), we then denote by P f and P g the probabilities that the corresponding norms F (r, s, t) and G(r, s, t) are b-smooth, respectively. The degrees of these norms can be bounded by

deg F (r, s, t) ≤ deg t f + de ≈ de = δε k 2/3 (log k) 1/3 (log q) 1/3
(since f has small coefficients) and

deg G(r, s, t) ≤ deg t g + e ≈ k/d = 1 δ k 2/3 (log k) 1/3 (log q) 1/3 (since deg t g ≈ k/d dominates e).
Assuming that these norms behave like random polynomials of the same degree, following [START_REF] Panario | An analytic approach to smooth polynomials over finite fields[END_REF], we then estimate the probabilities that they are b-smooth as

P f = u -u(1+o(1)) where u = deg F (r,s,t) b ≈ de/b = δε β k log q log k 1/3
and

P g = v -v(1+o(1)) where v = deg G(r,s,t) b ≈ k/db = 1 δβ k log q log k 1/3
, which we rewrite as (1) and (1) . Since the sieving domain comprises q 2e+1 = L q k (1/3, 2ε) 1+o (1) such pairs (r, s), the expected total number of relations collected by the sieving step is therefore q 2e+1 P f P g . However, in order to be able to solve the corresponding linear system, we require at least as many relations as there are elements in the factor base, whose cardinality is less than 2q b = L q k (1/3, β) 1+o (1) . Consequently, we impose that

P f = L q k (1/3, δε 3β ) -1+o
P g = L q k (1/3, 1 3δβ ) -1+o
q 2e+1 P f P g ≥ (2q b ) 1+o(1) or, equivalently, that 2ε - δε 3β - 1 3δβ = β.
Solving in ε, and additionally requiring that δ < 6β, we finally obtain the following constraint on the sieving bound:

ε ≥ 3δβ 2 + 1 δ(6β -δ) . ( 1
)
Furthermore, since the degrees of the norms F (r, s, t) and G(r, s, t) are polynomial in log(q k ), checking if they are b-smooth can be done in polynomial time, and the number of non-zero coefficients in the corresponding row of the matrix in the linear algebra step will also be polynomial in log(q k ). Therefore, as FFS falls into the L q k (1/3, •) sub-exponential complexity range, we can ignore these polynomial terms and obtain the following time complexities: (1) . These two steps being the most expensive ones in FFS, balancing their computational cost is key to minimize the overall complexity of the algorithm. We therefore impose the further constraint that e = b or, equivalently, that ε = β. Under that condition, (1) can be rewritten as a quadratic inequation in δ, namely εδ 2 -3ε 2 δ + 1 ≤ 0, which admits a positive solution δ if and only if ε ≥ 3 4/9.

T sieving = (q 2e+1 ) 1+o(1) = L q k (1/3, 2ε) 1+o(1) and T lin.algebra = (2q b ) 2+o(1) = L q k (1/3, 2β) 1+o
Consequently, setting the constants ε = β = 3 4/9, we obtain δ = 3 3/2 and, finally, the overall complexity of FFS as (1) .

T FFS = L q k (1/3, 2ε) 1+o(1) = L q k (1/3, 3 32/9) 1+o
Individual logarithms. We follow here the reasoning of [6, Section 7.3] and adapt it to the FFS setting. It can be shown that the most expensive step in the computation of individual logarithms is the special-q descent when the degree d q of the norm of the prime ideal q is closest to b. In order to evaluate the complexity of this step, we consider here an ideal q whose norm has degree d q of the form

d q = γ k 1/3 (log k) 2/3 (log q) 2/3 , with γ > β.
Recall that, in that case, we consider the norms corresponding to pairs of polynomials of the form (ir 1 + jr 2 , is 1 + js 2 ) ∈ Λ q ⊂ (F q [t]) 2 , with the polynomials i and j of degree at most e ′ , i monic, and where the coefficients r 1 , r 2 , s 1 , and s 2 of the basis vectors all have degree around d q /2. The degrees of these norms can therefore be bounded by

deg F (ir 1 + jr 2 , is 1 + js 2 , t) deg t f + d(e ′ + d q /2) ≈ d(e ′ + d q /2) and deg G(ir 1 + jr 2 , is 1 + js 2 , t) deg t g + (e ′ + d q /2) ≈ k/d.
Denoting by ε ′ the positive parameter such that e ′ = ε ′ k 1/3 (log k) 2/3 (log q) 2/3 , the probabilities that these two norms are b ′ -smooth, for b ′ = λd q , are then given by P (1) and P ′ g = L q k (1/3, 1 3δλγ ) -1+o (1) , respectively. Furthermore, since there is no point in taking a smoothness bound b ′ for the descent lower than the sieving smoothness bound b, we can assume that b ′ = λd q ≥ b, whence λγ ≥ β.

′ f = L q k (1/3, δε ′ 3λγ + δ 6λ ) -1+o
Consequently, the overall probability to find one doubly-b ′ -smooth relation in this descent step when considering all (i, j) pairs can be bounded by

q 2e ′ +1 P ′ f P ′ g ≥ L q k 1/3, 2ε ′ - δε ′ 3β - δ 6λ - 1 3δβ 1+o(1)
. Since we require this probability to be non-negligible so that at least one such relation can actually be found, we end up with the following condition on ε ′ :

ε ′ ≥ δ 2 β/(2λ) + 1 δ(6β -δ) . ( 2
)
Plugging in the values for β and δ found previously and, following [START_REF] Barbulescu | Algorithms of discrete logarithm in finite fields[END_REF], taking for λ a constant close but not equal to 1, such as 0.999, allows us to choose ε ′ = 3 1/18. The cost for this special-q descent step is then (1) .

(q 2e ′ +1 ) 1+o(1) = L q k (1/3, 2ε ′ ) 1+o(1) = L q k (1/3, 3 4/9) 1+o
Finally, considering the tree formed by the recursive calls in the descent process, one can check that the arity of each node is less than 2k (since special-q descent will produce less than 2k new prime ideals), while the total depth of the tree is given by w = log λ (b/b 0 ) = O(log k). Therefore, the total number of nodes in the tree is in O(exp((log k) 2 ), which is polynomial in log(q k ). Consequently, ignoring the polynomial terms, the overall time complexity for computing an individual logarithm is the same as the complexity of a single special-q descent step, namely T indiv.log. = L q k (1/3, 3 4/9) 1+o (1) .

The FFS factory

The main contribution of this paper is based on the observation that, in the Function Field Sieve, a same polynomial f (x, t) ∈ F q [t][x] can be used to compute discrete logarithms in several finite fields of approximately the same size. Therefore, in a setting where one wants to compute discrete logarithms in many different finite fields of close enough sizes, it is possible to use a single polynomial f for all these fields and share the computations on the algebraic side of the FFS algorithm.

Batching FFS computations

Let us now assume that we want to compute discrete logarithms in several finite fields F q k ′ , with k ′ ≤ k and q a prime power such that q = L q k (α, c) with 0 ≤ α < 1/3 and c > 0.

The idea here is to split the relation collection step into two parts:

-An precomputation step, which is performed only once, and which exclusively focuses on the algebraic (i.e., left-hand) side of the FFS commutative diagram. In this step, we select a good polynomial f (x, t) ∈ F q [t][x] of degree d, and find all pairs (r, s) in the sieving domain which are b-smooth on the algebraic side. These pairs are then stored into a large file, where they can be reused later. -An individual sieving step, which is performed for each target field F q k ′ .

Here, a linear polynomial g(x, t) is first chosen so that its resultant in x with f has an irreducible factor of degree k ′ . The previously computed file is then read, and each pair (r, s) in this file is checked for b-smoothness on the rational (i.e. right-hand) side.

Once the individual sieving step is completed for a given finite field F q k ′ , the remaining linear algebra and individual logarithm steps can be performed for this field just as in the original FFS algorithm.

Complexity analysis

Since the first part of the relation collection step is now shared between several discrete logarithm computations, the optimal values for the parameters b, d, and e will differ from the ones in the original FFS. In order to find these new values, we build upon the complexity analysis of FFS detailed in Section 2.4.

Relation collection and linear algebra.

First of all, one has to remark that, with respect to the parameters b, d, and e, the degrees of the polynomials f and g, the sieving domain and the factor base are the same as in the original FFS. In other words, the sieving domain still comprises q 2e+1 = L q k (1/3, 2ε) 1+o (1) pairs of polynomials (r, s), the cardinality of the factor base is still less that 2q b = L q k (1/3, β) 1+o (1) , and the degrees of the norms F (r, s, t) and G(r, s, t) are still bounded by de and k/d, respectively.

Consequently, the condition q 2e+1 P f P g = (2q b ) 1+o (1) which ensures that enough relations are collected in order to solve the corresponding linear system imposes the exact same constraint on ε:

ε ≥ 3δβ 2 + 1 δ(6β -δ) , with δ < 6β. (1)
We now consider the costs of the various steps involved in the FFS factory. Note however that the actual values of the constants β, δ, and ε will be determined later.

First of all, as the precomputation step requires to enumerate all pairs (r, s) of the sieving domain, its complexity is T precomp. = (q 2e+1 ) 1+o(1) = L q k (1/3, 2ε) 1+o (1) . Furthermore, since each pair (r, s) has probability P f to be b-smooth on the algebraic side, the number of such b-smooth pairs written to the file in this precomputation step is then

N precomp. = q 2e+1 P f = L q k 1/3, 2ε - δε 3β 1+o (1)
.

Then, for each target field, we need to perform the corresponding individual sieving step, which entails going through all the precomputed pair (r, s) and checking whether each of them is b-smooth on the rational side. Since this check can be done in polynomial time, the actual complexity of this step is then T indiv.sieving = N precomp. . The linear algebra step, which also has to be performed for each target field, still has complexity quadratic in the size of the factor base, as in the original FFS:

T lin.algebra = (2q b ) 2+o(1) = L q k (1/3, 2β) 1+o (1) .

Finally, we denote by T indiv.FFS = T indiv.sieving + T lin.algebra the overall time complexity of the specific computations required for each target field.

Individual logarithms. In a similar way as for the sieving constraint on ε, one can easily see that computing a special-q descent step in a target field F q k ′ entails exactly the same constraint on the parameter ε ′ of the sieving region as in the case of the original FFS:

ε ′ ≥ δ 2 β/(2λ) + 1 δ(6β -δ) . ( 2
)
Furthermore, the cost of an individual logarithm in this field will also be 1) .

T indiv.log. = L q k (1/3, 2ε ′ ) 1+o (
Balancing the complexities. Assuming that the precomputation step is done once and for all, we only need to balance the cost of the individual sieving and linear algebra steps for each target field. Setting q 2e+1 P f = (2q b ) 2+o (1) and using the constraint (1) on ε, we obtain the condition δ ≥ 1/(3β 2 ), which in turn imposes that β > 3 1/18, since (1) also requires that δ < 6β.

In fact, it can be shown that, for any λ < 1, the quantity

ε ′ -β ≥ δ 2 β/(2λ) + 1 δ(6β -δ) -β ≥ 3βδ 2 -12β 2 δ + 2 2δ(6β -δ)
is always positive when 3 1/18 < β < 3 1/6. Consequently, if one takes β in that interval, then the cost of computing an individual logarithm in a target field F q k ′ will dominate that of the linear algebra step in the same field. The intuitive explanation is that, in such a case, the factor base is too small and the descent is thus much harder. It is therefore useless to consider values of β below 3 1/6. Similarly, considering values of β larger that 3 4/9 is also useless, as such values will yield complexities larger than that of the original FFS algorithm, thus defeating the purpose of the FFS factory approach.

In the following, we denote by ε 0 the lower bound on ε given by (1):

ε 0 (β, δ) = 3δβ 2 + 1 δ(6β -δ) .
We first study the behavior of ε 0 with respect to δ, in the range 1/(3β 2 ) ≤ δ < 6β, for a fixed value of 3 1/6 < β ≤ 3 4/9. Taking the partial derivative of ε 0 with respect to δ then gives

∂ε 0 ∂δ (β, δ) = 3β 2 δ 2 + 2δ -6β δ 2 (6β -δ) 2 ,
which is negative when 1/(3β 2 ) ≤ δ < δ 0 (β) and positive when δ 0 (β) < δ < 6β, with δ 0 (β) = (ξ(β) -1)/(3β 2 ) and ξ(β) = 18β 3 + 1. Hence, in order to minimize ε 0 , we define ε0 (β) = ε 0 (β, δ 0 (β)). This function and its derivative with respect to β are then given by

ε0 (β) = ε 0 (β, δ 0 (β)) = 3β 2 ξ(β) -1 2 and dε 0 dβ (β) = 9β 3 ξ(β) 2 -4ξ(β) + 3 ξ(β)(ξ(β) -1) 3 ,
respectively. The latter shows that ε0 is a strictly decreasing function of β on the whole interval 3 1/6 < β < 3 4/9, its derivative vanishing at β = 3 4/9.

Similarly, fixing δ = δ 0 (β) in constraint (2) for individual logarithms gives the following lower bound on the parameter ε ′ :

ε ′ ≥ β 2ξ(β) 1 λ + ξ(β) + 1 ξ(β) -1 , which becomes ε ′ ≥ β/(ξ(β) -1)
when λ is chosen to be almost equal to 1.

One can remark that, when taking β = 3 4/9, we end up with the exact same complexity as the original FFS algorithm: (1) and T indiv.log. = L q k (1/3, 3 4/9) 1+o(1) .

T precomp. = T indiv.FFS = L q k (1/3, 3 32/9) 1+o

Discussion

From the previous analysis, taking the parameters ε = ε0 (β) and ε ′ = β/(ξ(β) -1), one can use β in order to adjust the tradeoff between the cost of the precomputation step and that of the individual sieving/linear algebra steps, depending on how many target fields F q k ′ are considered. Indeed, if one wants to compute discrete logarithms in many different finite fields, taking a lower value for β will increase the precomputation time, while decreasing the individual cost for each target field. This can be seen in Figure 1, in which the costs T precomp. , T indiv.FFS , and T indiv.log. are given as functions of β.

T indiv.FFS = L q k (1/3, 2β) 1+o(1) T precomp. = L q k (1/3, 2ǫ) 1+o(1) T indiv.log. = L q k (1/3, 2ǫ ′ ) 1+o (1)
(original FFS) Fig. 1. Costs of the various steps in the FFS factory, as functions of β, and expressed as the parameter c which appears in their complexity when written as

L q k (1/3, c).
Of course, mitigating the extra cost of the precomputation step requires that enough target fields are considered. In fact, the number N of distinct finite fields in which to compute discrete logarithms should be of the form N = L q k (1/3, ν) 1+o (1) , with ν > 0, in order to be able to amortize the precomputation cost. For instance, while β = 3 4/9 corresponds to the original FFS algorithm and can therefore be used even for a single target field, on the other hand, setting β = 3 1/6 requires that N ≥ T FFS /T precomp. or, in other words, that ν ≥ 3 9/2 -3 32/9 ≈ 0.125. In that case, we have the following complexity estimates: (1) and T indiv.FFS = T indiv.log = L q k (1/3, 3 4/3) 1+o (1) . However, since the finite fields of a given size q k ′ are all isomorphic, and that this isomorphism is computable in polynomial time, there is absolutely no point in applying the FFS factory to more than one field of each size. As there are only a polynomial number of distinct finite fields F q k ′ with k ′ ≤ k, there is no way for N to be in the L q k (1/3, •) complexity range as k grows. On first sight, this renders the whole FFS factory approach useless, at least asymptotically.

T precomp. = L q k (1/3, 3 9/2) 1+o
However, this criticism might be mitigated as, since 2013, it is known that FFS, asymptotically speaking, is no longer the most efficient algorithm known for computing discrete logarithms in finite fields of small characteristic [START_REF] Joux | A new index calculus algorithm with complexity L(1/4 + o(1)) in very small characteristic[END_REF][START_REF] Göloğlu | On the function field sieve and the impact of higher splitting probabilities[END_REF][START_REF] Barbulescu | A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic[END_REF]. Even though the exact crossing point between FFS and these asymptotically faster algorithms is not known yet, recent experiments show that computing discrete logarithms using FFS still makes sense for finite fields F q k of size log 2 (q k ) up to around 1000 bits [START_REF] Barbulescu | Discrete logarithm in GF(2 809 ) with FFS[END_REF]. It turns out that, for fields of that size, the quantity L q k (1/3, ν) amounts to at most a few dozens when ν ≤ 3 9/2 -3 32/9. Therefore, in this case, the number N of finite fields to consider for the FFS factory to be better than N independent instances of the original FFS is roughly of the same order of magnitude and is thus totally manageable in practice, as shown by the experiment presented in Section 4.

Practical experiment

In order to assess the applicability and the impact of the proposed FFS factory approach, we have implemented this algorithm and used it to compute discrete logarithms in the 50 binary finite fields F 2 k ′ for all odd values of k ′ between 601 and 699 (inclusive), which fall slightly below the current size records for FFS [START_REF] Hayashi | Breaking pairing-based cryptosystems using ηT pairing over GF (3 97 )[END_REF][START_REF] Barbulescu | Discrete logarithm in GF(2 809 ) with FFS[END_REF].

Software implementation. Our implementation of the FFS factory is based on the C implementation of FFS which is freely available as part of the cado-nfs software suite [START_REF] Bai | cado-nfs, an implementation of the Number Field Sieve algorithm[END_REF]. Since some of the steps in the FFS factory are identical to those of the original FFS, we were able to directly reuse various part of cado-nfs for our computation, such as the polynomial selection [START_REF] Barbulescu | Selecting polynomials for the Function Field Sieve[END_REF], the filtering utilities (which prepare the matrix before the linear algebra) [START_REF] Bouvier | The filtering step of discrete logarithm and integer factorization algorithms[END_REF], or the GPU-based linear algebra implementation [START_REF] Jeljeli | Accelerating iterative SpMV for Discrete Logarithm Problem using GPUs[END_REF].

However, the relation collection step had to be modified so as to match the FFS factory algorithm. In the cado-nfs implementation of FFS, this step is directly based on the implementation described by Detrey et al. in [START_REF] Detrey | Relation collection for the Function Field Sieve[END_REF] which, among other techniques, uses special-q sieving, which ensure that large prime ideals q (on either the algebraic or the rational side) appear in the relations, thus increasing the smoothness probabilities; and lattice sieving, which, in a somewhat similar way to the sieve of Eratosthenes, allows one to quickly find all pairs (r, s) which are divisible by small prime ideals (on both sides), and to actually check for smoothness only those pairs which are divisible by sufficiently many of these small prime ideals, since they will then have higher chances of being b-smooth.

In order for this program to follow the FFS factory approach, we have modified it to support several polynomials (and therefore several target fields) on the rational side at the same time, thus sharing the (pre)computations for the algebraic side amongst all target fields. We have also disabled both the special-q sieving and the lattice sieving on the rational side, but kept these techniques for the algebraic side so as to maintain the running time of the precomputation step as low as possible.

All in all, adding support for the FFS factory mostly entailed minute changes in the cado-nfs software. It is therefore planned that these changes eventually make their way into the official code base of cado-nfs, and that the FFS factory becomes available in future releases.

Experimental setup and results. In order to compute discrete logarithms in all finite fields F 2 k ′ , with k ′ odd and between 601 and 699, using the proposed FFS factory, we used the same degree-6 polynomial f (x, t) for the algebraic side that was used for the discrete logarithm computation in F × 2 809 [START_REF] Barbulescu | Discrete logarithm in GF(2 809 ) with FFS[END_REF]:

f (x, t) = x 6 + 0x7x 5 + 0x6bx 3 + 0x1abx 2 + 0x326x + 0x19b3.
Note that we also considered using a degree-5 polynomial, but none were found in the polynomial selection step that were as good as the one above for the considered finite fields. Sieving was performed using the implementation described above on Intel Xeon E5-2650 CPUs running at 2.0 GHz. The smoothness bound was fixed to b = 26, and we lattice-sieved on the algebraic side all prime ideals whose norm had degree at most 20. We sieved for special-q's of norm starting at degree 21 and increasing until enough relations were found. As soon as sufficiently many relations were collected for a given target field, we stopped sieving for this field. Sieving timings and the number of collected relations for each target field are reported in Figure 2 (left).

It is to be noted that the precomputation step required 38.2 core-days, and that the 50 individual sieving steps took a total of 1788.6 core-days. If we had used the original FFS instead, we estimate that this computation would have required about 2991.3 core-days to produce a similar set of relations. Therefore, the FFS factory induced a speedup of 39 % on the overall computation time, that is, a saving of almost 3.2 core-years on an 8.2-core-year computation. As mentioned previously, we used Jeljeli's GPU implementation of the block Wiedemann algorithm for the linear algebra step [START_REF] Jeljeli | Accelerating iterative SpMV for Discrete Logarithm Problem using GPUs[END_REF]. Timings on Nvidia GTX 680 graphics cards, along with the dimension of the corresponding matrices (whose density was set to an average of 100 non-zero coefficients per row), are given in Figure 2 (right). This computation represents a total running time of 83.8 GPU-days.

Conclusion

In this paper, we have presented an adaptation of Coppersmith's "factorization factory" idea to the case of the Function Field Sieve for batching discrete logarithm computations in several finite fields of small characteristic. Along with a careful complexity analysis showing that this approach can be leveraged in practice to decrease the total computation time when enough target fields are considered, we also presented a working implementation of this algorithm based on the FFS implementation of cado-nfs. This implementation was used in a full-scale experiment in order to validate our analysis, thus solving the discrete logarithm problem in all the binary finite fields F 2 k ′ of odd extension degree k ′ and of size from 601 to 699 bits. For this experiment, the observed speedup against the original FFS algorithm was 39 %.

Even though the days of FFS are now numbered, it is far from obsolete yet, especially for finite fields of (almost) prime extension degrees and of size around or below 1000 bits. Future works include polishing the FFS factory implementation so that it can be published as part of the cado-nfs suite and, more importantly, using this approach to (pre)compute discrete logarithms in as many binary (or ternary) finite fields as possible so as to complete the database of factor bases in computer algebra systems such as Magma or Sage. Even though such computations need to be done only once, they still represent a huge endeavor when large field sizes are targeted.

  Time complexity, as the parameter c of L q k (1/3, c)

6 ]

 6 Field extension degree k ′Linear algebra time [GPU-days]Rows and columns [× 10Time for linear algebra Nb. of rows and columns in matrix

Fig. 2 .

 2 Fig.2. Timings for the relation collection step on each target field F q k ′ , for both the original FFS (estimated) and the FFS factory, along with the number of collected relations (left). Timings for the linear algebra step on each target field, along with the number of rows and columns of the corresponding matrix (right).

Selecting good polynomials for FFS is a non-trivial task, but it does not fall into the scope of this paper. For more details about this point, please refer to[START_REF] Barbulescu | Selecting polynomials for the Function Field Sieve[END_REF].


Brahim Tamadazte
email: brahim.tamadazte@femto-st.fr

Anthony Agustinos

Philippe Cinquin

Gaelle Fiard
email: gfiard@chu-grenoble.fr

Sandrine Voros

Multi-View Vision System for Laparoscopy Surgery

Keywords: Surgical robotics, laparoscopic surgery, distributed vision system, CMOS sensors, endoscopy, robotic endoscope holder, robotic surgery, clinical experiments

This paper deals with the development of a new generation of augmented laparoscopy system. We propose to equip a traditional endoscope, or a robotic endoscope holder, with a miniature stereovision device. The system includes two miniature high resolution CMOS cameras mounted around the endoscope as a pair of glasses that provides a global view of the abdominal cavity completing the traditional view. Each camera can reach a frame rate of 30 images/second with a resolution of 1600 × 1200 pixels. A deployment, fixation and rapid extraction system of the proposed device through the trocar was designed and validated through preclinical experiments (testbench and human cadaver). The main benefit of the proposed system in the minimally invasive surgery domain is to provide simultaneously local/global views, and with perspectives in 3D reconstruction of the organ being treated.

Introduction

Laparoscopy surgery, also known as minimally invasive surgery (MIS) or keyhole surgery, uses tiny incisions, usually less than 1 cm to perform intraabdominal or intrathoracic procedures as compared to the larger incisions needed in laparotomy. This approach offers decreased blood loss and postoperative pain, in addition to small hemorrhage, and shorter recovery time, while offering better cicatrization [START_REF] Makhoul | Laparoscopic radical nephrectomy for t1 renal cancer: The gold standard? a comparison of laparoscopic vs open nephrectomy[END_REF]. Laparoscopic surgery belongs to the broader field of endoscopy which consists in using a viewing system to visualize the operating field. The latter can be a rod lens system connected to a video camera [START_REF] Xie | Grin lens rod based probe for endoscopic spectral domain optical coherence tomography with fast dynamic focus tracking[END_REF] or a digital laparoscope where the charge-coupled device (CCD) sensor and the optical lens are altogether introduced inside the abdominal cavity [START_REF] Simi | Magnetic link design for a robotic laparoscopic camera[END_REF]. During a laparoscopic surgery, the surgeon often uses two to four specific surgical instruments introduced within the patients body through two to four trocars. Generally, the surgeon has an instrument in each of his hands and the endoscope is held by an assistant. Thus, the surgeon has no direct access to control the visualization of the endoscope. Robotic endoscope holders such as ViKY R [START_REF] Voros | An integrated port camera and display system for laparoscopy[END_REF], AESOP R [START_REF] Nathan | The voicecontrolled robotic assist scope holder aesop for the endoscopic approach to the[END_REF], EndoAssist R [START_REF] Dowler | The evolutionary design of an endoscopic telemanipulator[END_REF] or more complete telesurgery systems, such as the daVinci R robotic system [START_REF] Ballantyne | The davinci telerobotic surgical system: the virtual operative field and telepresence surgery[END_REF] have been developed to overcome these limitations. Despite the significant advance of the robotic endoscope holders and laparoscopy approaches, there are still improvements to be made to offer more intuitive systems.

The laparoscopic approach can be challenging for the surgeon for the following (non-exhaustive) reasons: [START_REF] Ballantyne | The davinci telerobotic surgical system: the virtual operative field and telepresence surgery[END_REF] difficult control of the surgical instruments;

(2) restricted field of view (FOV); (3) lack of visual access to hidden parts. They can make the operation difficult and the learning curve slower than for traditional procedures. In addition, the lack of information due to specular reflections and inhomogeneous illumination [START_REF] Marek | A robust motion estimation system for minimal invasive laparoscopy[END_REF] can hinder computer vision solutions to problems such as automatic organ or instruments detections.

More specifically, this paper focuses on the second reason by proposing an exhaustive global view of the surgical site to complement the traditional laparoscopic view. We believe that this approach will allow for a reduction of the endoscope's movements, allowing for a time gain and an enhanced focus on the surgical procedure rather than the control of the endoscope. In particular, our system could help avoid noble structures when manipulating the instruments, thanks to a wider FOV. This wider FOV is obtained by positioning two mini-cameras as a pair of glasses around the endoscope's trocar. The two cameras and the endoscope are inserted directly within the abdominal cavity through a standard trocar (so that no additional port is required, making it even be compatible with so called "single port procedures"). Once the system is inserted inside the scene, the cameras provide a panoramic view of the abdominal cavity, while keeping the same orientation as the endoscope (same point of view), as illustrated by Fig. 1.

In this paper, we focus on the presentation of a mechanical system and a procedure for the easy and quick insertion, deployment, fixation and retrieval of the cameras. Our proposed approach is validated 1) on a testbench which consists of porcine organs placed within a black box to simulate the abdominal cavity 2) through a human cadaver experiment.

The article is structured as follows: Section 2 presents a state of the art relative to the role of the vision sensor in laparoscopy systems and the existing systems in the literature. The developed materials are described in section 3. Section 4 presents the experimental scenario used to validate our developments and the obtained results. Discussions about the proposed vision device are reported in section 5. This paper ends by a conclusion and possible perspectives of our work: a) development of a disposable version of the proposed vision system, and b) first leads concerning possible user-interfaces exploiting our device (image mosaicing and 3D reconstruction).

State of the art

A possible approach to improve the quality of surgical procedures, consists in reducing their invasiveness and enhance the effectiveness of the surgeon [START_REF] Heemskerk | Advantages of advanced laparoscopic systems[END_REF]. For instance, voice activated robotic laparoscope manipulators increase the accuracy of the vision system and reduce personnel count [START_REF] Martinez | Tonatiuh ii: Assisting manipulator for laparoscopic surgery[END_REF], [START_REF] Voros | An integrated port camera and display system for laparoscopy[END_REF]. For successful surgical gestures, the surgeon must have access to reliable and rich information acquired from the vision system. Improving the quality of the vision system can be achieved by working on the miniaturization of the vision sensors (as the endoeye endoscope developed by Olympus R ) as well as on the mechanical cameras support (deployment, handling, fixation and extraction systems) [START_REF] Terry | An integrated port camera and display system for laparoscopy[END_REF], [START_REF] Covia | Miniaturized digital camera system for disposable endoscopic applications[END_REF], [START_REF] Koninckx | Endoscopic vision systems[END_REF], [START_REF] Kobayashi | A high-resolution three-dimensional thin endoscope for fetal surgery[END_REF].

Most of the laparoscopic vision systems described in the literature deal with the following concepts classified in two parts, lab prototypes and industrial devices. We position our work with respect to these concepts.

Industrial devices:

-(i) Stereo-endoscope (based on a left and right optical systems) replacing the traditional endoscope (mono-optical system) in order to form a right and a left images such as the daVinci stereo-endoscope [START_REF] Ballantyne | The davinci telerobotic surgical system: the virtual operative field and telepresence surgery[END_REF], [START_REF] Hu | Insertable stereoscopic 3d surgical imaging device with pan and tilt[END_REF]. Although these systems offer high-definition quality and stereovision capabilities, they do not allow for a panoramic view of the abdominal cavity, since the endoscope is displaced like a traditional endoscope. If the endoscope is inserted deep inside the abdominal cavity to obtain a precise visualization of the organ to operate on, the FOV may become narrower than when the endoscope is barely inserted inside the abdominal cavity, whether the endoscope is monoscopic or stereoscopic (Fig. 3).

Lab prototypes:

-(ii) Systems where the traditional endoscope is replaced by distributed vision systems (numerous individual cameras) [START_REF] Suzuki | Development of new augmented reality function using intraperitoneal multi-view camera[END_REF] or by two or three stereoscopy systems [START_REF] Tamadazte | Distributed vision system and virtual view for laparoscopic surgery[END_REF], [START_REF] Tamadazte | Enhanced vision system for laparoscopic surgery[END_REF]. In the latter, the cameras that compose the distributed system are independent from each another, requiring additional incisions for the insertion of the vision system. This system allows creating 3D virtual views of the abdominal cavity by fusing geometrical and color information provided by the cameras. The surgeon may thus explore virtually around the observed organs without moving any real camera but by displacing a virtual camera which provides real 2D images. The system proposed by [START_REF] Suzuki | Development of new augmented reality function using intraperitoneal multi-view camera[END_REF] presents a similar concept, but the cameras are mounted on a unique deployable structure allowing for a pre-operative calibration. -(iii) Laparoscopic systems equipped with a traditional endoscope and an additional camera mounted on a surgical instrument [START_REF] Terry | An integrated port camera and display system for laparoscopy[END_REF], [START_REF] Terry | Single port access surgery with a novel port camera system[END_REF]. This type of device is also called as port-camera. The main clinical gain of such systems is the ability to perform single-port laparoscopy, especially in the case of a simple biopsy or exploration of the abdominal cavity. However, other problems associated to the use of such systems appear, such as registration difficulties and image stability. -(iv) Articulated stereo-endoscope supposed to replace the conventional endoscope by a pan and tilt stereo-cameras, especially in order to improve visualization and depth perception [START_REF] Hu | Insertable stereoscopic 3d surgical imaging device with pan and tilt[END_REF], [START_REF] Miller | In-vivo stereoscopic imaging system with 5 d egrees-offreedom for minimal access surgery[END_REF], [START_REF] Rentschler | Mobile in vivo camera robots provide sole visual feedback for abdominal exploration and cholecystectomy[END_REF]. -(v) Magnetic-based grip miniature camera: a miniature camera is attached to abdominal wall using external magnetic fields provided from metal parts of a robotic arm [START_REF] Simi | Magnetic link design for a robotic laparoscopic camera[END_REF]. This last work is closely related to our proposed system. Its main drawback is that in order to exploit fully the potential of the added camera, a registration is necessary between the traditional laparoscope and the miniature camera, which can be challenging inside the patient. Our proposed system avoids this problem, since the miniature cameras have roughly the same axis as the laparoscope by construction. Given to this state-of-the-art, our proposed system aims at offering:

-A stereovision system (objectives of the work described in items (i), (ii), (iv)), -A large FOV of view and depth of field (objectives of (iii) and (v)), -A low cost system (aim of (ii)), -A system that does not require in-situ registration between images (endoscope and additional cameras images) (required in (i) or (v) for instance), -A system that does not require additional incisions (objective of (i), (iii), (iv), and (v)).

In the next section, we present the used resources and the proposed mechanical system, in order to provide the improvements listed above.

Materials

CMOS Cameras

Our proposed enhanced endoscopy vision system includes two miniature and high resolution cameras in addition to the classical mono-view endoscope. The cameras are based on two 5 mm × 5 mm × 3.8 mm complementary metal oxide semiconductor (CMOS) sensors with (Fig. 2):

a resolution of 1600 × 1200 pixels, -a frame rate of ≈ 30 frames/second, -a low noise/signal ratio, -an exposure control of +81 dB, -a FOV of 51 • with a low TV distortion (≤ 1%), -a cost of the presented camera of a few US dollars (in large scale diffusion). These characteristics are similar to High-Definition classical endoscopic systems. For instance the daVinci endoscope has a 1920×1080 resolution, with a FOV of 70 • horizontally and 50 • vertically. However, compared to our system, the daVinci's camera system is positioned ex-vivo with a complex optical system compared to mini-CMOS cameras. Moreover, even though the horizontal FOV is a bit larger for the daVinci's endoscope than for our proposed system, the more the endoscope is inserted in the abdominal cavity, the more its FOV will be reduced compared to our panoramic system, as illustrated by Fig. 3: let d 1 be the distance of a simple 50 • FOV camera within our proposed panoramic system to a given object, and d 2 be the distance of a mobile 70 • FOV endoscope to the same observed object; simple trigonometrics show that as soon as the ratio d2 d1 is inferior to tan(25 • ) tan(35 • ) = 0.6, the area observed by the panoramic system will be wider than the area observed by the mobile endoscope. For instance, if d 1 = 10 cm, the 50 • FOV camera's observed width will be the same as that of a 70 • mobile endoscope positioned at d 2 = 6 cm of the observed object. However, if the 70 • mobile endoscope is positioned at d 2 = 2 cm of the observed object, its view width will be of 2,8 cm whereas the view width of a CMOS 50 • FOV camera positioned at 10 cm of the observed object will be of 9.3 cm.

Multiple View Vision System

Obviously, our approach is not to remove completely the traditional endoscope, which is popular and widely used in the operating rooms; but to propose an addition to the laparoscope, which does not modify consequently the usual practices of surgeons, and which should not require lengthy learning phases. This motivated us to adapt our vision system to existing endoscopes (or trocars).

Deploying the system (ie. the two mini-cameras) inside the abdominal cavity through a 10 mm diameter trocar without a visual control is challenging.

The surgeon should be able to deploy, stabilize and extract (particularly in the case of an emergency) the device easily and quickly. After having studied several design options (precisely 3 different prototypes), we have chosen the design shown in Fig. 4. The cameras are prepositioned in a hollow tube with sliding rails (see the exploded view in Fig. 4), in which the laparoscope trocar is inserted. The proposed device is deployed when the surgeon inserts the endoscope that will push cameras out of the sliding rails (see step 1 in Fig. 5). When both cameras are out of the sliding rails (see step 2 and step 3 in Fig. 5), and the endoscope is fully inserted, the proposed vision system is completely introduced in the abdomen cavity. However, at this stage of deployment, the cameras are not fully stabilized (see step 4 in Fig. 5). By pulling on the acquisition/power cables of the system, the surgeon fixes the cameras in place (see step 5 in Fig. 5) which shows the obtained deployment for one camera), and the cameras now have a point of view very close to that of the endoscope, and a stereoscopic configuration.

Once the device is deployed, it takes the form of a pair of glasses around the laparoscope's trocar allowing access to a large FOV of the abdominal cavity (Fig. 6). In addition, with the particular positioning of the cameras, our system has other advantages such as the ability to visualize and control the insertion of surgical instruments, allowing for instance to avoid undesirable contact between the surgical instruments and organs/tissues.

To extract the global vision system, the surgeon removes the endoscope first, then he simply pulls on the power/acquisition cables to remove the cameras one after the other. Indeed, the cylindrical element positioned on the upper part of each camera (see the exploded view in Fig. 4) guides each camera back inside the trocar.

Fig. 5 Illustration of the different steps of the functioning of the developed deployment/removal system. For a better understanding, only one camera was used in this illustration.

Fig. 6 Photography showing the developed system when deployed and fixed to the endoscope carried by the ViKY robot.

ViKY Robot

To validate and quantify the proposed vision device, we decided to use the robotic endoscope holder ViKY R commercialized by EndoControl, Grenoble Fig. 7) resulting from the research work of the TIMC-IMAG Laboratory [START_REF] Long | Development of miniaturized light endoscope holder robot for laparoscopic surgery[END_REF]. The ViKY can be fixed on the operating table with a passive and articulated arm and directly placed on the patient's abdomen. It is easily integrated in the operating room and fully sterilizable (mechanical structure, cables, motors, etc.). It is equipped with 3 degrees-of-freedom (dofs). The first dof ie. θ (Fig. 7(a)) allows left/right moves which represent displacement of the robot along the x axis of the laparoscopic image. The second dof ie. z (Fig. 7(b)) is to control the insertion of the endoscope in the human body allowing zoom in/zoom out motions. Finally, the φ dof (Fig. 7(c)) allows for up/down moves that corresponding to the displacements along the yaxis of the laparoscopic image. ViKY R can be controlled with 4 different techniques: manual control (when the motors are off), pedal control, vocal recognition-based control and semi-automatic/automatic control using vision feedback control [START_REF] Wolf | 3d tracking of laparoscopic instruments using statistical and geometric modeling[END_REF].

We use the ViKY R robot as an endoscope localizer for our experimental validation tests. The robot has a recording console capable of saving both the time of each performed task, the number of orders sent to the different robot's dof and their respective amplitudes which correspond to the endoscope movements.

Validation Scenario and Results

Validation Scenario

Our validation was performed on a testbench mimicking a laparoscopic setup. Porcine organs were placed into a black box. The traditional endoscope was carried by the robotic system ViKY R , allowing us to record the displacements performed by the endoscope and the vision system (number of commands issued, amplitude of the endoscope's displacements, and time needed to perform these displacements) (Fig. 8).

One experimented urologist surgeon, one medical intern were asked to repeat 17 times the same experiment which consisted in performing a specific surgical task, once with the traditional endoscope alone, and once with the innovative vision system alone. We decided to use the innovative vision system alone, rather than combined with the traditional endoscope, in order to ensure that the vision system was used for guidance, and not the classical endoscopic images that the surgeons are accustomed to. At each realization of the experiment, the surgeon started randomly with the endoscope or with the vision system, to avoid a learning bias. The surgical task consisted in At the beginning of each task, the needle was positioned randomly at a fixed distance to the target point. The distance was chosen such as the initial needle position was not visible in the laparoscopic image. We recorded the time required to perform the task, the number of orders given by the surgeon to the ViKY R robot in order to move the endoscope or the vision system and the log files of the ViKY R robot indicating the actual displacements of the robotic holder's motors (ie. θ, φ and z).

Results

The results given in this section were obtained by repeating the experiment described in the previous section 17 times by two operators alternately using the proposed vision system and a traditional endoscope. Fig. 9 represents the disposition of the different views (proposed vision device and traditional endoscope). It can be noticed that the images given by the proposed system offers a large FOV comparing to the endoscope image. It is even possible to see the surgical instrument (Fig. 9(a)) during the insertion task which is not visible in the endoscopic view.

Table 1 shows that the time required for a surgeon to perform the task with the endoscope and the developed system, respectively. The surgeon needs an average of 2.1 minutes for a successful task using the endoscope alone when he or she needs only 0.49 minutes using the developed vision system. This represents a time gained of a factor of 4.2. For example, for a wound 1).

The new concept offers more than 27.25 minutes of time gained compared to a traditional endoscope alone. The total number of commands given by the surgeon to ViKY (through the assistant) is illustrated in Table 2. In the case of the use of the traditional endoscope, the surgeon needs to give an average of 27.2 commands to ViKY/assistant to perform one stitch. Moreover, only 5.7 commands suffice to perform the same stitch using the new device. A total of 211 commands were sent to the 3 dof of the robot to achieve the 17 experimental tests using the endoscope versus 69 using the developed concept. This gain in terms of number of commands required to move the vision system could benefit the surgeon by allowing him/her to concentrate better on the surgical task.

In order to assess whether the difference observed between the two visualization devices was significant, we applied the Wilcoxon test on unpaired series to the studied variables. This test is a non-parametric test, with no constraint on the sample size. This test shows in a statistically significant way that the medians of the compared distributions between the two studied groups (endoscope or novel system) are different: if the p-value is inferior to 0.05, there is a 5% chance to conclude wrongly that the difference between groups is significant [START_REF] Wilcoxon | Individual comparisons by ranking methods[END_REF]. The Wilcoxon test was applied on two series: the consumed-time and the number of commands sent to ViKY using our vision system and using the endoscope, respectively. The obtained p.value are 0.03156 (for the timeconsuming series) and p.value = 0.00544 (for the commands sent series) which show that, according to the Wilcoxon test, there is a statistically meaningful improvement in using our system compared to a traditional endoscope alone, both in terms of time and number of commands sent.

Discussions

To test our system in conditions close to clinical practice, we performed an experiment on a male cadaver (human body) with a surgeon of the Grenoble's hospital who performed a radical prostatectomy. We tested the insertion, the deployment and the fixation techniques of the proposed vision concept (Fig. 10). This first experiment was cut short because of problems with the cameras' connectivity: the flexible acquisition cable, built for mobile phones, was very short, which complicated the insertion of the device inside the pa-Fig. 10 Photography of the preclinical validation of our system on a human cadaver.

tient. However, it allowed us to validate the first version of our new vision system and to identify improvements to be made in the aim of creating a device compatible with clinical constraints:

-The first possible improvement concerns essentially the sterilization (reusable system) or the non-sterilization (disposable system) of the device. It should be noticed that the cost of the developed device will be only a few US dollars for small and medium manufacturing series (without taking into account the cost of clinically-compatible housing). The price of the vision device could be about the same as the price of a disposable 5-10 mm Auto Suture R trocar (≈ 20 US dollars). Furthermore, the repetitive sterilization process could damage the CMOS sensors. From a medical point of view, it could be more appropriate to opt for a disposable system: it would be always easily available, with a flawless sterilization (ie. sterilized once before its packaging), its manipulation would be limited, with lower costs and enhanced safety and security for the patient. -A study on the coating of the cameras should be conducted. The elements that will be used to coat the cameras must be biocompatible, compact (to save the functionality of deployment and retrieval of the cameras through the trocar), and ensure that the CO2 introduced into the patient's abdomen does not leak (at the trocar). From the first investigations about this point, it appears that the Parylene CVD (class 4 according to the FDA regulation) could be an appropriate solution. The Parylene CVD can be deposited on materials with layers ranging from 50 nm to a few hundred micrometers in low temperature conditions. -The designed deployment and extraction system must be tested by several surgeons before final validation. To date, it has been tested on an experimental set-up but never on a patient. Thus, our next step is to test the device several times in conditions closer to the clinical reality with tests on cadavers or animals. Those tests will help us in estimating the time required to extract the developed system in case of emergency. They will allow us to prepare for a biomedical protocol for a validation of the approach through clinical trials. With a larger number of experiments, we will also be able to perform more in-depth statistical analysis for the quantification of the expected time gain with the system. Indeed, during our experiments, we observed a large standard deviation in the time required for performing a task, with the endoscope or with the global vision system. This high standard deviation is due to the initial random choice of the surgeon on the direction he will take to follow the needle thread. If he takes the right direction immediately, the task completion time will be short, but if he takes the wrong direction, the task time will be much longer.

As stated in the introduction, the paper focuses on describing the device and first experiments of its potential benefits during a laparoscopy. We

have not yet taken into account human machine interfaces, but we will of course need to study display possibilities that exploit the potential of multiple vision, without surcharging the visual information provided to the surgeon. These questions will be addressed in the Future Works section.

conclusion

The drawbacks and the limitations of the use of the classical endoscopy vision system led us to develop a cheap multiple view (coarse and local views) vision system (cost of few US dollars). The system is based on miniature cameras positioned like a pair of glasses around the classical endoscope. Thus, the proposed device has, by construction, a point-of-view almost similar to that of the endoscope, which implies that it does not require registration techniques between the endoscope images and the mini-cameras of the multiple view system. This device is not more invasive than standard endoscopy since it is inserted through the laparoscope's trocar. We also presented our deployment, fixation and rapid extraction design and provided first estimations of its potential during preclinical experiments (porcine organs and human cadaver). The validation tests have been achieved by 2 operators (one urologist surgeon and one medical intern) and consisted in performing a series of stitches using only the endoscope, then only the developed device. In addition to the significant improvements provided by the cameras, particularly in terms of FOV, the use of the multiple views system allows time-savings of a factor of 4.2 (ie. 35.7 minutes are necessary to perform) 17 experimental tests using the endoscope and only 8.45 minutes are necessary using the new concept. Also, the voice orders sent to ViKY robot endoscope-holder during the different experiments have been saved and accounted for in both cases: 211 commands (endoscope case) and 69 commands (proposed concept case). This shows that the surgeon can be concentrated in the surgery task rather than the communication with robotic endoscope-holder or his assistant. 7 Future Works

A disposable global view system?

As mentioned earlier in this paper, we study currently a disposable (singleuse system) version of our vision device. Due to a lower cost (few US dollars) manufacturing (in medium and large series), we consider that it is preferable to provide a disposable system. This will avoid numerous sterilization cycles which generate additional costs and can damage the cameras. The fact that the cameras are already prepositioned in the sliding rails (Fig. 11) (the system can be marketed in this form) allows for the introduction of the cameras during the endoscope trocar insertion phase of the surgery. To deploy vision system, the surgeon inserts the endoscope that will push cameras out the sliding rails. Then, thanks to a simple pulling of the cameras power cables, the vision system will be positioned around the endoscope as glasses. This installation and deployment step should not increase much the surgery time compared to the expected time gain using the system.

Towards 3D reconstruction and navigation

As we stated earlier, this paper focused on the potential on using our proposed device for laparoscopic surgeries. We have not considered yet the manmachine interface questions, for a display of the new information provided by our panoramic system compatible with the surgical workflow. We now need to address those issues. A first step could consist in working on a mosacing of the images, to combine in a single display then endoscopic view and the two views provided by our system. Another solution could consist in creating a 3D model of the scene, from the two cameras of our system that are in stereoscopic conditions (Fig. 12, for more details, please refer to [START_REF] Tamadazte | Distributed vision system and virtual view for laparoscopic surgery[END_REF]), [START_REF] Suzuki | Development of new augmented reality function using intraperitoneal multi-view camera[END_REF].

Fig. 1

 1 Fig. 1 Schematization of the proposed concept of global vision system.

Fig. 2

 2 Fig. 2 Photography of the CMOS cameras which equip the proposed global view imaging system.

Fig. 3

 3 Fig.3An endoscope FOV vs. our system FOV.

Fig. 4

 4 Fig. 4 CAD model of the proposed multiple view device illustrating the different elements with compose the system.

Fig. 7

 7 Fig. 7 Representation of the 3 dofs ViKY robotic scope holder where (a), (b) and (c) illustrate the move lef t/move right, zoom in/zoom out, and move up/move down motions, respectively.

Fig. 8

 8 Fig. 8 Photography of the experimental set-up used to simulate the abdominal cavity and validate the different proposed materials and techniques.

Fig. 9

 9 Fig. 9 Illustration of the images shown to the surgeon during the experimental validation: (a) the image acquired by the left camera, (b) the image given by the endoscope and (c) the one given by the right camera.

Fig. 11

 11 Fig. 11 Illustration of the proposed multi-view vision system (in its disposable version).

Fig. 12

 12 Fig.123D reconstruction used the proposed vision device.

Table 1

 1 Summary of the time-consumed for 17 different tests using the both vision systems. Note That T is the total time consumed for the entire test, µ is the mean time for each test, and σ is the standard deviation.

	vision system	T (minutes) µ (minutes) σ (minutes)
	endo.	35.7	2.1	0.92
	dev. system	8.45	0.49	0.47

localizing a suture needle placed in the abdominal cavity; -bringing it to a fix target point (representing the organ of interest for the task).

Table 2

 2 Summary of the number commands given to ViKY's dofs using the two types of visualization system. Note that T is the total commands sent to ViKY, µ is the mean commands of each test and σ is the standard deviation.

	vision system	T	µ	σ
	endo.	211	23.16	10.48
	dev. system	69	4.6	3.44
	of 17 experimental tests, 35.7 minutes are necessary for the surgeon with the
	endoscope, and only 8.45 minutes are needed with proposed device (Table

Acknowledgements This work is partially conducted with financial support from the project "Projet ANR-TECSAN 2009 DEPORRA" funded by the program TecSan from the Agence Nationale de la Recherche (ANR), France.