Pascal Giorgi
email: pascal.giorgi@lirmm.fr

Bruno Grenet
email: bruno.grenet@lirmm.fr

Armelle Perret
email: armelle.perret-du-cray@lirmm.fr

Du Cray

Polynomial modular product verification and its implications

Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations.

We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product.

Introduction

Polynomials are one of the most basic objects in computer algebra and the study of fast polynomial operations remains a very challenging task. Polynomials can be represented using either the dense representation, that stores all the coefficients in a vector, or the more compact sparse representation, that only stores nonzero monomials. Depending on which representation is chosen the problems might have a very different flavor leading to two very separate lines of research.

Polynomial multiplication is the most noticeable problem that attracted a lot of attention since many decades, culminating nowadays with quasi-optimal algorithms [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF][START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF]. Although such algorithms are really efficient in theory and in practice, there are not yet optimal and they often rely on complex approaches that can be error prone. Therefore, looking for rather simple procedure to verify the correctness of polynomial products is of great interest. From a theoretical perspective, the goal is then to provide asymptotically faster algorithms than those for multiplying polynomials, ultimately seeking for an optimal algorithm. In practice the objective is barely to find simpler and faster procedures that reveal easier to trust.

In this work, we intend to present the most recent advances in verifying polynomial products in both the dense and sparse case, to extend such results to either optimal algorithms or to more reliable solutions in practice. Finally, we extend the problem to some specific modular multiplication of polynomials which seems to not having been explored yet.

Dense polynomial multiplication

We know from the early 60's that dense polynomial arithmetic is subquadratic, and that it can even be quasi-linear when the so-called FFT applies [START_REF] Cooley | An Algorithm for the Machine Calculation of Complex Fourier Series[END_REF]. It has been more than two decades later that Cantor and Kaltofen [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF] provide a quasi-linear algorithm without any assumption on the polynomial algebra. They show that two dense polynomials of degree less than n over an algebra can be multiplied with (n log n log log n) operations in . In regards to the bit complexity model, the operations in the base ring cannot count (1) anymore, and the previous algorithms may not lead to the best complexity estimates for specific domains such as = q or = . There, the use of Kronecker substitution together with fast integer multiplication turns out to be the best alternative [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]Section 8.4]. It has been showed by Harvey and van der Hoeven in [START_REF] Harvey | Faster polynomial multiplication over finite fields using cyclotomic coefficient rings[END_REF] that one can reach a bit complexity of (n log q log(n log q)4 log * (n) ) for polynomial multiplication over q [X ] for any prime field q . We shall mention that very recently, such complexity have been further improved to (n log q log(n log q)) bit operations [START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF] under some mild hypothesis. For polynomials with integer coefficients bounded by an integer C, the complexity falls down to multiplying two integers of bit length (n(log n + log C)) which gives (n(log 2 n + log C log n + log C log log C) = ˜ (n log C) 1when we assume that n-bits integer multiplication complexity is I(n) = (n log n) [START_REF] Harvey | Integer multiplication in time O(n log n)[END_REF]. For clarity in the presentation, we will often use M(n) as the number of operations in required to multiply two dense polynomials of size n, while M q (n) will denote the bit complexity for such multiplication over a prime field q .

Sparse polynomial multiplication In the sparse representation, a polynomial F = n i=0 f i X i ∈ [X ] is expressed as a list of pairs (e i , f e i ) such that all the f e i are nonzero. We denote by #F the sparsity of the polynomial F which corresponds to its number of nonzero coefficients. Let F be a polynomial of degree n, and log C be a bound on bit length of its coefficients. Then, the size of the sparse representation of F is (#F (log n + log C)) bits. Contrary to the dense case, note that fast algorithms for sparse polynomials must have a (poly-)logarithmic dependency on the degree, and that the size of the output does not exclusively depend on the size of the inputs. Indeed, the product of two polynomials F and G has at most #F #G nonzero coefficients. But it may have as few as 2 nonzero coefficients, as shown by the following example.

Example 1. Let F = X 14 + 2X 7 + 2, G = 3X 13 + 5X 8 + 3 and H = X 14 -2X 7 + 2. Then F G = 3X 27 + 5X 22 + 6X 20 + 10X 15 + 3X 14 + 6X 13 + 10X 8 + 6X 7 + 6 has nine terms, while F H = X 28 + 4 has only two.

Another difference with the dense case is that studying the complexity in a pure algebraic model remains meaningless, unless you assume a transdichotomous model on the degree, meaning that the integer computation on the exponents is always (1) [START_REF] Cole | Verifying candidate matches in sparse and wildcard matching[END_REF][START_REF] Nakos | Nearly optimal sparse polynomial multiplication[END_REF]. The classical approach for computing the product of two polynomials of sparsity T is to generate all the T 2 possible monomials, and to sort them and merge those of equal degree to collect the monomials of the result. Using radix sort, this algorithm takes for instance (T 2 (I(log C) + log n)) bit operations over and it exhibits a T 2 factor in the space complexity, whatever the number of terms in the result. Many improvements have been proposed to reduce this space complexity, to extend the approach to multivariate polynomials, and to provide fast implementations in practice [START_REF] Johnson | Sparse polynomial arithmetic[END_REF][START_REF] Monagan | Parallel sparse polynomial multiplication using heaps[END_REF][START_REF] Monagan | Sparse polynomial division using a heap[END_REF]. Yet, none of these results reduces the T 2 factor in the time complexity. In general, no complexity improvement is expected as the output polynomial may have as many as T 2 nonzero coefficients. However, this number of nonzero coefficients can be overestimated, giving the opportunity for output-sensitive algorithms. Such algorithms have first been proposed for special cases. Notably, when the output size is known to be small due to sufficiently structured inputs [START_REF] Roche | Chunky and equal-spaced polynomial multiplication[END_REF], especially in the multivariate case [START_REF] Van Der Hoeven | On the Complexity of Multivariate Blockwise Polynomial Multiplication[END_REF][START_REF] Van Der Hoeven | Structured FFT and TFT: Symmetric and Lattice Polynomials[END_REF], or when the support of the output is known in advance [START_REF] Van Der Hoeven | On the bit-complexity of sparse polynomial and series multiplication[END_REF].

Output-sensitive multiplication algorithms try to take into account the two reasons that can decrease the sparsity of the product. The first one is exponent collisions, while the second one occurs when these collisions imply some coefficient cancellations. The exponent collision is captured by the sumset of the exponents of F = T i=1 f i X α i and G = T j=1 g j X β j , that is {α i + β j : 1 ≤ i, j ≤ T }. Arnold and Roche call this set the structural support of the product F G and its size the structural sparsity [START_REF] Arnold | Output-sensitive algorithms for sumset and sparse polynomial multiplication[END_REF]. If H = F G, then the structural sparsity S of the product F G satisfies 2 ≤ #H ≤ S ≤ T 2 . Observe that although #H and S can be close, their difference can reach (T 2 ) as shown by the next example. iT ) and H = F G. We have #F = T , #G = 2T and the structural sparsity of F G is T 2 + 1 while H = X T 2 -1 has sparsity 2.

Example 2. Let F = T -1 i=0 X i , G = T -1 i=0 (X iT +1 -X
For polynomials with non-negative integer coefficients, no coefficient cancellation can occur and Cole and Hariharan describe a multiplication algorithm requiring ˜ (S log 2 n) operations in the RAM model with (log(C n)) word size [START_REF] Cole | Verifying candidate matches in sparse and wildcard matching[END_REF], where log(C) bounds the bitsize of the coefficients. Arnold and Roche improve this complexity to ˜ (S log n + #H log C) bit operations for polynomials with both positive and negative integer coefficients [START_REF] Arnold | Output-sensitive algorithms for sumset and sparse polynomial multiplication[END_REF]. A recent algorithm of Nakos avoids the dependency on the structural sparsity for the case of integer polynomials [START_REF] Nakos | Nearly optimal sparse polynomial multiplication[END_REF], using the same word RAM model as Cole and Hariharan. Unfortunately, the bit complexity of this algorithm, ˜ ((T log +#H log 2 n) log(C n) + log 3 n), is not quasi-linear. More recently, we propose in [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF] the first quasi-optimal algorithm for sparse polynomial multiplication yielding a bit complexity of ˜ (T (log n + log C)) where T = max(T, #H). More precisely, taking k = T (log n + log c) which is the bit length of the input and output, we are able to reach a bit complexity of (k log 2 k log 2 T (log T + log log k)).

Verification of polynomial products

Considering the non-optimality of polynomial multiplication in both representations, it is quite natural to ask whether it is rather a simple task or not to verify an instance of the problem. More formally, given three polynomials F, G and H, can we assert that H is equal to the product of F and G in less operations than computing the product itself? Furthermore, we want such procedure to be as simple as possible and to not rely on polynomial multiplication if possible. Unfortunately, doing this with a deterministic procedure is not yet known, but using probabilistic algorithms lead to positive answers as shown by several papers [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF][START_REF] Schwartz | Fast probabilistic algorithms for verification of polynomial identities[END_REF][START_REF] Zippel | Probabilistic algorithms for sparse polynomials[END_REF][START_REF] Giorgi | A probabilistic algorithm for verifying polynomial middle product in linear time[END_REF]. Here and henceforth, polynomials are assumed to have coefficients in an integral domain , rather than in a more general algebra.

For dense polynomials this verification amounts to choosing a random element α in a finite subset of and to assert that H(α) -F (α)G(α) is zero. In that case, the complexity for the verification becomes (n) operations in , which is optimal. Of course, the probability of error is less than one as soon as has more than n elements. If this not the case, for instance when = 2 , it is not desirable to choose α in a sufficient large extension of to have (n) elements. The latter would require an extension of degree (log n) and it would raise the complexity to (nM(log n)). This is actually larger than the complexity M(n) of computing the product. In [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF], Gamin's solved the latter problem by replacing the evaluation, that corresponds to computing within [X ]/(Xα), by doing a polynomial multiplication within [X ]/(X i -1) for a random integer i < n. More precisely, by choosing i = (n 1-e ) for some 0 < e < 1/2, his verification algorithm runs in (n) operations in , whatever its size, with a probability of error bounded away from one. While the result sounds optimal from a theoretical perspective, it might be mitigated for practical applications as it verifies polynomial multiplication of degree n by doing multiplication of polynomials of degree (n 1-e ).

All these results remain valid under the bit complexity model, but the obtained complexity might not be optimal. For polynomials over q [X ], both approaches using products in q [X ]/(Xα) or in q [X ]/(X i -1) lead to a bit complexity of (nI(log q)) = (n log q log log q). While being non optimal, they remain however asymptotically faster than the computation of the initial products by a factor log n/ log log q. Actually, Kaminski's approach has a better bit complexity than the standard method and can even yield a linear bit complexity in favorable cases. For polynomials over [X ], the result is more surprising as it is possible to reach an optimal bit complexity of (n log C) for any input. This result should be attributed to Kaminski, as he provided in [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF] all the necessary materials while not noticing the result explicitly. It seems surprising, but we haven't found any references advertising such result. Thus, we propose to provide the description of those optimal verifications of polynomial products.

For sparse polynomials, the verification of products remains less studied. It is misleading to think that using polynomial evaluation is satisfactory. Assuming that only T coefficients are nonzero, sparse polynomial evaluation is not quasi-linear in the input size (T (log n + log C)). Indeed, computing α n requires (log n) operations in which implies a complexity of (T log n) operations in when applied to the T nonzero monomials. Since one needs to use a subset of of size at least n to ensure a nonzero probability of success, this implies that the bit complexity is at least (T log 2 n). Using similar ideas as Kaminski's [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF], we proposed recently in [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF] to verify sparse polynomial identities by doing the computation in [X ]/(X p -1) for a random prime p. In particular, we prove that choosing p = (T 2 log n) ensures that (H -F G) mod (X p -1) = 0 implies that H -F G = 0 with good probability and that the computation can be done in quasi-linear time with ˜ (T (log n + log C)) bit operations.

Another important measure for randomized verification algorithms is the probability of failure. All the known verification algorithms are True-biased one-sided Monte Carlo algorithms. This means that they always return True if H = F G and return False with probability at least 1-ε otherwise. Given an algorithm with error probability at most ε, we can attain any smaller probability of error τ by repeating ( log τ log ε ) rounds of the algorithm. This shows that the complexity of the algorithm is actually dependent on the target error probability. In our results, we always explicitly indicate this dependency. We can distinguish several regimes of values for the error probability: the constant regime ε = (1), the inverse polynomial regime ε = 1/n (1) and the inverse exponential regime ε = 1/2 (n) , where n is the input degree. Given an algorithm with constant error probability, one can attain any smaller constant probability using a constant number of rounds. This keeps the same asymptotic complexity. The same is true for two probabilities inside the inverse polynomial regime. To get to the inverse polynomial regime from the constant regime, the number of rounds must be (log n), slightly increasing the asymptotic complexity. The inverse exponential regime can then be attained using a polynomial number of rounds. In our context of linear and quasi-linear algorithms, the inverse exponential regime is not attainable in general. The best known verification algorithms have linear bit complexity in the inverse polynomial regime.

Contributions

As an extension of our prior work [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF], we propose to study more generally the verification of polynomial multiplication in [X ]/P where P is a monic sparse polynomial. In the dense case, this generalizes a work from one of the authors on the probabilistic verification on polynomial middle product [START_REF] Giorgi | A probabilistic algorithm for verifying polynomial middle product in linear time[END_REF]. By reusing our modular product's verification, we show that we can address the difficulty of Kaminski's approach that verifies polynomial products using products of roughly the same degree, more than n. In particular, we show that we can avoid the dependency on polynomial multiplication in every cases. When dealing with finite field arithmetic it is quite common to rely on irreducible polynomials that are sparse [START_REF] Mullen | Handbook of Finite Fields[END_REF]. Therefore, having the possibility to verify multiplication over finite fields in less operations than computing the product seems of great interest. In particular, we show that the verification of products in q s can be done in (s#P) operations in q where P ∈ q [X ] is the monic irreducible polynomial of degree s used to define q s . Clearly for irreducible polynomial with constant sparsity, as it is often the case over 2 [START_REF] Golomb | Shift register sequences[END_REF] and more generally q [START_REF] Mullen | Handbook of Finite Fields[END_REF], this offers an optimal verification procedure. Finally, for sparse polynomials, this work extends our prior result for [X ]/(X p -1) in [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF] that was of great importance to achieve the first quasi-linear time algorithm for sparse polynomial multiplication. We hope our new insight on this problem will leverage other fast algorithms for sparse polynomial operations, especially for the division problem [START_REF] Roche | What can (and can't) we do with sparse polynomials?[END_REF].

All our techniques and results extend to the more general problem of verifying a polynomial identity of the form i F i G i mod P = 0, where the sum may have an arbitrary number of terms. It would be interesting to be able to extend these results to more general polynomial identities. As a very simple example, given F 1 , F 2 , F 3 , H and P ∈ [X ] for some integral domain , what is the complexity of the verification of H = F 1 F 2 F 3 mod P? Obviously if the inputs are dense polynomials, the computation of F 1 F 2 F 3 mod P can be done in quasi-linear time. But the question is to design an algorithm than runs faster than performing the computation. In the sparse case, the computation may increase the input size quite a lot and even a quasi-linear time algorithm is lacking. More generally, the problem is to verify identities of the form i j k • • • F i, j,k,..., mod P = 0. This problem can be phrased as a Modular Polynomial Identity Testing (Modular PIT) problem. The standard Polynomial Identity Testing (PIT) problem takes as input an arithmetic circuit, or equivalently a straight-line program, and consists in deciding whether the polynomial it represents is zero. In this extension, a polynomial P is also given as input and the question is whether the polynomial represented by the circuit is divisible by P. The standard PIT problem admits polynomial-time, and even quasi-linear-time, randomized algorithm. A very important open question is whether it also admits a polynomial-time deterministic algorithm. For the Modular PIT problem, the question is already to design efficient randomized algorithms. If the dense case, the challenge is to obtain faster algorithms than performing the product, ideally linear-time algorithms. In the sparse case, it is not even known how to solve the problem in randomized polynomial-time. Our results may be seen as a first step towards this goal.

Outline We start our work in Section 2 by introducing all the technical materials that serve to demonstrate our main results. Then, Section 3 is devoted to the study of the evaluation of modular multiplication. In particular, we provide algorithms and their thorough analysis for evaluating (F G) mod P on α without computing F G mod P. The results of that section serve to derive efficient algorithms in Section 4 for the verification of modular multiplication of polynomials. Finally, we present in Section 5 the more general results on the verification of classical polynomial multiplication. In particular, we extend the work of Kaminski [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF] for the dense case with a thorough analysis of its bit complexity that enables to reach optimal verification. We also give a more detailed presentation of our first quasi-optimal algorithm for the sparse case that appears in [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF].

Preliminaries

Notations and complexities

Let Q ∈ [X ] be a degree-n polynomial. We denote its coefficient of degree i by q i . The sparsity of Q is its number of nonzero monomials and is denoted by #Q. The support of Q is the set supp(Q) = {i : q i = 0}. If Q is a polynomial over , we denote by Q ∞ its norm, defined as max 0≤i≤n |q i |. We denote by log(•) the base-2 logarithm and by ln(•) the natural logarithm. We also use log b (•) to denote the base-b logarithm defined by log b (x) = log x log b . We work in this paper with dense and sparse polynomials. A dense polynomial is represented as the vector of its coefficients, which has size n + 1 for a degree-n polynomial. A sparse polynomial is represented by the list of its nonzero monomials. We consider that we work, for sparse polynomials, with an abstract structure of sparse vector. In practice, this can be implemented by several data structures, depending on the operations that need to be performed. A standard choice in sparse polynomial arithmetic is the use of heaps [START_REF] Johnson | Sparse polynomial arithmetic[END_REF][START_REF] Monagan | Parallel sparse polynomial multiplication using heaps[END_REF][START_REF] Monagan | Sparse polynomial division using a heap[END_REF]. To get better complexities, we might resorting to van Emde Boas Trees [START_REF] Th | Introduction to Algorithms[END_REF]Chapter 20] as in Section 3.3.We also use sparse vectors in some algorithms to represent data which are not directly polynomials. The underlying data structure is the same as for sparse polynomials.

Complexity of dense polynomial multiplications

We denote by M(n) the number of ring operations needed to compute a product of degree-n dense polynomials over an integral domain. We can take M(n) = (n log n log log n) [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF]. We denote by M q (n) the bit complexity of the multiplication of two degree-n dense polynomials over a finite field q . The best known bounds on M q (n) are (n log q log(n log q) 4 log * (n log q) ) [START_REF] Harvey | Faster polynomial multiplication over finite fields using cyclotomic coefficient rings[END_REF] unconditionally and (n log q log(n log q)) assuming the existence of some Linnik constant [START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF]. To simplify the notation, we assume the existence of this Linnik constant. The cost of multiplying two elements in an extension field q d is the cost of degree-d polynomial multiplications, that is (M q (d)). Let F , G ∈ [X ] of degree n and norm C. Their product has norm at most nC 2 . To compute F G, we can evaluate both F and G on some power of 2 larger than nC 2 , multiply the resulting integers (that have size n log(nC 2 )), and read the coefficients of F G directly on the output integer. Let I(m) = (m log m) denote the bit complexity of multiplying two m-bit integers [START_REF] Harvey | Integer multiplication in time O(n log n)[END_REF]. Then the bit complexity of multiplying F and G is I(n log(nC 2 )) = (n log 2 n + n log n log C + n log C log log C).

Complexity of polynomial evaluation

The evaluation of a dense degree-n polynomial F ∈ [X ] on a point α ∈ requires (n) operations in using for instance Horner scheme. If α lies in an extension ring ext of , the evaluation requires (n) operations in ext . If F has coefficients in a finite field q , this translates directly to a linear number of operations in q . Now if F has coefficients in , one must take into account the growth of the integers during the computation. Using a divide-and-conquer approach to use balanced integer multiplications, the cost of the evaluation is (I(n log C) log(n log C)) bit operations where C = max(|α|, F ∞ ). We note that this cost is quasi-linear in the worst case output size while using Horner scheme would have been quadratic.

To evaluate a sparse polynomial F ∈ [X ] on α ∈ , we compute the relevant powers of α and then perform #F multiplications and additions in . Computing each power independently yields (#F log n) operations in . Using simultaneous exponentiation [START_REF] Yao | On the Evaluation of Powers[END_REF], the cost is reduced to (log n+#F log n/ log log n) operations in . Again, this directly translates to operations in q if = q . For polynomials with integer coefficients, the growth is much more severe than in the dense case. Indeed, α n has (n log |α|) bits. This implies that the bit complexity is at least linear in n which is exponentially larger than the input size. The cost is actually not better than with dense polynomials.

Bounds on polynomial products and modular reductions

Reducing a polynomial modulo P changes its norm and sparsity. We provide bounds on these growths. They rely on the gap between the degree of P and its second degree, that is the degree of its second highest-degree monomial.

Definition 1. Let P = X n + k i=0 p i X i for k < n and p k = 0. The second degree of P is the integer k. The gap parameter

γ of P is γ = 1 n (n -k).
In particular, the second degree of P is (1 -γ)n. The parameter γ is between 0 and 1. If γ is close to 0, the polynomial actually has no gap, while γ = 1 corresponds to a binomial aX n + b. We note that given this definition, 1 γ is always upper bounded by n. Polynomials with a large gap are also known as sedimentary polynomials [START_REF] Mullen | Handbook of Finite Fields[END_REF]. A polynomial is said t-sedimentary if it is of the form X n + H where deg(H) = t. A tsedimentary polynomial is a polynomial with gap parameter (nt)/n and conversely a monic polynomial with a gap parameter γ is (1 -γ)n-sedimentary.

The norm of the product of two polynomials is classically related to their norms and degrees. This can be slightly refined using the sparsities instead of the degrees.

Lemma 2.1. Let F and G be two polynomials over . Then F G

∞ ≤ min(#F, #G) F ∞ G ∞ . Proof. Let H = k h k X k be the product of F and G. Then h k = i+ j=k f i g j . Let T = min(#F, #G). Then the sum to define h k has size of most T . Since | f i | ≤ F ∞ for all i and |g j | ≤ G ∞ for all j by definition, |h k | ≤ T F ∞ G ∞ , whence the result.
The modular reduction of polynomials has a bigger impact on the norm. It is actually related to several parameters such as the gap parameter of the divisor and the difference of the degrees. The following example shows a large increase in the norm, as well as a densification of the result.

Example 3. Let P = X 80 +7X 65 +2X 61 -8X 59 +X 56 +3 and Q = X 131 +4X 120 +8X 118 -3X 108 -3X 80 +X 71 +5X 32 . Here the gap parameter of P is γ = 3 16 , #P = 6, #Q = 7 and P ∞ = Q ∞ = 8. The polynomial Q mod P has degree 79, sparsity 53 and norm 11912.

The following proposition bounds the growth on the different parameters of the polynomial after a modular reduction. Proposition 2.2. Let Q be a sparse polynomial of degree at most n -1 + k and P a monic polynomial of degree n with #P ≥ 2. The polynomial Q mod P has at most #Q(#P -1)

k γn monomials. If Q and P are defined over , Q mod P ∞ ≤ Q ∞ (#P P ∞ ) k γn .
Proof. We analyse the growth of the norm and the sparsity while performing the euclidean division.

Instead of following the classical quadratic algorithm, we first reduce once all the monomials of Q with degree at least n to obtain a new dividend. We repeat this process until the dividend has degree less than n. Let us define the sequence (Q [i] ) i by

Q [0] = Q and Q [i+1] = (Q [i] mod X n ) + (Q [i] quo X n )(X n -P). Then Q [i] mod P = Q mod P for all i. Since deg(Q [i] quo X n ) = deg(Q [i] ) -n and deg(X n -P) ≤ (1 -γ)n, deg(Q [i+1] ) ≤ max(n -1, deg(Q [i] ) -γn), whence deg(Q [i] ) ≤ max(n -1, deg(Q) -iγn). Also, #Q [i+1] is at most #Q [i] (#P -1), thus #Q [i] ≤ #Q(#P -1) i . Finally, Q [i+1] ∞ ≤ Q [i] ∞ (1 + min(#Q [i] , #P -1) P ∞ ). Therefore, Q [i] ∞ ≤ (#P P ∞ ) i Q ∞ . Since deg(Q [i] ) ≤ n + k -1 -iγn, deg(Q [i] ) < n if i = k
γn . This implies that Q [i] = Q mod P.

Random primes and random irreducible polynomials

We collect in this section some useful results to produce random prime numbers and random irreducible polynomials over finite fields.

Proposition 2.3 ([28]

). If λ ≥ 21, there are at least 3 5 λ/ ln λ prime numbers in [λ, 2λ]. Using this proposition together with Miller-Rabin probability test, we can produce integers that are prime with good probability [START_REF] Shoup | A Computational Introduction to Number Theory and Algebra[END_REF].

Proposition 2.4.

There exists an algorithm RANDOMPRIME(λ, ε) that returns an integer q in [λ, 2λ], such that q is prime with probability at least 1 -ε. It requires (log( 1 ε ) log 2 (λ)I(log λ) log log λ) bit operations. Proposition 2.5. Let H ∈ [X ] be a nonzero polynomial of degree at most n and sparsity at most T , 0 < ε < 1 and λ = max (21, 10 3ε T ln n). With probability at least 1 -ε, RANDOMPRIME(λ, ε 2 ) returns a prime number p such that H mod X p -1 = 0.

Proof. It is sufficient, for H mod X p -1 to be nonzero, that there exist one exponent e of H that is not congruent to any other exponents e j modulo p. In other words, it is sufficient that p does not divide any of the T -1 differences δ j = e j -e.

Noting that δ j ≤ n, the number of primes in [λ, 2λ] that divide at least one δ j is at most

(T -1) ln n ln λ
. Since there exists 3 5 λ/ ln λ primes in this interval, the probability that a prime randomly chosen from it divides at least one δ j is at most ε/2. RANDOMPRIME(λ, ε/2) returns a prime in [λ, 2λ] with probability at least 1-ε/2, whence the result.

The following two propositions will be useful to either reduce integer coefficients modulo some prime number or to construct irreducible polynomials over finite fields. Proposition 2.6. Let H ∈ [X ] be a nonzero polynomial, 0 < ε < 1 and λ ≥ max (21, 10 3ε ln H ∞ ). Then with probability at least RANDOMPRIME(λ,ε 2 ) returns a prime q such that H mod q = 0. Proof. Let h i be a nonzero coefficient of H, a random prime from [λ, 2λ] divides h i with probability at most 5 3 ln H ∞ /λ ≤ ε/2. Since RANDOMPRIME(λ, ε/2) returns a prime in [λ, 2λ] with probability at least 1 -ε/2 the result follows.

Proposition 2.7 [START_REF] Shoup | A Computational Introduction to Number Theory and Algebra[END_REF]Chapter 19]). The number of irreducible monic polynomial of degree d over a field q is between q d 2d and q d d .

Proposition 2.8 ([30, Chapter 20]).

There exists an algorithm that, given a finite field q , an integer d and

0 < ε < 1, computes a degree-d polynomial in q [X ] that is irreducible with probability at least 1 -ε. It requires (log( 1 ε )d 2 M(d)(log q + log log d))
operations in q or (log( 1 ε )d 4 log q) operations in q if using only naive polynomial multiplications. Remark 2.9. Shoup [START_REF] Shoup | A Computational Introduction to Number Theory and Algebra[END_REF] presents Las Vegas algorithms for Propositions 2.4 and 2.8. We consider Monte Carlo versions of his algorithms. Also, he analyses the complexities with naive algorithms. Our complexity estimates use fast integer and polynomial arithmetic.

Evaluation for polynomial multiplication in a quotient ring

As seen earlier, the verification of polynomial multiplication mainly relies on the evaluation of the polynomial identity at a random point. In this section we present algorithms to efficiently compute the evaluation of a modular product (F G) mod P on a point α, without computing (F G) mod P. There, the modulus P is always considered as a sparse polynomial, while F and G can be either dense or sparse.

Section 3.1 describes our method in the simpler case where P is a binomial. We obtain linear-time evaluations, whether F and G are dense or sparse. Section 3.2 generalizes the method to the product of two dense polynomials modulo a sparse modulus, and Section 3.3 presents the case of a sparse modular product.

Evaluation of a product modulo a binomial

Let us first present our method to evaluate a modular product F G mod P where P = X n -1. This special case illustrates our more general method. It also has its own interest since it is used as the main tool for the verification of a product of two polynomials in Section 5, either for dense or sparse representation.

We first describe the algorithm for dense polynomials F and G.

Theorem 3.1. Let F and G be two polynomials in [X ] of degrees less than n and α ∈ . The polynomial (F G) mod X n -1 can be evaluates on α using (n) operations in .

Proof. Let H = F G and M = H mod X n -1. We denote by f i (resp. g i , h i , m i ) the coefficient of degree i of the polynomial F (resp. G, H, M ). Let also g = (g 0 , . . . , g n-1 ) T , h = (h 0 , . . . , h 2n-2 ) T and m = (m 0 , . . . , m n-1 ) T .
It is a well-known fact that considering F as fixed, the multiplication by F is a linear map described by a Toeplitz matrix. More precisely, we have h = T F g where

T F =            f 0 f 1 f 0 . . . . . . f n-1 . . . . . . f 0 f n-1 f 1 . . . . . . f n-1            . Since M = H mod X n -1, m i = h i + h i+n-1 for 0 ≤ i < n -1 and m n-1 = h n-1 . Therefore, m = C F g where C F is the circulant matrix C F =     f 0 f n-1 • • • f 1 f 1 f 0 • • • f 2 . . . . . . . . . f n-1 f n-2 • • • f 0     .
On the other hand, evaluating M on α corresponds to the inner product α n m where α n = (1, α, . . . , α n-1 ). Therefore, our aim is to compute α n C F g. The standard way to perform this evaluation corresponds to first computing m = C F g and then α n m. As noticed by Giorgi [START_REF] Giorgi | A probabilistic algorithm for verifying polynomial middle product in linear time[END_REF], the bracketing ( α n C F ) g yields a faster algorithm due to the structure of the matrix

C F . Let c = α n C F . Then c j+1 = n-1 =0 α f ( -j-1) mod n = f n-j-1 + α n-2 =0 α f ( -j) mod n . Since for j > 0 we have n-2 =0 α f ( -j) mod n = c j -α n-1 f n-j-1
, we obtain the recurrence relation

c j+1 = αc j -P(α) f n-j-1 for j ≥ 0 c 0 = F (α) (1)
where P = X n -1 and c 0 = F (α).

It is immediate that exploiting such recurrence relation for computing the evaluation of (F G) mod P leads to a complexity of (n) operations in . Indeed, once c 0 and P(α) = α n -1 are computed each other c j can be computed sequentially at cost (1).

For completeness, we provide the full description of this method in Algorithm 3.1. We can actually be more precise on the number of operations required by Algorithm 3.1. In particular when α does not lie into but in an extension ext of , we can distinguish between operations in and ext . In the next corollary, we call scalar multiplications those that are multiplications of an element of ext by an element of . The following analysis minimizes the number of non-scalar multiplications.

Algorithm 1 EVALUATIONMODULOBINOMIAL

Input: F , G ∈ [X ] with deg(F ), deg(G) < n, and α ∈ . Output: (F G mod X n -1)(α) 1: c ← F (α) 2: P α ← α n -1 3: β ← c g 0 4: for j = 1 to n -1 do 5: c ← αc -P α f n-j 6: β ← β + c g j 7: return β Corollary 3.2.
Let F and G be two polynomials in [X ] of degree less than n and α ∈ ext . The polynomial (F G) mod X n -1 can be evaluated on α using 2n -2 multiplications and 3n -2 additions in ext , and 3n -2 scalar multiplications.

Proof. We can first compute α 2 , α 3 , . . . , α n using (n -1) multiplications. Then, F (α) can be computed using (n -1) scalar multiplications and additions, and P(α) = α n -1 require one more addition. The initial value c g 0 of β requires one scalar multiplication. Then each iteration of the loop require one multiplication, two scalar multiplications and two additions. Therefore, the complete evaluation require 3n -2 additions, 2n -2 multiplications and 3n -2 scalar multiplications.

To minimize the total number of multiplications instead, we remark that one can also evaluate F using Horner's scheme with (n-2) multiplications, one scalar multiplication and (n-1) additions. Then α n has to be computed using at most 2 log n multiplications. This results in 3n-2 additions, 2n-3+2 log n multiplications and 2n scalar multiplications. The total number of multiplications (scalar or not) is a bit less.

We now turn to the analysis of the algorithm for F and G given in sparse representation.

Theorem 3.3. Let F and G be two sparsely represented polynomials in [X ] of degrees less than n and α ∈ .

The polynomial (F G) mod X n -1 can be evaluated on α using

((#F + #G) log n) operations in .
Proof. We use the same notations as in the previous proof. If the support of

G is supp(G) = { j 0 , . . . , j #G-1 } with j 0 < • • • < j #G-1 , the inner product c g is equal to #G-1 k=0 c j k g j k .
This means that only the #G entries c j 0 , . . . , c j #G-1 of c need to be computed. Applying the recurrence relation (1) as many times as necessary, we obtain the new recurrence relation

c j k+1 = α j k+1 -j k c j k -P(α) j k+1 = j k +1 α f n- for k ≥ 0 c j 0 = ((X j 0 F ) mod X n -1)(α). (2)
The initial value c j 0 can be computed using (#F log n) operations in since it needs #F exponentiations of α with exponent bounded by n. Most values of f n-are actually equal to zero since F is sparse.

A nonzero coefficient f t of F appears in the definition of c j k+1 if and only if n-j k+1 ≤ t < n-j k . Thus, each f t is used exactly once to compute all the c j k 's. Since for each summand, one needs to compute α for some < n, the total cost for computing all the sums is (#F log n) operations in . Similarly, the computation of

α j k+1 -j k c j k for all k ∈ [0, #G -2] costs (#G log n) operations in
plus #G -1 additions of (log n)-bit integers to get the exponents. As one operation in requires at least one bit operation, the integer additions that costs (#G log n) bit operations are negligible. The last remaining step is the final inner product which costs (#G) operations in , whence the result.

As in the dense case, one can be more precise on the complexity if α liesin an extension ext . In contrary to the dense case where there is more operations in than in ext , one can note that the number of operations in is negligible in the sparse case.

Corollary 3.4. Let F and G be two sparsely represented polynomials in [X ] of degrees less than n and α ∈ ext .

The polynomial (F G) mod X n -1 can be evaluated on α using log n + ((#F + #G) log n/ log log n) operations in ext plus #G -1 additions of (log n)-bit integers.

Proof. We first notice that in the sparse case the operations on α dominate the complexity. These operations are operations in ext . To improve the complexity estimates, we remark that in the sparse settings we need to compute α t for several values of t. The computation of c j 0 requires to know #F values of α t , more precisely those with t = -j 0 mod n for each nonzero coefficient f of F . To apply Equation ( 2), one needs to compute α t for t = j k+1 -j k , 1 ≤ k < #G, and for t = where f n-= 0. The value α n is also needed to compute P(α).

Finally, the inner product requires to compute α t for each nonzero g t . Altogether, one needs α t for at most 2(#F +#G) values of t, each at most n. They can be computed independently using fast exponentiation, using at most ((#F + #G) log n) multiplications, as it is done in Theorem 3.3. Actually, Yao [START_REF] Yao | On the Evaluation of Powers[END_REF] shows that these values of α t can be computed simultaneously using only log n + ((#F + #G) log n/ log log n) multiplications. Once these α t have been computed, computing c j 0 and the c j k 's by means of Equation ( 2), as well as the inner product c g, only require (#F + #G) operations.

Evaluation of a dense modular product

In this section, we extend the previous algorithm to the evaluation of a polynomial F G mod P where P is any monic sparse polynomial. We first consider the case where F and G are given in dense representation. The case where they are given is sparse representation is postponed to the next section.

The algorithm goes along the same lines as the evaluation modulo X n -1. Let F [i] = (X i F ) mod P. We can rewrite F G mod P = n-1 i=0 g i F [i] where g i is the coefficient of degree i in G. The evaluation of this equality on a point α yields the formula

(F G mod P)(α) = n-1 i=0 g i F [i] (α). (3)
To make use of this formula, we need to be able to efficiently evaluate each F [i] on α. Note that consecutive F [i] 's are bound by the recurrence relation

F [i+1] = (X F [i] ) mod P. Since deg(F [i] ) = n -1, (X F [i] ) mod P = X F [i] -f [i] n-1 P where f [i] n-1 is the coefficient of degree n -1 of F [i]
. Consequently we have the following recurrence relation

F [i+1] (α) = αF [i] (α) -f [i] n-1 P(α) for i ≥ 0 F [0] (α) = F (α) (4)
The evaluations of each F [i] on α can thus be computed iteratively from F (α), only knowing the coefficient

f [i] n-1 of F [i] for 0 < i < n -1.
We first present an algorithm to compute these coefficients. Note that we did not need such an algorithm when P = X n -1 since these coefficients were given for free as we had f [i] n-1 = f n-1-i . In the general case, the computation is based on the recurrence relation F

[i+1] = X F [i] -f [i]
n-1 P, which implies

f [i+1] k = f [i] k-1 -f [i] n-1 p k (5)
for 0 < k ≤ n -1. This allows to compute each f [i] n-1 , starting from the values of f [0] k for all k. These values are given as input since F [0] = F by definition. Note that since P is a sparse polynomial, Equation ( 5) actually reduces to an equality f

[i+1] k = f [i]
k-1 in many cases. Algorithm 2 takes this into account and only performs the required updates.

Algorithm 2 LEADINGCOEFFICIENTS

Input: Two polynomials P and F in [X ], with deg(F ) < deg(P) = n and P monic.

Output: The vector [ f [0] n-1 , f [1] n-1 , . . . , f [n-2] n-1 ], where f [i] n-1 is the coefficient of degree n-1 of F [i] = (X i F ) mod P. 1: V ← [ f n-1 , f n-2 , . . . , f 1 ] 2: for i = 0 to n -2 do 3: for k ∈ supp(P) such that i < k < n do 4: V [i + n -k] ← V [i + n -k] -p k V [i] 5: return V Lemma 3.5. Algorithm 2 is correct. It uses (n#P) operations in .
Proof. The number of operations is clear: all operations are performed at Step 4 and it is called (n#P) times. Note that the external for loop can be stopped as soon as there exists no k ∈ supp(P) such that i < k < n. In other words, i never goes beyond deg(X n -P) -1.

To show the correctness of Algorithm 2, we prove by induction that after iteration i of the external loop, the following property (i) holds:

V [ j] = f [ j]
n-1 for any j ≤ i + 1 and

V [ j] = f [i+1] n-( j-i) for j > i + 1.
Before the first iteration, (-1) holds since it reads V [ j] = f [0] n-j-1 for all j, and F = F [0] by definition. Suppose that (i -1) holds. In particular, V [ j] = f [ j] n-1 for j ≤ i. During iteration i, only

V [i + 1] to V [n -2]
can be modified so these equalities remain after that iteration. For j > i, V [ j] = f [i] n-( j-i+1) before the iteration by hypothesis. After the iteration, it becomes

V [ j] = f [i] n-( j-i+1) -p n-j+i V [i] = f [i] n-j+i-1 -p n-j+i f [i] n-1 .
Equation [START_REF] Th | Introduction to Algorithms[END_REF] shows that

V [ j] = f [i+1]
n-j+i after Step 4, and (i) holds. To conclude, after the last iteration, V [ j] = f [ j] n-1 for all j ≤ n -2 and the algorithm is correct.

We can now make use of Algorithm 2 to evaluate F G mod P on a point α. In the following algorithm, we assume that α belongs to some extension ring ext of . Our analysis distinguishes between operations in and in ext .

Algorithm 3 MODULAREVALUATION Input: P, F , G ∈ [X ] with deg(F ), deg(G) < deg(P) = n, P monic, and α ∈ ext . Output: (F G mod P)(α) 1: V ← [ f [0] n-1 , . . . , f [n-2]
n-1 ] using a call to LEADINGCOEFFICIENTS(P, F ) As before, we notice that the operations in ext are sometimes scalar multiplications, that is multiplications of an element of ext by an element of . We provide an analysis that minimizes the number of non-scalar multiplications.

2: P α ← P(α) 3: F α ← F (α) 4: β ← F α g 0 5: for i = 1 to n -1 do 6: F α ← αF α -V [i -1]P α 7: β ← β + F α g i
Corollary 3.7. Let P, F , G and α as in Algorithm 3. Then (F G) mod P can be evaluated on α using 2n -2 multiplications and (3n-5+#P) additions in ext , (3n-3+#P) scalar multiplications in ext , and (n-1)(#P-1) multiplications and additions in .

Proof. We first note that the number of operations performed by Algorithm 2 is at most (n -1)(#P -1) multiplications and additions in . In Algorithm 3, we need to evaluate both P and F on α. To minimize the number of non-scalar multiplications, we first compute α 2 , . . . , α n using n -1 multiplications in ext . We can then compute P α using #P -1 scalar multiplications and #P -1 additions, and F α using n -1 scalar multiplications and n-2 additions. Then, the initialization of β and the for loop require n-1 multiplications, 2n -1 scalar multiplications and 2n -2 additions. This results in 2n -2 multiplications in ext , (3n -3 + #P) scalar multiplications in ext , and (3n -5 + #P) additions in ext .

In a different context where the aim is specifically to compute the evaluation with no restriction to the use of polynomial arithmetic one can first compute the polynomial F G mod P and then evaluate it on α ∈ ext . Such method requires (n log n log log n) operations in for the polynomial multiplication F ×G and division by P and (n) operations in ext for the evaluation. Thus we see that if P verifies #P < log n log log n our technique is more efficient.

Evaluation of a sparse modular product

In this section, we adapt and analyse the previous algorithms for polynomials F and G given in sparse representation. Our results depend on the difference between the highest and the second highest exponents in P. Recall that the gap parameter γ is a measure of this difference, defined by 1

-γ = 1 n max{k < n : p k = 0}.
In particular, the second highest exponent with nonzero coefficient in P is (1 -γ)n. Proposition 2.2 gives a relation between the gap parameter and the sparsity of (F G) mod P. The potential growth of the sparsity induced by the reduction modulo P explains the dependency of our results on the gap parameter.

As G is sparse, Equation ( 3) becomes

(F G mod P)(α) = i∈supp(G) g i F [i] (α), (6)
with the same notations as in the previous section. The recurrence relation F

[i+1] = X F [i] -f [i] n-1 P still holds, hence F [i+1] (α) = αF [i] (α) -f [i]
n-1 P(α) too. The goal now is to efficiently compute F [i] (α) for all i ∈ supp(G) only, not for all indices i. When γ is not close to zero, there are actually few indices i such that f [i] n-1 = 0. In fact, the number of such indices depends on #F, #P and γ. Let I = {i 1 , . . . , i t } denote this set of indices. We will prove in Lemma 3.8 that this set is of size (#F #P 1/γ-1 ). We decide to first provide some arguments and an explicit algorithm to prove this claim.

An important remark is that for any 0 ≤ j < n -1, in particular those verifying j ∈ supp(G), if we assume i to be the largest index in I not larger than j, then Equation (5) implies

F [ j] (α) = α j-i F [i] (α). (7)
Therefore, the recurrence relation given in (4) becomes

F [i k+1 ] (α) = α i k+1 -i k -1 (αF [i k ] (α) -f [i k ] n-1 P(α)) for k ≥ 0 F [i 1 ] (α) = α i 1 F [0] (α) (8)
To efficiently use Equations ( 7) and ( 8) to perform the evaluation, we need to provide a sparse variant of Algorithm 2. It computes a sparse representation of the vector

V = [ f [0] n-1 , . . . , f [n-2] n-1 ]
, that is the sparse vector {(i, f [i] n-1 ) : f [i] n-1 = 0}. The idea of Algorithm 4 is to mimic Algorithm 2 in the sparse settings. For simplicity of the presentation, we first consider to store V as a sparse vector as it is sufficient to our needs for proving our claims on the size of the set I. We will show in Corollary 3.9 that we must require another structure to minimize the complexity attached to data management.

The initial nonzero values in V are the nonzero coefficients of

F = F [0] , with V [i] = f n-1-i if n -i -1 ∈ supp(F ).
Let now consider the external loop in Algorithm 2. Iteration i does not require any operation if

f [i] n-1 = 0 since Equation (5) reduces to f [i+1] k = f [i]
k-1 in that case. Therefore, we must loop over indices i such that f [i] n-1 is nonzero. For such an index i, the same updates as in Step 4 of Algorithm 2 are required. For k ∈ supp(P), i < k < n, we must perform the update

V [i + n -k] ← V [i + n -k] -p k f [i] n-1 . If V [i + n -k]
is already nonzero, its value is already stored in V and must be updated. Otherwise, the new value -p k f [i] n-1 must be inserted in V with index i + nk.

It remains to be able to only loop over the indices i such that f [i] n-1 = 0. Let us assume that iteration i has been performed since f [i] n-1 = 0. The proof of Lemma 3.5 shows that

V [i + 1] then contains f [i+1]
n-1 . Therefore in the sparse setting, we know that iteration i + 1 has to be performed if, and only if, V [i + 1] = 0. More generally, the next index to be considered is the index of the next nonzero entry of V after V [i]. Algorithm 4 below uses such method for computing all the indices i such that f [i] n-1 is nonzero.

Algorithm 4 SPARSELEADINGCOEFFICIENTS

Input: P, F ∈ [X ] with deg(F ) < deg(P) = n, and P monic Output: The list {(i, f [i] n-1 ) : 0 ≤ i < n -1, f [i] n-1 = 0}, sorted by increasing values of i. 1: L ← empty list 2: V ← {(i, f n-1-i ) : n -1 -i ∈ supp(F )} (sparse vector) 3: while V is not empty do 4: (i, v) ← extract the element of minimal index from V 5: if v = 0 then 6: Add (i, v) to the list L 7:
for k ∈ supp(P) such that i < k < n do 8:

V [i + n -k] ← V [i + n -k] -p k v
9: return L Lemma 3.8. Algorithm 4 is correct. If the polynomial P has a gap parameter γ, the algorithm uses (#F #P 1/γ-1 ) operations in and additions of (log n)-bits integers. In particular, there are at most #F #P 1/γ-1 indices i such that f [i] n-1 = 0.

Proof. As explained above, Algorithm 4 is an adaptation of Algorithm 2 to the sparse settings that only computes those f [i] n-1 that are nonzero, using Equations ( 7) and ( 8) in place of Equation ( 4). Instead of considering all the F i [n -1] one after the other it only considers those which are not zero. Let us call "iteration i" the iteration in the while loop that extract a pair (i, v) from V . To prove the correctness, we prove by induction that at the end of iteration i,

V = {( j, f [i+1] n-j+i ) : j > i, f [i+1] n-j+i = 0} and L = {( j, f [ j] n-1 ) : j ≤ i, f [ j] n-1 = 0}.
Before the loop ("iteration -1") the property holds, that is L is empty and V contains exactly the pairs ( j, f [0] n-j-1 ) such that f [0] n-j-1 = 0. Let us assume that the property holds at then end of iteration , and let (i, v) be the pair extracted at the next iteration. We first prove that f [i] n-1 = v and f [ j] n-1 = 0 for < j < i. By minimality of i and induction hypothesis, f [ +1] n-j+ = 0 for < j < i at the end of iteration . In particular, f [ +1] n-1 = 0. By Equation ( 5),

f [ +2] n-j+ +1 = f [ +1] n-j+ -f [ +1]
n-1 p n-j+ +1 = 0. And an easy recurrence shows that f [ j] n-1 = 0 for < j < i. Now this implies that f [i] n-

1 = f [i-1] n-2 = • • • = f [ +1]
n-i+ . Yet by induction hypothesis, at the end of iteration , V contains ( j, f [ +1] n-j+i

) if f [ +1] n-j+i = 0. Therefore, if f [i] n-1 is nonzero, f [ +1]
n-i+ is nonzero too and V contains the pair (i, f [ +1] n-i+ ) = (i, f [i] n-1 ). In other words, the value v extracted from V is indeed equal to f [i] n-1 and the property holds for L after iteration i.

Now with the same argument,

f [i] n-1-j+i = f [ +1]
n-j+ for < j < i. Right before iteration i, V contains then the pairs ( j, f [i] n-1-j+i ) for f [i] n-1-j+i = 0. After iteration i, such pairs are replaced by ( j,

f [i] n-1-j+i -p n-j+i f [i] n-1 ), that is ( j, f [i+1]
n-j+i ) by Equation ( 5). And if

f [i] n-1-j+i = 0 but p n-j+i = 0, a new pair ( j, -p n-j+i f [i] n-1 ) = ( j, f [i] n-j+i
) is inserted into V . Therefore, the property holds for V too after iteration i.

The second point is to count the number of operations. Since the while loop stops when V is empty, the number of operations in is at most twice the number of pairs that are inserted into V during the algorithm and the same number of additions in are performed as the index of each pair is computed by two additions of number at most n. We will classify the pairs by generations. Initially, V contains #F pairs which form generation 0. New pairs can be inserted into V when a pair (i, v) is extracted. If (i, v) is a pair of generation t, the new pairs inserted at iteration i belong to generation t + 1. At any iteration, at most #P -1 pairs are inserted into V . Therefore, there are at most #F (#P -1) pairs of generation 1, #F (#P -1) 2 pairs of generation 2, and in general #F (#P -1) t pairs of generation t. Now we need to bound the number of generations. Note the pairs of generation 0 have an index i between 0 and n -1. But at generation 1, the new pairs have index (i + nk) for some k ∈ supp(P), k < n. There comes the gap into account: If P has gap parameter γ, the largest exponent less than n in supp(P) is (1 -γ)n by definition. Therefore, at generation 1, all pairs have an index at least i + n -(1 -γ)n ≥ γn. At generation 2, all pairs have then an index at least 2γn. At generation t, all pairs have an index at least tγn. Since indices are bounded by n -1, there cannot be any pair of generation t if tγn ≥ n. In other words, the largest possible generation is t = 1/γ -1 . Altogether, the total number of pairs inserted into V is at most

1/γ-1 t=0 #F (#P -1) t = #F (#P -1) 1/γ -1 #P -2 if #P > 2
, and is at most 1/γ #F if #P = 2. To simplify the exposition, we bound both of them by #F #P 1/γ-1 in the following. Note that of course, this number is also a bound on the number of pairs that are extracted from V during the algorithm. This has two consequences. First, the number of extracted pairs is a bound on the size of the list at then end of the algorithm. Therefore there are at most (#F #P 1/γ-1 ) nonzero values f [i] n-1 . Second, this number also bounds the total number of executions of Step 8, that is the total number of operations. Corollary 3.9. All operations of INSERTION, REMOVAL, MINIMUM and SEARCH of pairs (i, ν) in the data structure V within Algorithm 4 can be done with (#F #P 1/γ-1 log log n) bit operations.

Proof. By definition the size of the sparse vector V is at most n. Therefore, using a data structure for V of type van Emde Boas tree with a universe of size n, ensures that any requested operations can be done with (log log n) bit operations, see [START_REF] Th | Introduction to Algorithms[END_REF]Chapter 20].

Remark 3.10. As the bit-complexity of all the operations in of Algorithm 4 is (#F #P 1/γ-1 log n) the cost driven by the data structure of V is negligible.

Our algorithm to compute the evaluation of the polynomial F G mod P on some point α, when F and G are given in sparse representation, relies on Equations ( 6), ( 8) and [START_REF] Freivalds | Fast probabilistic algorithms[END_REF]. More precisely, we first compute each F [i] (α) for indices i such that f [i] n-1 = 0 by means of Equation [START_REF] Zur Gathen | Modern Computer Algebra[END_REF]. From these values, we get each F [ j] (α) for j ∈ supp(G) by means of Equation [START_REF] Freivalds | Fast probabilistic algorithms[END_REF]. Finally, we deduce (F G mod P)(α) using Equation [START_REF] Demillo | A probabilistic remark on algebraic program testing[END_REF].

In Algorithm 5, all these computations are intertwined. The idea is to loop over all indices j such that either f [ j] n-1 = 0 or j ∈ supp(G). If f [ j] n-1 = 0, we update the value F [ j] (α) using Equation ( 8). If j ∈ supp(G), we accumulate partial evaluations of (F G mod P)(α) using Equations ( 6) and [START_REF] Freivalds | Fast probabilistic algorithms[END_REF].

(F G mod P)(α) 1: V ← {(i, f [i] n-1 ) : 1 ≤ i < n -1, f [i] n-1 = 0}, using a call to SPARSELEADINGCOEFFICIENTS(P, F ) 2: if f [0] n-1 = 0 then insert (0, 0) in V 3: P α ← P(α) 4: F α ← F (α) 5: β ← F α g 0 β ← 0 if 0 / ∈ supp(G) 6: i ← 0 7: for j ∈ supp(V ) ∪ supp(G) \ {0}, by increasing order do 8: if j ∈ supp(V ) then 9: F α ← α j-i-1 (αF α -V [i]P α )
Equation ( 8)

10: i ← j 11: if j ∈ supp(G) then 12:
β ← β + α j-i F α g j Equations ( 6) and ( 7)

13: return β Theorem 3.11. Algorithm 5 is correct. It uses (#F #P 1 γ -1 ) operations in , ((#F #P 1 γ -1 + #G) log n) operations in ext .
Proof. We prove that at the end of iteration j, F α = F [ j] (α) if j ∈ supp(F ) and β = i g i F [i] (α) where the sum ranges over indices i ∈ supp(G) ∩ {0, . . . , j}. The property is satisfied after iteration 0 (before entering the loop) since F α = F [0] (α) and β = F α g 0 = g 0 F [0] (α). Let us assume that the property holds before entering iteration j. Index i denotes the previous index that belongs to supp(F ). Therefore, if j ∈ supp(F ), Equation [START_REF] Zur Gathen | Modern Computer Algebra[END_REF] ensures that F α has the right value after iteration j since V [i] = f [i] n-1 . And Equations ( 6) and [START_REF] Freivalds | Fast probabilistic algorithms[END_REF] justify that β also has the right value if j ∈ supp(G).

The evaluations P(α) and F (α) require (#P log n) and (#F log n) operations in ext respectively. Steps 9 and 12 each require (log n) operations in ext to compute powers of α and (1) additions with integers of size (log n) to compute the appropriate exponent. These steps are executed (#V + #G) times. Since #V = (#F #P 1/γ-1 ) this gives a total of ((#F #P

1 γ -1 + #G) log n) operations in ext plus ((#F #P 1 γ -1 + #G) log n) bit
operations for the integer additions. Since we can easily assume that one operation in ext will cost more than one bit operation, the latter complexity is dominated by the computation part in ext . The cost of Step 1 is given by Lemma 3.8

. We can still use van Edme Boas tree to iterate over the union of the supports of V and G at Step 7 with a total of ((#F #P 1 γ -1 + #G) log log n) bit operations which is less than the number bit operations required by the additions in and thus negligible.

Obviously, since polynomial multiplication over integral domains is commutative, the roles of F and G can be exchanged in Algorithm 5. In particular if #G < #F , this exchange decreases the complexity in Theorem 3.11. In other words, the statement remains valid if #F is replaced by min(#F, #G) and #G by max(#F, #G). The same remark applies to subsequent results. Remark 3.12. As in Corollary 3.4, we can decrease the number of operations over ext by using simultaneous exponentiation on α. This results in log n + ((#F #P 1/γ-1 + #G) log n/ log log n) operations in ext .

If the gap parameter γ is close to 1 n , the polynomial F G mod P is in general a dense polynomial even if F G is sparse and the dense modular evaluation will be more appropriate. On the contrary, F G mod P remains sparse if γ is close to 1, in particular if γ ≥ 1 2 .

Remark 3.13. If γ ≥ 1 2 , the evaluation requires ((#F #P + #G) log n) operations in ext .

Remark 3.14. The factor #F #P 1 γ -1 +#G in the complexity may be larger than the actual sparsity of F G mod P. For instance, the sparsity can be 0 if P divides F G. Yet, it is smaller than the general bound #F #G(#P -1)

1 γ
given by Proposition 2.2. Thus in general it is more efficient to use our method than to directly evaluate F G mod P if the polynomial is known.

Verification of polynomial modular product

This section is devoted to the verification of polynomial modular product. That is, given F , G, H and P, such that deg(F ), deg(G), deg(H) < deg(P) = n, we want to test whether H = F G mod P. The idea is classical, that is to evaluate the identity at a random point. Contrary to the more straightforward verification of polynomial multiplication, we cannot do such evaluation directly since we do not know the polynomial Q = (F G -(F G mod P))/P. As seen in the previous section, we provide new algorithms to do such evaluation efficiently without reverting to the computation of Q. We remind that P is always taken monic. Note that this is a mild assumption since (F G) mod P = (F G) mod (λP) for any invertible constant λ.

In the following, all algorithms are analysed both when the polynomials F , G and H are dense and when they are sparse. On the other hand, P is always considered as a sparse polynomial. We shall recall that γ denotes the gap parameter of P, defined by 1 -γ = deg(P -X n ), and it serves to control the densification of the modular reduction.

We first begin in Section 4.1 with an abstract case where the polynomials are defined over an integral domain. There, we analyse the algorithms by counting the number of ring operations. In Sections 4.2 and 4.3 we discuss some adaptations of the algorithm to the case of integers and small finite fields in order to provide finer analysis in the bit complexity model.

Modular product verification in [X ]

Algorithm 6 depicted below is straightforward from Theorems 3.6 or 3.11. We mainly provide his description to serve as a starting point for its adaptations in the next sections. The algorithm covers both the dense and the sparse case. The only difference is at Step 1.

Algorithm 6 MODULARVERIFICATION

Input: F , G, H and P ∈ [X ], P monic of degree n and F , G and H of degrees < n ; 0 < ε < 1. Output: True if H = F G mod P, False with probability at least 1 -ε otherwise.

((#F #P 1 γ -1 + #G + #H) log n) operations in . Proof.
Step 1 dismisses a trivial mistake if the polynomials are sparse. If H = (F G) mod P, H(α) = (F G mod P)(α) for any α and the algorithm always returns True. Otherwise, let ∆ = H -(F G) mod P. Then ∆ has degree < n, hence has at most n -1 roots since it is nonzero. Therefore, the probability that α, randomly chosen in , is a root of ∆ is at most (n -1)/ 1 ε (n -1) = ε. The algorithm returns True in that case with probability at most ε.

The complexity is given by the cost of a single modular product evaluation that is stated in Theorem 3.6 for the dense case and in Theorem 3.11 for the sparse case.

If

is not large enough, the algorithm fails and it is customary to revert to an extension ring ext to perform the evaluation in a larger set. Using Theorems 3.6 and 3.11, we get the following extension when the polynomials are evaluated on a random point of ext rather than . In the dense case, Algorithm 6 uses an optimal number of operations in as soon as #P is constant.

Corollary 4.2. Let be an integral domain with less than

It is always faster than a modular product when #P n < M(n) that is when #P < log(n) log log(n) for a general ring . In the sparse case, Theorem 4.1 is not linear in the input size. Indeed, #P is raised to a potentially large power 1 γ -1 and more importantly there is a factor log n in the number of operations in while the input has only (#F + #G + #H) elements of . Nevertheless, the efficiency of verification has to be compared with the cost of computing F G mod P. We assume the latter to be done with a sparse multiplication followed by a sparse division with P. This hypothesis seems reasonable as no work have been done to optimize such operation yet. Letting aside the division, the number of operations in for sparse multiplication could be either (#F #G) with naive approach or ˜ (#F + #G + #(F G)) using [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF]. Assuming #P to be constant, our verification has a complexity of ((#F + #G + #H) log n) which is always faster when #(F G) = o(#F #G/ log n). If we assume that #(F G) = (#F #G), our verification will be faster at least when n = 2 (#F +#G) and #P constant. Depending on the cost of the division, our algorithm could be faster in more cases.

Of course, these conditions are not very restrictive. We use Algorithm 6 in Section 5 to verify classical polynomial multiplication, where P will be a binomial of degree either logarithmic in the sparsity or polynomial in the input degree.

Yet the efficiency of Algorithm 6 depends heavily on the integral domain . Indeed the complexity of polynomial multiplication in [X ] can be faster than (n log n log log n) operations in [START_REF] Harvey | Faster polynomial multiplication over finite fields using cyclotomic coefficient rings[END_REF][START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF]. Furthermore, if is small, one operation in ext corresponds to a non-constant number of operations in . In the following sections we consider polynomials over the integers or finite fields and we provide thorough analyses together with adapted versions when necessary.

Modular product verification in [X ]

If the polynomials are defined over , there is no difficulty with the size of in Algorithm 6. However we must prevent the integers growth during the evaluation. It is very classical to choose a random prime q and to map the whole computation into q . To do so, we must ensure two properties on the prime q. First, q must be large enough to use the algorithm, that is at least 1 ε (n -1). Second, if H = (F G) mod P, we need this inequality to hold modulo q as well. For this second property, we define ∆ = H -(F G) mod P. To ensure that ∆ does not vanish modulo q, we need that at least one coefficient of ∆ is nonzero modulo q. We then need to bound its coefficients to assess the latter fact.

Proposition 4.3. The coefficients of ∆ are bounded by H

∞ + min(#F, #G) F ∞ G ∞ (#P P ∞ ) 1 γ .
Proof. The coefficient of ∆ are bounded by H ∞ + F G mod P ∞ . The bound follows from Proposition 2.2, with

Q = F G and Q ∞ ≤ min(#F, #G) F ∞ G ∞ by Lemma 2.1.
Using this bound and Proposition 2.6 we can determine an appropriate prime q to adapt the Algorithm 6 to the integer case. This is done in the Algorithm MODULARVERIFICATIONOVERZ below.

Algorithm 7 MODULARVERIFICATIONOVERZ

Input: F , G, H and P ∈ [X ], P monic of degree n and F , G and H of degrees < n ; 0 < ε < 1. Output: True if H = F G mod P, False with probability at least 1 -ε otherwise.

1: ∆ ∞ ← H ∞ + min(#F, #G) F ∞ G ∞ (#P P ∞ ) 1 γ 2: q ← RANDOMPRIME(λ, ε
2 ) where λ = max(21, 2 ε n, 20 3ε ln ∆ ∞ ) 3: (F q , G q , H q , P q ) ← (F mod q, G mod q, H mod q, P mod q) 4: return MODULARVERIFICATION(F q , G q , H q , P q , ε 2 )

Theorem 4.4. Algorithm 7 is correct. If C = max( P ∞ , F ∞ , G ∞ , H ∞ ) and T = max(#F, #G, #H), the algorithm requires (log 2 ( n ε log C) log log( n ε log C) log 1 ε I(log( n ε log C))
) bit operations to get a prime number, plus Proof. To ensure that MODULARVERIFICATION works properly, we need q to be at least 2 ε (n -1). This is the case since λ ≥ 2 ε n. The algorithm always returns the correct answer when H = (F G) mod P. Otherwise, it may incorrectly return True in two cases: Either H q = (F q G q ) mod P q while the equality does not hold over , or MODULARVERIFICATION incorrectly returns True. Both situations occur with probability at most ε 2 . Indeed, by Proposition 4.3, ∆ ∞ is always a bound on ∆ ∞ where ∆ = H -(F G) mod P. Therefore, Proposition 2.6 shows that with probability at least ε 2 , the number q chosen at Step 2 is a prime number such that ∆ mod q = 0. The error probability of Algorithm 7 is thus at most ε.

• ((#P n + n log C log( n ε log C) )I(log( n ε log C))) bit operations if F , G
Let us now analyse the complexity of the algorithm. As a first step, we shall express q in terms of the input size.

Since #P, #F , #G ≤ n, ∆ ∞ = (n 1+ 1 γ C 2+ 1 γ ). Thus, ln ∆ ∞ = ( 1 γ (log n+log C)) = (n(log n+log C)) since 1
γ ≤ n. This implies q = ( n ε (log n + log C)) and log q = (log( n ε log C)). By Proposition 2.4, Step 2 costs (log 1 ε log 2 q log log qI(log q)) bit operations, that is

log 1 ε log 2 ( n ε log C) log log( n ε log C)I(log( n ε log C)) . ( 9
)
Step 3 requires (n log C log q I(log q)) bit operations in the dense case, and ((T + #P) log C log q I(log q)) bit operations in the sparse case. By Theorem 4.4, Step 4 requires (#P nI(log q)) bit operations in the dense case and (T #P 1 γ -1 log nI(log q)) bit operations in the sparse case. Adding the complexities of all these steps leads to the claimed bit complexity. Remark 4.5. In most cases, the cost of finding a prime number is negligible in comparison to the rest of the algorithm. In the dense case, it is negligible as long as ε = 1/n (1) . In the sparse case, it is negligible when the degree n is not too large compared to the other input parameters. More precisely, this is the case when n ε = ((T + #P) log C) (1) . When computing a multiplication followed by a modular reduction with polynomials in [X ], the size of the coefficients can grow significantly as shown by the bound on F G mod P ∞ given in the proof of Proposition 4.3. At the opposite, our verification algorithm is done with bounded integers of bit length (log( n ε log C)). This is logarithmic in the input size in dense representation and linear in the sparse one. Our verification therefore avoids paying the coefficient growth, contrary to the direct computation. Taking this growth into account to compare our verification algorithm with the computation seems hard. We only detail the cases where our algorithm is already faster even without considering the coefficient growth. We shall mention that for sparse polynomial, #(F G mod P) might be smaller that #H. In our analysis, we assume for simplicity that both have approximately the same size. (ii) when the polynomials are sparse and n ε = ((T + #P) log C) (1) .

Proof. We assume ε = 1/n (1) . In particular, log n ε = (log n). To simplify the analysis, we place ourselves in the case of a negligible cost for finding the prime q, as described in Remark 4.5. In the sparse case, this implies that n ε must be polynomial in (T + #P) log C. Therefore log n < min(T, #P) and I(log(n log C)) = I(log log C). This makes our verification faster than computing the modular product since the latter requires at least #(F G mod P) = (T 2 #P

Modular product verification in q [X ]

The situation over a finite field q is different since there is no growth to prevent. When q is large enough, Theorem 4.1 applies directly. Otherwise, one can revert to computing in a sufficiently large extension field of q , where Corollary 4.2 can be applied. We first give the precise complexity bounds for these two cases. Corollary 4.7. Let F , G, H and P ∈ q [X ] as in Algorithm 6. One can test whether H = (F G) mod P using Algorithm 6, with (log 1 ε (log q n ε ) 2 M(log q n ε )(log q+log log q n ε )) operations in q to get an irreducible polynomial of degree (log q n ε ) , plus

• (n#P + nM(log q n ε )) operations in q if F , G and H are dense, or

• (T #P 1 γ -1 log nM(log q n ε )) operations in q if F
, G and H are sparse with at most T nonzero monomials.

Proof. Let us assume that q < 1 ε (n -1) otherwise Theorem 4.1 applies straightforwardly. In that case, Corollary 4.2 requires to choose a random point in an extension q d of q with at least 1 ε (n -1) elements. More precisely, we use Proposition 2.8 to produce with probability 1 -ε 2 an irreducible polynomial of degree d over q , where d is the smallest integer such that q d ≥ 2 ε (n -1). The algorithm may be incorrect if either the polynomial used to defined q d fails to be irreducible, or if the Algorithm 6 fails. If we choose α at random in q d , the error probability of Algorithm 6 is at most ε 2 . This gives a total probability of error of at most ε. By definition, the degree of the extension is d = (log q n ε ). The cost of generating the irreducible polynomial of degree d is (log 1 ε d 2 M(d)(log q + log d)) by Proposition 2.8. Using Corollary 4.2 and the fact that an operation in q d costs M(d) operations in q , we obtain the claimed costs. Remark 4.8. If ε = 1/n (1) , the cost of getting an irreducible polynomial is negligible in the dense case. Then the algorithm requires (#P n + nM(log q n)) operations in q . If we add the degree constraint log n = o(T ), the cost of getting an irreducible polynomials is also negligible in the sparse case and the algorithm requires

(T #P 1 γ -1 log nM(log q n)) operations in q .
As #(F G mod P) is bounded by T 2 #P 1 γ and computing F G mod P requires at least one operation in q for each monomial, this remark gives directly a case where the verification is faster than the modular product in general. Moreover, naive algorithms can be used to perform products in the extension of q . Remark 4.9. When ε = 1/n (1) and n = T (1) , Algorithm 6 in the sparse case is in general faster than the modular multiplication and requires ˜ (T #P 1 γ -1 ) bit operations if q < n ε .

In the dense case, we can see from Remark 4.8 that the verification complexity might in fact be larger than the cost of computing the modular product F G mod P. Indeed, assuming M q (n) = (n log q(log n+log log q)) bit operations [START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF], we have M q (log q n ε ) = (log n ε (log log n ε +log log q)). While the cost of computing F G mod P uses M q (n) bit operations, our verification requires (#P n log q log log q + n log n ε (log log n ε + log log q)) bit operations. When #P is not a constant, the latter is always larger. The following remark precise when we can expect a positive result. Remark 4.10. Assuming #P to be constant and ε = 1/n (1) , Algorithm 6 in the dense case with = q is asymptotically faster than the modular multiplication when (i) log n ε < q < n ε , since modular multiplication costs (n log q log n) bit operations while verification, which does need an extension, is (n log n ε log log n ε ).

(ii) n ε < q < 2 n ε , since modular multiplication costs (n log q log n) bit operations while verification, which does not use an extension, is (n log q log log q); If the field is very large q > 2 n ε , Algorithm 6 is asymptotically as fast as the modular multiplication. The dominant factor in both complexity is (n log q log log q). We shall mention that the verification cost in (i) of Remark 4.10 assumes the use of fast multiplication of polynomials in order to check fast multiplication of polynomial of degree (n). Even though this dependency is not a problem in theory it might not be satisfactory in practice. One solution would be to use a naive polynomial multiplication for the extension field arithmetic but this further tightens the superiority of the verification.

Remark 4.11. Assuming that extension field arithmetic is done naively using quadratic polynomial multiplication, Algorithm 6 remains faster than modular multiplication only when n 1/3 < q in the dense case.

We now propose an novel method that enables us to improve all the dense cases where an extension field is necessary, while not relying on any polynomial arithmetic. More precisely, we show that fast verification does exist when q < log n, which is of great interest for the field 2 . It is based on the evaluation of polynomials on matrices rather than scalars, combined with Freivalds algorithm for verifying matrix multiplication [START_REF] Freivalds | Fast probabilistic algorithms[END_REF].

Indeed, choosing α from an extension field inherently leads to depend on polynomial multiplication. Instead of picking a random point that is probably not a root of ∆ = H -(F G) mod P when ∆ = 0, we pick a polynomial R ∈ q [X ] of degree k < n that is probably not a divisor of ∆ = 0. To test whether R divides ∆, we evaluate ∆ on the companion matrix C R of R, defined by

C R =       0 0 • • • 0 -r 0 1 0 • • • 0 -r 1 0 1 • • • 0 -r 2 . . . . . . . . . . . . . . . 0 0 • • • 1 -r k      
where R = k i=0 r i X i . This strategy relies on the fact that R is the minimal polynomial of its companion matrix. Therefore, R(C R ) = 0 and any polynomial ∆ such that ∆(C R ) = 0 must be a multiple of R. In other words, R divides ∆ if and only if ∆(C R ) = 0. We will show that taking R irreducible over q of degree k = (log n) makes this approach faster then the one using extension field when ε is constant. Furthermore, it will extend the possibility to have fast verification for any fields, whatever the size of the polynomials.

To check whether ∆(C R ) = 0, we need to evaluate H and (F G) mod P on C R , and to verify that the evaluations match. Of course, one cannot directly evaluate those polynomials on C R as it would cost (nk ω ) operations in q for the dense case, where ω < 2.3729 is the best exponent for matrix multiplication [START_REF] Gall | Powers of tensors and fast matrix multiplication[END_REF]. Since k = (log n), this would not give any improvement to Remark 4.10.

Instead, we rely on the so-called Freivald's technique to verify matrix multiplication [START_REF] Freivalds | Fast probabilistic algorithms[END_REF]. The idea is that the matrix product C = A × B ∈ k×k can be verified by asserting that uC = (uA) × B for a random vector u ∈ {0, 1} n with a probability of error of 1/2. To assert that two polynomials evaluations on the matrix C R match, it is sufficient to verify that their projection by the vector u are equal. Given a degree-n polynomials H ∈ q [X ], one can compute uH(C R ) in (nk) operation in q using Horner evaluation:

uH(C R ) = u n i=0 h i C R i = n i=1 h i uC R i-1 C R + uh 0 . (10)
Since matrix-vector product with C R only costs (k) operations in q , and Horner procedure only uses n of those matrix-vector products, the cost is clear.

Remark 4.12. It is sufficient to replace the evaluation of F (α) and P(α) by uF (C R ) and uP(C R ) in Algorithm 3 (MODULAREVALUATION) to reach a complexity of (n(#P + deg(R))) operations in q for computing u(F G mod P)(C R ) in the dense case. More informally, it is sufficient to say that any of the operations in ext have now the cost of one matrix-vector product with C R .

Theorem 4.13. Let F , G, H and P ∈ q [X ], as in Algorithm 6. We can check whether H = F G mod P in (#P n + n log q n log 1 ε ) operations in q with a probability of error at most ε if H = F G.

Proof. Let 0 < ε 1 < 1 4 be a fixed probability. The algorithm needs two steps. First it computes with probability at least 1 -1 ε 1 an irreducible polynomial R of degree d = log q 2n ε 1 using Proposition 2.8. Second, it computes uH(C R ) and u(F G mod P)(C R ) for some random vector u ∈ {0, 1} d . If both evaluations are distinct, the algorithm returns False. Otherwise, it repeats (log 1 ε ) these two steps until one of the repetition fails. If this is the case it return false, otherwise the algorithm return true.

If H = (F G) mod P, the algorithm always returns True. Let us assume that H = (F G) mod P, and let ∆ = H -(F G) mod P. For the algorithm to return True, each repetition must ensure that uH

(C R ) = u(F G mod P)(C R ). This may happen if either R divides ∆, whence H(C R ) = (F G mod P)(C R ), or R does not divide ∆ but uH(C R ) = u(F G mod P)(C R ).
Since there are at least q d /2d irreducible polynomials of degree d in q by Proposition 2.7 and at most n/d of them divide ∆, the probability that R divides ∆ is at most 2n/q d ≤ ε 1 provided R is irreducible. Taking into account the probability that R is not irreducible, the probability that R divides ∆ is at most 2ε 1 . Then, using Freivalds standard argument, if R does not divide ∆, the probability u∆(C R ) = 0 is at most 1 2 . Altogether, the probability that one iteration returns True is at most 1 2 + 2ε 1 < 1. Therefore, the probability that log 1 ε / log( 1 2 + 2ε 1 ) independent iterations all return True is at most ε. Let us now analyse the complexity of the algorithm. Since ε 1 is a constant, the second step uses (#P n + n log q n) operations in q using Remark 4.12. The first step is negligible, even if naive polynomial arithmetic is used. Note that in this complexity, #P n is the cost of Algorithm 2 (LEADINGCOEFFICIENTS). Since it is deterministic and only depends on P and F , it can be called only once rather than at each iteration.

We then get the complexity (#P n + n log q n log 1 ε ).

Remark 4.14. Note that compared to using evaluation at α in an extension field, no operation depends on ε. If ε is fixed, the new method replaces a factor M(log q n) in the complexity by log q n. Moreover our new approach requires only simple computations: additions of vectors, multiplication of a vector by a scalar and matrix-vector product with a companion matrix. Furthermore, when #P and ε are constants, the verification is always faster than the modular multiplication, whatever the size of q.

This new method still requires some polynomial arithmetic even if only naive polynomial multiplication is used. This is because the algorithm called to provide the degree-d polynomial R relies on polynomial products and GCDs to ensure that R is probably irreducible. In order to remove the dependency to polynomial arithmetic, we can just choose a random monic degree-d polynomial R and compute the evaluation on C R even if R is not irreducible. This implies to take several random polynomials R to reach the target probability ε.

Corollary 4.15. Let F , G, H and P ∈ q [X ], as in Algorithm 6. Without using any polynomial multiplication we can check whether H = F G mod P in (#P n + n(log q n) 2 log 1 ε ) operations in q with a probability of error at most ε if H = F G.

Proof. In the proof of Theorem 4.13, we replace one evaluation on C R with R irreducible with probability at least 1 -ε 1 by few evaluations on several C R with R random monic polynomial of degree d. As the probability of a random monic polynomial R to be irreducible is at least 1 2d by Proposition 2.7, we need to generate (d log 1 ε 1 ) random polynomials R to reach a probability at least 1 -ε 1 that at least one of them is irreducible. Thus the evaluation part of the algorithm is repeated (d) = (log q n) times since ε 1 is constant.

Even if this new approach does not improve the complexity from evaluation at α in an extension field using naive polynomial multiplication, it allows to remove completely the dependency to any polynomial multiplication algorithm While this result might not being seen useful as first sight, it will be used in Section 5.1 to provide efficient verification for polynomial multiplication. Indeed, in that case we will need to use verification with P being of degree smaller than the input degree. This new method using companion matrix also works in the sparse case. Indeed, any power α t in Algorithm 5 (SPARSEMODULAREVALUATION) are now replaced with C t R . However, only few powers C t R with 1 < t < n are relevant and we cannot compute all of them as in the dense case. This implies that computing u(F G mod P)(C R ) instead of (F G mod P)(C R ) is useless in that case. Indeed, using fast exponentiation together with the structure of the powers of companion matrices [START_REF] Gries | Computing fibonacci numbers (and similarly defined functions) in log time[END_REF] already yield a complexity of ((#F #P 1 γ -1 + #G) log n log 2 q n) operations in q , and we cannot hope to lower this down by some random vector projection. In that case, using Freivald technique is useless and we have a better probability of success. Choosing (log n ε log 1 ε ) polynomials R at random, at least one of them is irreducible and does not divide ∆ = H -F G mod P with probability 1 -ε. This leads to an algorithm which does not use any polynomial product in the sparse case too. Even though it is asymptotically not as fast as the verification in an extension field where naive polynomial arithmetic is used, it is still quasi-linear. Corollary 4.16. Let P ∈ q [X ] be monic of degree n and F , G, H ∈ q [X ] of degree less than n and sparsity at most T , and 0 < ε < 1. Using a direct evaluation on a companion matrix, we can check whether H = F G mod P with a probability of error at most

ε if H = F G in (T #P 1 γ -1 log n(log q n ε ) 3 log 1 ε
) operations in q , without performing any polynomial product.

Polynomial product verification

In this section we study the simpler problem of verifying a classical polynomial multiplication. Given three polynomials F , G and H ∈ [X ] of respective degrees n, n and 2n, the classical idea to verify H = F G simply falls down to testing H(α) = F (α)G(α) for some random α in a large enough set . As mentioned in the introduction, this strategy may or may not have an optimal bit complexity, depending on the context. Here we are concerned with two difficulties that arise in either the dense or the sparse cases.

If the polynomials are dense, the verification through evaluation requires a number of operations in that is linear in the input polynomials degree n. When has more than n elements, taking ⊂ is sufficient to use evaluation. However, multiplication in has not a linear bit complexity and best known results remain quasi-linear [START_REF] Cantor | On fast multiplication of polynomials over arbitrary algebras[END_REF][START_REF] Harvey | Polynomial multiplication over finite fields in time O(n log n)[END_REF][START_REF] Harvey | Integer multiplication in time O(n log n)[END_REF]. The evaluation therefore leads to a quasi-linear bit complexity of (nI(log n)) = (n log n log log n). When is too small, for instance with a small finite field, is classically taken as a field extension of , large enough to make it unlikely that α is a root of H -F G. Therefore, each operation in corresponds to an operation over [X ] with non-negligible degree, meaning that the number of operations in is no more linear in the inputs degree n. As mentioned in the introduction, Kaminski's approach [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF] circumvents the later problem by replacing the evaluation with a computation in [X ]/(X i -1) for random integer i in a prescribed range. There, his algorithm is able to verify dense polynomial products with a linear number of operations in whatever the ring size. However, the same difficulty as for large rings may arise. Since operations in do not have an linear bit complexity, unless say = 2 , this is not always sufficient to reach an optimal bit complexity for the verification. In Section 5.1, we present Kaminski's approach [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF] and we provide a thorough analysis in the bit complexity model. In particular, we show that it is possible to get optimal verification in the bit complexity model for any polynomial in [X ] and for some polynomials in q [X ], depending on the relation between q and n.

If the polynomials F , G and H are sparse with at most T nonzero coefficients, the evaluation requires a number of operations in that is (T log n). However the input bit size is given by the size of the exponents plus the size of the coefficients, that is (T + log n) bits. Since has to be of size at least (log n), the bit complexity of evaluation would be (T log 2 n) which is not even quasi-linear. In Section 5.2 we develop a novel method, already appearing in [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF], to verify sparse polynomial multiplication with a quasi-linear bit complexity of ˜ (T + log n).

Dense polynomial product verification

In [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF], Kaminski describes an algorithm to verify a polynomial product H = F G ∈ [X ] using a linear number of operations in , regardless of its size. His method chooses at random a polynomial P that probably do not divides ∆ = H -F G if ∆ = 0. Then he verifies H = F G ∈ [X ]/P using fast polynomial multiplication. Surprisingly, taking P of degree o(n) in his algorithm enables to reach a linear number of operations in . In the following we will often use δ > 1.78107 to be some constant value related to Euler's constant.

Kaminski's algorithm

The first step is to randomly select a polynomial from a fixed set, such that it most probably does not divide ∆ = H -F G if ∆ = 0. A standard approach could be to consider irreducible polynomials. This would be the direct generalization of the evaluation method. However, Kaminski considers polynomials that are instead of the form X i -1, for some integers i > 0. These polynomials have two advantages: Reduction modulo X i -1 has a linear cost and all their divisors are cyclotomic polynomials so their least common multiple (lcm) has specific properties. Proposition 5.1 ([20]). For any integer set I ⊂ , i∈I Φ i divides lcm{X i -1 : i ∈ I}, where Φ i is the i-th cyclotomic polynomial in [X ].

Kaminski also gives a lower bound on the degree of lcm{X i -1 : i ∈ I}, depending in I. In particular the proposition implies that a nonzero polynomial, divisible by k polynomials, of the form X i -1, cannot have a too small degree. In the converse direction, a nonzero polynomial ∆ of degree at most 2n cannot have too many divisors of the form X i -1. This is the content of Kaminski's main theorem.

Theorem 5.2 ([20]

). Let ∆ be a nonzero polynomial in [X ] of degree ≤ 2n and 0 < e < 1 2 . Let k = 2δn e ln ln(n 1-e ) . At most k -1 polynomials in the set {X i -1|n 1-e ≤ i < 2n 1-e } divide ∆.

Kaminski's approach is then to choose a random integer i ∈ [n 1-e , 2n 1-e [, to reduce the input polynomials modulo X i -1 and to assert the equality in [X ]/(X i -1). We provide in Algorithm KAMINSKIVERIFICATION a more precise description of this approach.

Algorithm 8 KAMINSKIVERIFICATION

Input: F, G, H ∈ [X ] of degree n, n and 2n; and 0 < e < 1 2 . Output: True if H = F G, False with probability at least 1 -( 2δn e ln ln(n 1-e ) -1)/n 1-e otherwise.

1: i ← random integer in [n 1-e , 2n

F i , G i , H i ← F mod X i -1, G mod X i -1, H mod X i -1 3: M ← F i G i
Using a fast multiplication algorithm 4: M i ← M mod X i -1 5: return M i = H i Theorem 5.3 ([20]). Let F , G and H ∈ [X ] of degree at most n, n and 2n, 0 < e < 1 2 and an integer k as in Theorem 5.2. Algorithm 8 uses (n) operations in , and its failure probability is at most (k -1)/n 1-e if H = F G.

Remark 5.4. To be more precise, Algorithm 8 requires (n) additions in at Step 2 to compute the first three reductions modulo X i -1, M(n 1-e ) operations in to compute the product at Step 3,and (n 1-e ) additions in to compute the last reduction.

One shall remark that the product in Step 3 must be computed with a subquadratic algorithm such that M(n 1-e ) = (n) since e < 1/2. If the parameter e is taken close enough to 1/2, Karatsuba's algorithm suffices to reach a linear number of operations. The failure probability is (log log n/n 1-2e ), whence the need to have e < 1/2. We can bound this probability by ( 1 n e ) for any positive integer e < 1 -2e. In order to reach a probability ε of error, the algorithm should be repeated (log n 1 ε ) times. Note that this number of rounds is constant if ε is taken as 1/n (1) .

The drawback of such approach is to crucially rely on a somewhat fast multiplication algorithm, and to perform multiplications of polynomials of degrees more than n. This means that optimal verification of the product of two degree-n polynomials uses a product of polynomials of degrees close to n. In some contexts, such as verifying an implementation, relying on the same problem is definitively problematic.

We note that all steps starting from Step 3 aim to verify H i = F i G i mod X i -1 deterministically. It is easy to see that those steps can be replaced by our probabilistic modular product verification developed in Section 4. For polynomials over the integers or finite fields, this method does not require any polynomial multiplications at all. ) operations in , without reverting to any polynomial multiplication. In particular, the algorithm uses an optimal number of operations in when ε = 1/n (1) .

Proof. We replace the last three steps of Algorithm 8 by a modular product verification, with a probability of failure at most 1/n. Over or large finite fields, the complexity of this part is given by the dense version of Theorem 4.1 with #P = 2 and degree i = (n 1-e ). Over small finite fields, we rely instead on Corollary 4.15.

In both cases, one can achieve a failure probability at most 1/n with at most (log n) repetitions of the algorithm, for a total number of operations in that remains o(n). The total probability of failure of the modified algorithm is then 1/n + (1/n e ) = (1/n e ) for some e > 0. We can repeat this modified algorithm for (log n 1 ε ) rounds to get the announced failure probability and complexity.

Analysis in the bit complexity model

In [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF], Kaminski only details the algebraic complexity of its polynomial product verification, and no further insights on the bit complexity are given. We now perform this analysis for polynomials over finite fields and over . We surprisingly prove that his algorithm remains linear in number of bit operations in many cases. For polynomials over q , the algorithm fails to be linear only when q is doubly exponentially larger than the degree. For polynomials over , a similar condition applies. However, we are able to describe a variant of the algorithm that has linear bit complexity for polynomials with large coefficients. Hence we prove that polynomial product verification over has linear bit complexity in all cases. Our variant is based on integer product verification, for which Kaminski actually gives also in [START_REF] Kaminski | A note on probabilistically verifying integer and polynomial products[END_REF] a linear-time algorithm. Of course all those algorithms are therefore optimal.

The next theorem provides the bit complexity analysis of Kaminski's algorithm over finite fields. Theorem 5.6. Let F , G and H ∈ q [X ] of degrees n, n and 2n, and 0 < e < 1 2 . Algorithm 8 requires (n log q + n 1-e log q log log q) bit operations. When log log q = (n e ), one can verify if H = F G with failure probability at most ε if H = F G, using (n log q log n 1 ε ) bit operations which is optimal when ε = 1/n (1) .

Proof. We apply the count of operations given in Remark 5.4. The additions give the term (n log q). The bit complexity of the product of degree-(n 1-e ) polynomials over q is M q (n 1-e ) = (n 1-e log q log(n log q)), which is (n log q + n 1-e log q log log q). We obtain the claimed complexity.

The second part directly follows from the observation that (log n 1 ε ) rounds of the algorithm yield a failure probability at most ε.

Note that the bound log log q = (n e ) to get a linear number of bit operations in n log q is only valid when using the fastest known multiplication algorithm. If we replace by a slower algorithm, the bound becomes smaller. For instance, using Karatsuba's algorithm the product of degree-(n 1-e ) polynomials uses (n (1-e) log 3 log q log log q) ring operations. For the algorithm to still have an optimal complexity, we need that n (1-e) log 3 log log q = (n). This implies e ≥ 1 -1/ log 3 0.367, and the bound becomes log log q = (n 1-(1-e) log 3 ). If we take e close to 1/2, say 0.45, the bound reads log log q = (n 0.13 ) while it is log log q = (n 0.45 ) using the fastest multiplication algorithm.

Further, as mentioned previously, using a fast multiplication algorithm for the verification of a polynomial product is problematic. We now analyse the bit complexity of our variant that does not use any polynomial product, that is of Corollary 5.5. We show that the same complexity and the same bound on q can be obtained without any polynomial product.

Remark 5.7. Let F , G, H ∈ q [X ] of degrees n, n and 2n, and 0 < e < 1 2 . Algorithm 8 can be implemented using a modular product verification and without any polynomial product. This variant has bit complexity (n log q + n 1-e log q log log q). When log log q = (n e ), one can verify if H = F G with failure probability at most ε if H = F G, using (n log q log n 1 ε ) bit operations, which is optimal when ε = 1/n (1) , and without reverting to any polynomial product.

Proof. The proof simply consists in using Corollary 4.15 in place of Remark 5.4 in the previous proof.

Now we consider

F , G and H ∈ [X ] with F ∞ , G ∞ , H ∞ ≤ C.
We first analyse the bit complexity of Algorithm 8 and provide conditions for the algorithm to use a linear number of bit operations. Later we propose a variant to be able to verify H = F G with a linear number of bit operations for any integer polynomials.. ) bit operations which is optimal when ε = 1/n (1) . Proof. The first three reductions require (n) additions in to compute F i , G i and H i , whose norms are at most n e C. A careful computation of these additions using a binary tree uses ( As for polynomials over finite fields, the final computations can be replaced by a modular product verification. Here this yields a slightly better complexity. This improvement translates into an exponentially smaller constraint on the norm C for the algorithm to be optimal. Remark 5.9. Let F , G and H ∈ [X ], of degrees n, n and 2n and norms at most C, and 0 < e < 1 2 . Algorithm 8 can be implemented using a modular product verification and without any polynomial product. This variant has bit complexity (n log C + n 1-e log(C) log log log(C)). When log log log C = (n e ), one can verify if H = F G with failure probability at most ε if H = F G, using (n log C log n 1 ε ) bit operations, which is optimal when ε = 1/n (1) , and without reverting to any polynomial product.

Proof. The proof is once again similar, using the dense part of Theorem 4.4 for the modular product verification. This verification is performed on polynomials of degrees (n 1-e ) and norm at most n e C. Its bit complexity is then (n 1-e (I(log(n log C)+log(C) log log(n log C)))) which is (n log C +n 1-e log(C) log log log(C)). This proves the first part of the remark. The second part relies on repetition of Algorithm 8.

As long as the coefficients are not insanely huge compared to the degree, the previous remark applies and the polynomial product verification is linear. More precisely, this corresponds to C ranging from (1) to 2 2 2 (n)

. To deal with this extreme case of huge coefficients, we develop another approach that is valid as soon as log n = (log C). This means that all cases are covered with an optimal bit complexity. We shall mention that both methods are applicable when C is ranging from n (1) to 2 2 2 (n)

, which could be interesting when designing the most efficient implementation.

To treat the huge coefficient case, we rely on a result of Kaminski about the verification of the product of two integers. His technique is similar to the polynomial case: He reduces s-bit integers modulo 2 i -1 for some i between s 1-e and 2s 1-e , and then performed the product with reduced integers.

Theorem 5.10 ([20]

). Let a, b, c be integers of at most s, s and 2s bits, 0 < e < 1 2 and k = 2δs e ln ln(s 1-e ) where δ > 1.78107. We can check whether ab = c in (s) bit operations with a probability of error at most (k -1)/s 1-e if a b = c.

To verify a polynomial product H = F G over , we use the same idea as for computing the product. We use Kronecker substitution. If we evaluate each polynomial on β that is some large power of two, the coefficients of F G can directly be read on the digits of the integer F (β)G(β). These evaluations at β require no operation. The polynomial product verification is thus reduced to an integer product verification H(β) = F (β)G(β). ) bit operations, which is optimal when ε = 1/n (1) .

Proof. As F and G have norm C and degree n, F G has norm at most nC 2 . Let β be the first power of 2 greater than nC 2 . Then H = F G if and only if

H(β) = F (β)G(β).
The integers F (β), G(β) and H(β) have bit length (n log β) = (n log(nC)) = (n log C) since log n = (log C). As β is a large enough power of 2, the evaluation on β does not require any operation. Therefore all the cost comes from the verification of F (β)G(β) = H(β). This is linear in the size of F (β), G(β) and H(β) by Theorem 5.10, hence linear in n log C.

To get the appropriate probability bound, we use (log n log C 1 ε ) round of this algorithm. This is supported by the fact that the probability bound in Theorem 5.10 is 1/s (1) .

Quasi-linear sparse product verification

Given three sparse polynomials F , G and H in [X ], we want to assert that H = F G. As already mentioned, evaluating the polynomials at a random point α cannot yield a quasi-linear algorithm. Our approach is to take a random prime p and to verify the equality modulo X p -1 through modular product verification. This method is explicitly described in Algorithm 9 that works over any large enough integral domain . We further extend the description and the analysis of this algorithm for the specific cases = and = q . Algorithm 9 SPARSEVERIFICATION Input: H, F, G ∈ [X ]; 0 < ε < 1. Output: True if H = F G, False with probability at least 1 -ε otherwise.

1: Define 0 < ε 1 < 3 10 and 0 < ε 2 < 1 such that

Proof.

Step 3 dismisses two trivial mistakes and ensures that n is a bound on the degree of each polynomial.

If H = F G, the algorithm always returns True. Otherwise, there are two sources of failure. Either X p -1 divides H -F G. Since this polynomial has at most #H + #F #G terms, this failure occurs with probability at most 10ε 1 3 by Proposition 2.5. Or X p -1 does not divide H -F G but the modular product verification fails. This occurs with probability at most ε 2 . Altogether, the failure probability is at most To clarify the complexity, we will use the notation ε ( f (n)) as a shortcut for ( f (n) log k 1 ε ) for some k. Using this notation, the complexity of Algorithm 9 becomes ε (T log(T log n)) operations in plus ε (T log n log log(T log n))) bit operations as getting the prime p is logarithmic in T and log n. The rest of the section is dedicated to the bit complexity analysis of this algorithm over integers or finite fields. Our goal is to have bit complexities that are as close as possible to linear. To ease the comparison with truly linear complexity, we express these bit complexities in terms of the total bit size s of the input. A degree-n polynomial with T monomials has bit size s = (T (log n + log q)) if it has coefficients in q , and s = (T (log n + log C)) if it has coefficients in of absolute value at most C.

We first note that reducing the input polynomials modulo X p -1 at Step 6 is already non-linear. Indeed, we proved that this step has bit complexity ε (T log n log log(T log n)), which is ε (s log log s). We shall prove that in some cases, this step is actually the dominant term in the complexity.

We begin with the analysis over the integers. Proof. The input size is s = Θ(log k+1 n + log k n log C). In this case, log p = ε (log log n). In the previous proof, there is one dominant term of order ε (s log s log log s), while the other terms are already of order ε (s log log s). It is sufficient to prove that with the new assumption, the dominant term is also ε (s log log s).

The dominant term ε (s log s log log s) in the complexity comes from the term ε (T log pI(log(p log C))). Since log(p log C) = ε (log log n + log log C), this dominant term becomes ε (log k n log log n(log log n + log log C) log(log log n + log log C)).

Note that log log n and log log C are both (log s), therefore this can be rewritten ε (log k n log 2 s log log s). Since log k n = (s k/(k+1) ), this yields ε (s log log s).

We now switch to polynomials over finite fields. There are more cases to consider, depending on the size of the field with respect to the degree and sparsity of the inputs. The first easy case is the case of large finite fields: If there are enough points for the evaluation, the generic algorithm keeps its guarantee of success while offering a quasi-linear bit complexity.

Corollary 5.15. Let F , G and H ∈ q [X ] of degree at most n and sparsity at most T where q > 2 ε 1 ε 2 (#F #G + #H) ln n. Then Algorithm 9 has bit complexity ε (s log 2 (s)) where s = T (log n + log q) is the input size.

Proof. It is still enough to analyse Step 7. Each ring operation in q costs (log(q) log log(q)) bit operations which implies that the bit complexity of Step 7 is ε (T log(T log n) log(q) log log(q)). Since both T log q and T log n are (s) and log log q = (log s), the result follows.

If the field is not large enough, we need to use some extension field. This slightly modifies the algorithm but actually yields a better complexity bound than for large finite fields. This is due to the fact that in that case, we choose an extension of the exact appropriate size. Note that the probability of success remains unchanged.

Corollary 5.16. Let F , G and H ∈ q [X ] of degree at most n and sparsity at most T where q < 2 ε 1 ε 2 (#F #G + #H) ln n. Algorithm 9 has bit complexity ε (s log s log log s), where s = T (log n + log q) is the input size.

Proof. By Corollary 4.7 Step 7 requires ε (T log pM q (log q p) + (log q p) 2 M q (log q p)(log q + log log q p)) operations in q . Since log p = ε (log(T log n)) = ε (log s) and log q = ε (log s) too, the second term is polylogarithmic in s. As log p = ε (log(T log n)) the first term is ε (T log(T log n)M q (log q (T log n))). Since log(T log n) = (log n), T log(T log n) = (s). Furthermore, log(T log n) = (log s) and the first term simplifies to ε (sM q (log q s)). Now M q (log q s) = (log s log log s). Altogether T log pM q (log q p) = ε (s log s log log s). The result follows.

Again, we note that for very sparse polynomials over some fields, the complexity is even better. Remark 5.17. Let F , G and H ∈ q [X ] of degree at most n and sparsity at most T , where q < 2 ε 1 ε 2 (#F #G + #H) ln n. The bit complexity of Algorithm 9 is (i) ε (s log s) if log q (T log n) = (1), (ii) ε (s log log s) if T = Θ(log k n) for some constant k.

Proof. The most significant term in the complexity is ε (T log(T log n)M q (log q (T log n)). In the first case, it becomes ε (T log(T log n)M q (1)) = ε (T log(T log n) log q log log q). As log q = ε (log log n), T log q log log q = ε (s) and the complexity becomes ε (s log s). In the second case, the most significant term can be bounded by ε (T log 3 (T log n)). But T = (s k/(k+1) ), and this most significant term becomes ε (s) only. The global bit complexity is then dominated by Step 6 and is ε (s log log s).

To conclude, the bit complexity of Algorithm 9 over integers or finite fields range from ε (s log log s) in the most favorable cases, to ε (s log 2 s) in more complicated situations. We note that in the best cases, the complexity is actually dominated by the cost of the modular reduction of the exponents of the input polynomials.

Remark 5.18. Verification of a sparse product is always faster than computing the sparse product over or q . Proof. Assuming s = T (log n+log ζ) to be the input size of the sparse polynomial F ,G and H. Over we have log ζ = log C where C is the norm of the coefficients, while log ζ = log q when in q . The best know result for computing the product F G needs ε (s log 2 (s) log 2 (T )(log T + log log s)) bit operations [START_REF] Giorgi | Essentially optimal sparse polynomial multiplication[END_REF]. Taking the worst case complexity for our verification yields a cost of ε (s log 2 s). This means that we are always faster by a factor (log 2 (T )(log T + log log s)). Of course, for some small finite fields we are even beyond this value.

8: return β Theorem 3 . 6 .

 36 Algorithm 3 is correct. It uses (n#P) operations in and (n) operations in ext . Proof. Step 6 relies on Equation (4) to compute F α = F [i] (α). Step 7 uses this evaluation together with Equation (3) to correctly compute (F G mod P)(α). The first step requires (n#P) operations in by Lemma 3.5. (It does not depend on α.) The other steps require (n) operations in ext .

Algorithm 5 SPARSEMODULAREVALUATION

 5 Input: P, F and G ∈ [X ], with deg(F ), deg(G) < deg(P) = n, P monic and α ∈ ext . Output:

1 γ - 1

 11 and H are dense, or • ((T #P log n + (T + #P) log C log( n ε log C) )I(log( n ε log C))) bit operations if F , G and H are sparse.

Remark 4 . 6 .

 46 For ε = 1/n(1) , Algorithm 7 is faster than the polynomial modular product (i) when the polynomials are dense and #P < min( log n log log n , log C log log log C );

1 γ

 1 ) operations on integers of bit length log C. For the dense case, we compare to the cost of multiplying two polynomials of degree n and coefficients bounded by C. As seen in the introduction, this reduces to integer multiplication with Kronecker substitution and it costs I(n(log n + log C)) = (n(log 2 n + log n log C + log C log log C) bit operations. By Theorem 4.4 our verification needs (#P nI(log n + log log C) + n log C log(log n + log log C)) bit operations. The second term is dominated by the complexity of multiplying the polynomials when ε = 1/n(1) . The first term is (#P n((log n + log log C) log log n + (log n + log log C) log log log C)). When #P < min( log n log log n , log C log log log C ), this term is bounded by (n(log 2 n + log n log C + log C log log C)), that is the complexity of computing the product.

Corollary 5 . 5 . 1 ε

 551 If = or a finite field, and F , G and H ∈ [X ] of degrees n, n and 2n. We can check whether H = F G with a probability of failure at most ε if H = F G. This requires (n log n ) additions in plus o(n log n 1 ε

Theorem 5 . 8 .

 58 Let F , G and H ∈ [X ] of degrees n, n and 2n, and norms at most C, and 0 < e < 1 2 . Algorithm 8 requires (n log C + n 1-e log C log log C) bit operations. When log log C = (n e ), one can verify if H = F G with failure probability at most ε if H = F G, using (n log C log n 1 ε

log n i=1 n 2 i 1 ε

 21 log(iC) = (n log C) bit operations. Then the polynomial product is performed with inputs of degree n 1-e and norm n e C. As discussed in the introduction, it requires I(n 1-e (log(n e C) + log n 1-e )) bit operations, that is (n 1-e (log n + log C)(log n + log log C)) = (n log C + n 1-e log C log log C). Finally the last reduction is performed with degree 2n 1-e and norm n(n e C) 2 in (n log C) bit operations.Repeating (log n ) times the algorithm provides the second part of the theorem.

Theorem 5 . 11 .

 511 Let F , G, H ∈ [X ] of respective degrees n, n and 2n, and norm at most C. If log n = (log C), we can check whether H = F G with failure probability at most ε if H = F G, using (n log C log n log C 1 ε

1 3 3 ) 6 : 2 Theorem 5 . 12 .

 1362512 )ε 2 ≤ ε 2: n ← deg(H) 3: if #H > #F #G or n = deg(F ) + deg(G) then return False 4: λ ← max(21, 1 ε 1 (#F #G + #H) ln n) 5: p ← RANDOMPRIME(λ, 5ε 1 (F p , G p , H p ) ← (F mod X p -1, G mod X p -1, H mod X p -1) 7: return True if H p = (F p G p ) mod X p -1, False otherwise using Theorem 4.1 with probability ε If is an integral domain of size ≥ 2 ε 1 ε 2 (#F #G + #H) ln(n), Algorithm 9 works as specified. Assuming that n = deg(H) and T = max(#F, #G, #H), it requires (T log( 1 ε T log n)) operations in , and (T log n log log( 1 ε T log n)) bit operations plus (log 1 ε log 3 ( 1 ε T log n) log 2 log( 1 ε T log n))bit operations to obtain a prime p.

10ε 1 3

 1 )ε 2 ≤ ε.To analyse the complexity, we consider ε 1 , ε 2 ∼ ε (for example ε 1 = 3ε 20 and ε 2 = ε 2 ). Let us remark that p = ( 1 ε T 2 log n). To get the prime p, Step 5 requires only (log 1 ε log 3 p log 2 log p) bit operations by Proposition 2.4. This gives the announced complexity once log p is replaced by (log( 1 ε T log n)). The operations in Step 6 are T divisions by p on integers bounded by n. Their cost is (T log n log p I(log p)) = (T log n log log p) bit operations, that is (T log n log log( 1 ε T log n))), plus T additions in . In Step 7, F p , G p and H p have degree p = ( 1 ε T 2 log n) and at most T monomials. They are still sparse and we can use the sparse version of Theorem 4.1 with P = X p -1. The verification of H p = F p G p mod X p -1 thus requires (T log p) = (T log( 1 ε T log n)) operations in . Other steps have negligible cost.

Corollary 5 . 13 .Remark 5 . 14 .

 513514 Let F , G and H ∈ [X ] of degree at most n, with norm at most C and sparsity at most T . Then Algorithm 9 has bit complexity ε (s log s log log s), where s = T (log n + log C) is the input size. Proof. The modification only concerns Step 7, where we use Theorem 4.4 for the modular product verification with P = X p -1 and F p , G p , H p that have sparsity T and norm T C. So this step costsε (T log pI(log(p log C)) + T log(T C) log log(p log T C)). Since T ≤ n, T log p = ε (T log n) = ε (s). And log(p log C) = ε (log(T log n log C)) = ε (log(T log n) + log log C) = ε (log s). Thus the first term is ε (s log s log log s). Also, T log(T C) = (T log nC) = (s). As log(p log T C) = ε (log(T log n) + log log C) = ε (log S), the second term is ε (s log log s). Since Step 6 is unchanged and has bit complexity ε (s log log s), the result follows.The complexity is actually better for very sparse polynomials. If F , G, H ∈ [X ] of bit size s have sparsity at most T = Θ(log k n) for some k, Algorithm 9 has bit complexity ε (s log log s).

  1-e [ 2:

Here, and throughout the article, ˜ ( f (n)) denotes ( f (n) log k ( f (n))) for some constant k > 0.