J. Doliskani, P. Giorgi, R. Lebreton, and É. Schost, Simultaneous conversions with the Residue Number System using linear algebra, ACM Transactions on Mathematical Software, vol.44, pp.62-64, 2018.
URL : https://hal.archives-ouvertes.fr/lirmm-01415472

P. Giorgi, A probabilistic algorithm for verifying polynomial middle product in linear time, Information Processing Letters, vol.139, p.23, 2018.
URL : https://hal.archives-ouvertes.fr/lirmm-01538453

P. Giorgi, On Polynomial Multiplication in Chebyshev Basis, IEEE Transactions on Computers, vol.61, pp.38-40, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00520207

J. Dumas, P. Giorgi, and C. Pernet, Dense Linear Algebra over Finite Fields: the FFLAS and FFPACK package, ACM Transactions on Mathematical Software, vol.35, p.61, 2008.

P. Giorgi, B. Grenet, and D. S. Roche, Generic reductions for in-place polynomial multiplication, Proceedings of the 2019 international symposium on symbolic and algebraic computation. ISSAC'19
URL : https://hal.archives-ouvertes.fr/lirmm-02003089

P. Giorgi and V. Neiger, Certification of minimal approximant bases, Proceedings of the 2018 international symposium on symbolic and algebraic computation. ISSAC'18, pp.67-174, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701861

A. Breust, C. Chabot, J. Dumas, L. Fousse, and P. Giorgi, Recursive double-size fixed precision arithmetic, ICMS: International Congress on Mathematical Software, vol.9725, p.11, 2016.
URL : https://hal.archives-ouvertes.fr/hal-00582593

B. Boyer, J. Dumas, P. Giorgi, C. Pernet, and B. Saunders, Elements of Design for Containers and Solutions in the LinBox Library, ICMS: International Congress on Mathematical Software, vol.8592, pp.654-662, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01015138

P. Giorgi and R. Lebreton, Online Order Basis and its impact on Block Wiedemann Algorithm, Proceedings of the 2014 international symposium on symbolic and algebraic computation. ISSAC'14
URL : https://hal.archives-ouvertes.fr/lirmm-01232873

, , pp.202-209, 2014.

P. Giorgi and B. Vialla, Generating Optimized Sparse Matrix Vector Product over Finite Fields, ICMS: International Congress on Mathematical Software, vol.8592, p.14, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-01275818

P. Giorgi, L. Imbert, and T. Izard, Parallel Modular Multiplication on Multi-Core Processors, Proceedings of the 21th IEEE Symposium on Computer Arithmetic, ARITH21, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00805242

. -bdg10],

B. Boyer, J. Dumas, and P. Giorgi, Exact Sparse Matrix-Vector Multiplication on GPU's and Multicore Architectures, Proceedings of PASCO'10: Parallel Symbolic Computation, vol.14, p.13, 2010.

P. Giorgi, L. Imbert, and T. Izard, Optimizing elliptic curve scalar multiplication for small scalars, Mathematics for Signal and Information Processing, vol.7444, p.14, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00424282

P. Giorgi, T. Izard, and A. Tisserand, Comparison of Modular Arithmetic Algorithms on GPUs, Proceedings of the International Conference on Parallel Computing ParCo, vol.19, pp.315-322, 2009.
URL : https://hal.archives-ouvertes.fr/lirmm-00424288

S. Boldo, M. Daumas, and P. Giorgi, Formal proof for delayed finite field arithmetic using floating point operators, Proceedings of the 8th Conference on Real Numbers and Computers, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00135090

J. Dumas, P. Elbaz-vincent, P. Giorgi, and A. Urbánska, Parallel computation of the rank of large sparse matrices from algebraic K-theory, Proceedings of the 2007 international workshop on parallel symbolic computation. PASCO '07, pp.43-52, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00142141

W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, and G. Villard, Faster inversion and other black box matrix computations using efficient block projections, Proceedings of the 2007 international symposium on symbolic and algebraic computation. ISSAC '07, pp.143-150, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00127807

P. Giorgi, C. Nègre, and T. Plantard, Subquadratic Binary Field Multiplier in Double Polynomial System, Proceedings of the International Conference on Security and Cryptography, SECRYPT'07, pp.229-236, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00140082

W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann, and G. Villard, Solving sparse rational linear systems, Proceedings of the 2006 international symposium on symbolic and algebraic computation. IS-SAC '06, pp.63-70, 2006.

J. Dumas, P. Giorgi, and C. Pernet, FFPACK: finite field linear algebra package, Proceedings of the 2004 international symposium on symbolic and algebraic computation. ISSAC '04, p.59, 2004.
URL : https://hal.archives-ouvertes.fr/hal-02018838

P. Giorgi, C. Jeannerod, and G. Villard, On the complexity of polynomial matrix computations, Proceedings of the 2003 international symposium on symbolic and algebraic computation. ISSAC '03, vol.60, p.69, 2003.
URL : https://hal.archives-ouvertes.fr/hal-02101878

J. Dumas, T. Gautier, and M. Giesbrecht, Linbox: A Generic Library For Exact Linear Algebra, Proceedings of the 2002 International Congress of Mathematical Software, 2002.
URL : https://hal.archives-ouvertes.fr/hal-02102080

P. Giorgi and R. Lebreton, Relaxing Order Basis Computation, Poster at ISSAC'13. Abstract published in ACM Communications in Computer Algebra, pp.100-101, 2014.
URL : https://hal.archives-ouvertes.fr/lirmm-01372532

P. Giorgi, Toward High Performance Matrix Multiplication for Exact Computation, talk given at SIAM Conference on Parallel Processing for Scientific Computing, 2014.

P. Giorgi, Z. Olesh, and A. Storjohann, Implementation of a Las Vegas Integer Matrix Determinant Algorithm. Poster East Coast Computer Algebra Day, 2005.

M. Brassel, P. Giorgi, and C. Pernet, LUdivine: a Symbolic block LU factorisation for matrices over finite fields using BLAS. Poster at East Coast Computer Algebra Day, 2003.

L. M. Adleman, The Function Field Sieve, Proceedings of the First International Symposium on Algorithmic Number Theory. ANTS-I, p.1, 1994.

A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, p.43, 1974.

G. Alagic, J. Alperin-sheriff, and D. Apon, Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process, p.85, 2019.

A. , Modern C++ Design: Generic Programming and Design Patterns Applied, p.11, 2001.

E. Anderson, Z. Bai, and C. Bischof, PA: Society for Industrial and Applied Mathematics, p.62, 1999.

A. Arnold and D. S. Roche, Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. ISSAC '15, vol.86, p.85, 2015.

S. Arora and B. Barak, Computational Complexity: A Modern Approach. 1st, vol.4, 2009.

R. Barbulescu, C. Bouvier, and J. Detrey, Discrete Logarithm in GF(2809) with FFS, Public-Key Cryptography -PKC 2014, pp.221-238, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00818124

P. Barrett, Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, Advances in Cryptology, CRYPTO'86, vol.263, pp.311-326, 1986.

G. Baszenski and M. Tasche, Fast polynomial multiplication and convolution related to the discrete cosine transform, Linear Algebra and its Application, vol.252, pp.1-25, 1997.

Z. Battles and L. Trefethen, An extension of MATLAB to continuous fractions and operators, In: SIAM J. Sci. Comp, p.37, 2004.

W. Baur and V. Strassen, The Complexity of Partial Derivatives, Theoretical Computer Science, vol.22, issue.83, p.90110, 1983.

B. Beckermann and G. Labahn, A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants, SIAM J. Matrix Anal. Appl, vol.15, p.69, 1994.

B. Beckermann and G. Labahn, Fraction-Free Computation of Matrix Rational Interpolants and Matrix GCDs, In: SIAM J. Matrix Anal. Appl, vol.22, p.82, 2000.

B. Beckermann, G. Labahn, and G. Villard, Shifted Normal Forms of Polynomial Matrices, ISSAC'99, vol.74, p.68, 1999.

B. Beckermann, G. Labahn, and G. Villard, Normal forms for general polynomial matrices, J. Symbolic Comput, vol.41, issue.6, pp.708-737, 2006.
URL : https://hal.archives-ouvertes.fr/hal-02101933

M. Ben-or and P. Tiwari, A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. STOC '88, p.85, 1988.

A. Benoit, Fast Semi-numerical Algorithms for Chebyshev Series, Theses. Ecole Polytechnique X, p.38, 2012.
URL : https://hal.archives-ouvertes.fr/pastel-00726487

D. J. Bernstein, Multidigit Modular Multiplication With The Explicit Chinese Remainder Theorem, p.66, 1995.

J. Berthomieu and R. Lebreton, Relaxed P-adic Hensel Lifting for Algebraic Systems, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. ISSAC '12, p.71, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00660566

R. E. Blahut, Transform Techniques for Error Control Codes, IBM Journal of Research and Development, vol.23, issue.3, p.85, 1979.

L. Bluestein, A linear filtering approach to the computation of discrete Fourier transform, IEEE Transactions on Audio and Electroacoustics, vol.18, p.63, 1970.

M. Bodrato and A. Zanoni, Integer and Polynomial Multiplication: Towards Optimal Toom-Cook Matrices, vol.28, p.27, 2007.

A. Borodin and R. Moenck, Fast modular transforms, Journal of Computer and System Sciences, vol.8, issue.3, pp.62-64, 1974.

A. Bostan, G. Lecerf, and É. Schost, Tellegen's Principle into Practice, Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation. ISSAC '03, vol.19, pp.37-44, 2003.

A. Bostan and É. Schost, Polynomial evaluation and interpolation on special sets of points, J. Complexity, vol.21, pp.420-446, 2005.

A. Bostan, F. Chyzak, and M. Giusti, Algorithmes Efficaces en Calcul Formel. 1.0, vol.5, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01431717

A. Bostan, B. Salvy, M. F. Chowdhury, É. Schost, and R. Lebreton, Power Series Solutions of Singular (Q)-differential Equations, Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. ISSAC '12, p.71, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00697733

A. Bostan, B. Salvy, and É. Schost, Power series composition and change of basis, Proceedings of the 2008 International Symposium on Symbolic and Algebraic Computation, pp.269-276, 2008.
URL : https://hal.archives-ouvertes.fr/inria-00273385

A. Bostan, B. Salvy, and É. Schost, Fast Conversion Algorithms for Orthogonal Polynomials, Linear Algebra and its Applications, vol.432, issue.1, pp.249-258, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00273508

J. P. Boyd, Chebyshev and Fourier Spectral Methods, p.37, 2001.

B. Boyer and J. Dumas, Matrix Multiplication Over Word-Size Modular Rings Using Approximate Formulas, ACM Trans. Math. Softw, vol.42, p.59, 2016.

B. Boyer, J. Dumas, C. Pernet, and W. Zhou, Memory Efficient Scheduling of Strassen-Winograd's Matrix Multiplication Algorithm, Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. ISSAC '09, pp.55-62, 2009.

R. Brent and P. Zimmermann, Modern Computer Arithmetic, vol.17, p.49, 2010.
URL : https://hal.archives-ouvertes.fr/cel-01500109

N. Brisebarre and M. Jolde?, Chebyshev Interpolation Polynomialbased Tools for Rigorous Computing, Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. ISSAC '10, p.37, 2010.
URL : https://hal.archives-ouvertes.fr/ensl-00472509

D. Buchfuhrer and C. Umans, The complexity of Boolean formula minimization, Journal of Computer and System Sciences, vol.77, issue.1, p.14, 2011.

J. R. Bunch and J. E. Hopcroft, Triangular Factorization and Inversion by Fast Matrix Multiplication, Mathematics of Computation, vol.28, p.61, 1974.

D. G. Cantor and E. Kaltofen, On Fast Multiplication of Polynomials over Arbitrary Algebras, Acta Informatica, vol.28, pp.693-701, 1991.

S. C. Chan and K. L. Ho, Direct methods for computing discrete sinusoidal transforms, Radar and Signal Processing, vol.137, p.37, 1990.

Y. Cheng, Space-Efficient Karatsuba Multiplication for Multi-Precision Integers, vol.81, p.24, 2016.

S. A. Cook, On the minimum computation time of functions, pp.51-77, 1966.

J. Cooley and J. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series, In: Mathematics of Computation, vol.19, pp.297-301, 1965.

D. Coppersmith, Solving homogeneous linear equations over GF[2] via block Wiedemann algorithm, Mathematics of Computation 62.205, pp.333-350, 1994.

R. A. Demillo and R. J. Lipton, A probabilistic remark on algebraic program testing, Information Processing Letters, vol.7, issue.78, p.20, 1978.

W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Transactions on Information Theory IT-22, p.1, 1976.

V. Dimitrov, L. Imbert, and P. K. Mishra, Efficient and Secure Elliptic Curve Point Multiplication using Double-Base Chains, Advances in Cryptology, ASIACRYPT'05, vol.3788, p.14, 2005.
URL : https://hal.archives-ouvertes.fr/lirmm-00106638

J. Dumas and E. Kaltofen, Essentially Optimal Interactive Certificates in Linear Algebra, ISSAC'14, vol.83, p.73, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00932846

J. G. Dumas, T. Gautier, and C. Pernet, Finite Field Linear Algebra Subroutines, Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. ISSAC '02, pp.63-74, 2002.
URL : https://hal.archives-ouvertes.fr/hal-02018841

J. P. Dumas-;-v, W. Gerdt, W. M. Koepf, E. V. Seiler, and . Vorozhtsov, Proof-of-work certificates that can be efficiently computed in the cloud, The 20th International Workshop on Computer Algebra in Scientific Computing, p.74, 2018.

J. Dumas, T. Gautier, C. Pernet, J. Roch, and Z. Sultan, Recursion based parallelization of exact dense linear algebra routines for Gaussian elimination, Parallel Computing, vol.57, p.62, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01084238

J. Dumas, T. Gautier, C. Pernet, and Z. Sultan, Parallel Computation of Echelon Forms, Euro-Par 2014 Parallel Processing, p.62, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00947013

J. Dumas, T. Gautier, and J. Roch, Generic Design of Chinese Remaindering Schemes, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation. PASCO '10
URL : https://hal.archives-ouvertes.fr/hal-00449864

F. Grenoble, , p.70, 2010.

J. Dumas, E. Kaltofen, and E. Thomé, Interactive certificate for the verification of Wiedemann's Krylov sequence: application to the certification of the determinant, the minimal and the characteristic polynomials of sparse matrices, vol.83, p.10, 2015.

J. Dumas, E. Kaltofen, E. Thomé, and G. Villard, Linear Time Interactive Certificates for the Minimal Polynomial and the Determinant of a Sparse Matrix, International Symposium on Symbolic and Algebraic Computation. ISSAC'2016, Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation, vol.10, p.73, 2016.

J. Dumas, C. Pernet, and Z. Sultan, Simultaneous Computation of the Row and Column Rank Profiles, Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation. ISSAC '13, vol.67, p.65, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00778136

J. Dumas, C. Pernet, and Z. Sultan, Computing the Rank Profile Matrix, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation. ISSAC '15, vol.62, p.61, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01107722

W. Eberly and E. Kaltofen, On Randomized Lanczos Algorithms, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation. ISSAC '97, vol.8, pp.176-183, 1997.

T. E. Gamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, Proceedings of CRYPTO 84 on Advances in Cryptology, pp.10-18, 1985.

J. Farkas, Theorie der einfachen Ungleichungen, In: J. Reine Angew. Math, vol.124, p.9, 1902.

M. J. Fischer and L. J. Stockmeyer, Fast on-line integer multiplication, Journal of Computer and System Science, vol.9, p.71, 1974.

M. A. Forbes and A. Shpilka, Challenges in Polynomial Factorization1, SIGACT News, vol.88, p.86, 2015.

R. Freivalds, Fast probabilistic algorithms, Mathematical Foundations of Computer Science, vol.74, pp.57-69, 1979.

M. Frigo and S. Johnson, Special issue on "Program Generation, Optimization, and Platform Adaptation, Proceedings of the IEEE 93, vol.2, p.40, 2005.

M. Fürer, Faster Integer Multiplication, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing. STOC '07, vol.43, p.17, 2007.

J. V. Gathen and J. Gerhard, Modern Computer Algebra, vol.85, p.81, 2013.

P. Gaudry, A. Kruppa, and P. Zimmermann, A Gmp-based Implementation of SchöNhage-strassen's Large Integer Multiplication Algorithm, Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. ISSAC '07. Waterloo, Ontario, vol.81, p.43, 2007.

P. Gaudry and E. Thomé, The mpFq library and implementing curve-based key exchanges". In: SPEED: Software Performance Enhancement for Encryption and Decryption. ECRYPT Network of Excellence in Cryptology, pp.49-64, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00168429

W. M. Gentleman and G. Sande, Fast Fourier Transforms: For Fun and Profit, Fall Joint Computer Conference. AFIPS '66 (Fall), p.17, 1966.

C. Gentry, A fully homomorphic encryption scheme, p.85, 2009.

S. Goldwasser, Y. T. Kalai, and G. N. Rothblum, Delegating Computation: Interactive Proofs for Muggles, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08

, , vol.73, p.9, 2008.

G. H. Golub and D. P. O'leary, Some History of the Conjugate Gradient and Lanczos Methods", In: SIAM Rev, vol.31, p.1, 1989.

K. Goto and R. Van-de-geijn, High-performance implementation of the level-3 BLAS, ACM Transactions on Mathematical Software, vol.35, p.61, 2008.

T. Granlund, . Development-team, and . Gnu-mp, The GNU Multiple Precision Arithmetic Library, vol.25, p.40

A. W. Groves and D. S. Roche, Sparse Polynomials in FLINT, In: ACM Commun. Comput. Algebra, vol.50, p.86, 2016.

S. Gupta, S. Sarkar, A. Storjohann, and J. Valeriote, Triangular x-basis decompositions and derandomization of linear algebra algorithms over K[x, J. Symbolic Comput, vol.47, pp.422-453, 2012.

S. Gupta and A. Storjohann, Computing Hermite Forms of Polynomial Matrices, ISSAC'11, pp.155-162, 2011.

T. Hagerup, Sorting and Searching on the Word RAM, Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science. STACS '98, p.3, 1998.

G. Hanrot and P. Zimmermann, A long note on Mulders' short product, Journal of Symbolic Computation, vol.37, p.18, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00071931

G. Hanrot, M. Quercia, and P. Zimmermann, The Middle Product Algorithm I, Applicable Algebra in Engineering, vol.14, p.23, 2004.
URL : https://hal.archives-ouvertes.fr/inria-00071921

W. B. Hart, Fast library for number theory: an introduction, Mathematical Software-ICMS 2010

D. Harvey, Faster arithmetic for number-theoretic transforms, Journal of Symbolic Computation, vol.60, p.60, 2014.

D. Harvey and J. Van-der-hoeven, On the complexity of integer matrix multiplication, Journal of Symbolic Computation, vol.89, p.62, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01071191

D. Harvey and J. Van-der-hoeven, Integer multiplication in time, vol.43, p.17, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02070778

D. Harvey and J. Van-der-hoeven, Polynomial multiplication over finite fields in time O, vol.43, p.17, 2019.
URL : https://hal.archives-ouvertes.fr/hal-02070816

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Even faster integer multiplication, Journal of Complexity, vol.36, p.17, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01022749

D. Harvey, J. Van-der-hoeven, and G. Lecerf, Faster Polynomial Multiplication over Finite Fields, J. ACM, vol.63, p.17, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01022757

D. Harvey and D. S. Roche, An in-place truncated fourier transform and applications to polynomial multiplication, Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, pp.325-329, 2010.

F. C. Hennie, On-Line Turing Machine Computations, Electronic Computers, vol.1, p.71, 1966.

J. Van-der-hoeven, Relax, but don't be too lazy, J. Symbolic. Comput, vol.34, p.71, 2002.

J. Van-der-hoeven, Relaxed multiplication using the middle product, ISSAC'03, p.71, 2003.

J. Van-der-hoeven, The truncated Fourier transform and applications, Proceedings of the 2004 international symposium on Symbolic and algebraic computation. ISSAC '04, p.29, 2004.

J. Van-der-hoeven, New algorithms for relaxed multiplication, J. Symbolic Comput, vol.42, p.71, 2007.

J. Van-der-hoeven, Making fast multiplication of polynomials numerically stable, vol.41, p.40, 2008.

J. Van-der-hoeven, G. Lecerf, and B. Mourrain, Mathemagix: the quest of modularity and efficiency for symbolic and certified numeric computation?, In: ACM Communications in Computer Algebra, vol.45, issue.4, p.52, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01285476

J. Van-der-hoeven, Lazy Multiplication of Formal Power Series, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation. ISSAC '97, p.71, 1997.

J. Van-der-hoeven, Faster Relaxed Multiplication, Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation. ISSAC '14, vol.72, p.71, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00687479

J. Van-der-hoeven, Fast Chinese Remaindering in Practice, Mathematical Aspects of Computer and Information Sciences, p.50, 2017.
URL : https://hal.archives-ouvertes.fr/hal-02350526

J. Van-der-hoeven and G. Lecerf, On the bit-complexity of sparse polynomial and series multiplication, Journal of Symbolic Computation, vol.50, p.85, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00476223

J. Van-der-hoeven and G. Lecerf, Sparse polynomial interpolation in practice, p.86, 2014.
URL : https://hal.archives-ouvertes.fr/hal-00980366

J. Van-der-hoeven, G. Lecerf, and G. Quintin, Modular SIMD Arithmetic in Mathemagix, ACM Trans. Math. Softw, vol.43, issue.1, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01022383

S. G. Hyun, V. Neiger, and É. Schost, Implementations of efficient univariate polynomial matrix algorithms and application to bivariate resultants". working paper or preprint, p.84, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01995873

O. H. Ibarra, S. Moran, and R. Hui, A generalization of the fast LUP matrix decomposition algorithm and applications, In: Journal of Algorithms, vol.3, p.61, 1982.

M. Intel, Intel math kernel library, 2007.

M. Ishii, J. Detrey, P. Gaudry, A. Inomata, and K. Fujikawa, Fast Modular Arithmetic on the Kalray MPPA-256 Processor for an Energy-Efficient Implementation of ECM, IEEE Transactions on Computers, vol.66, p.81, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01299697

T. Izard, Opérateurs arithmétiques parallèles pour la cryptographie asymétrique, vol.2, p.47, 2011.

C. Jeannerod, V. Neiger, É. Schost, and G. Villard, Fast computation of minimal interpolation bases in Popov form for arbitrary shifts, ISSAC'16, vol.77, pp.295-302, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01265983

C. Jeannerod, V. Neiger, É. Schost, and G. Villard, Computing minimal interpolation bases, J. Symbolic Comput, vol.83, p.22, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01241781

C. Jeannerod and G. Villard, Essentially optimal computation of the inverse of generic polynomial matrices, J. Complexity, vol.21, issue.6, pp.72-86, 2005.

C. Jeannerod, V. Neiger, and G. Villard, Fast computation of approximant bases in canonical form, p.68, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01683632

C. Jeannerod, C. Pernet, and A. Storjohann, Rank-profile revealing Gaussian elimination and the CUP matrix decomposition, J. Symbolic Comput, vol.56, p.67, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00655543

H. Jeljeli, Accélérateurs logiciels et matériels pour l'algèbre linéaire creuse sur les corps finis, p.14, 2015.

M. E. Kaihara and N. Takagi, Bipartire Modular Multiplication Method, IEEE Transactions on Computers, vol.57, pp.157-164, 2008.

T. Kailath, Linear Systems, p.75, 1980.

E. Kaltofen, Asymptotically Fast Solution of Toeplitz-like Singular Linear Systems, ISSAC'94, pp.297-304, 1994.

E. Kaltofen and W. Lee, Early Termination in Sparse Interpolation Algorithms, J. Symbolic. Comput, vol.36, pp.365-400, 2003.

E. Kaltofen, B. Li, Z. Yang, and L. Zhi, Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, J. Symbolic Comput, vol.47, issue.1, p.9, 2012.

E. Kaltofen and A. Lobo, Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields, Algorithmica 24.3, vol.8, pp.331-348, 1999.

E. Kaltofen, M. Nehring, and B. D. Saunders, Quadratic-time Certificates in Linear Algebra, ISSAC'11, vol.73, p.9, 2011.

E. Kaltofen and D. Saunders, On Wiedemann's method of solving sparse linear systems, AAECC-9, vol.539, pp.29-38, 1991.

E. Kaltofen and G. Villard, On the complexity of computing determinants, Comput. Complexity, vol.13, p.70, 2005.
URL : https://hal.archives-ouvertes.fr/hal-02102099

E. Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, vol.64, pp.777-806, 1995.

E. L. Kaltofen, Fifteen Years After DSC and WLSS2 What Parallel Computations I Do Today: Invited Lecture at PASCO, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation. PASCO '10, p.84, 2010.

A. Karatsuba and Y. Ofman, Multiplication of Multidigit Numbers on Automata, In: Soviet Physics-Doklady, vol.7, pp.595-596, 1963.

T. Kimbrel and R. K. Sinha, A probabilistic algorithm for verifying matrix products using O(n 2 ) time and log 2 (n) + O(1) random bits, Information Processing Letters, vol.45, pp.107-110, 1993.

T. Kleinjung, C. Diem, A. K. Lenstra, C. Priplata, and C. Stahlke, Computation of a 768-Bit Prime Field Discrete Logarithm, p.10, 2017.

T. Kleinjung, K. Aoki, and J. Franke, Factorization of a 768-Bit RSA Modulus, Advances in Cryptology -CRYPTO, p.84, 2010.
URL : https://hal.archives-ouvertes.fr/inria-00444693

T. Kleinjung, J. W. Bos, and A. K. Lenstra, A heterogeneous computing environment to solve the 768-bit RSA challenge, Cluster Computing, vol.15, pp.53-68, 2012.
URL : https://hal.archives-ouvertes.fr/inria-00535765

D. E. Knuth, The analysis of algorithms, Congrès int. Math, vol.3, pp.269-274, 1970.

D. E. Knuth, Seminumerical Algorithms, The Art of Computer Programming, vol.2, p.14, 1997.

Ç. K. Koç, T. Acar, and B. S. Kaliski, Analyzing and Comparing Montgomery Multiplication Algorithms, IEEE Micro, vol.16, issue.3, p.44, 1996.

G. Labahn, V. Neiger, and W. Zhou, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01345627

C. L. Lawson, R. J. Hanson, D. R. Kincaid, and F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Trans. Math. Softw, vol.5, issue.3, p.7, 1979.

F. and L. Gall, Powers of Tensors and Fast Matrix Multiplication, ISSAC'14, pp.296-303, 2014.

R. Lebreton, Contribution to relaxed algorithms and polynomial system solving, vol.81, p.71, 2012.

R. Lebreton, Relaxed Hensel lifting of triangular sets, Journal of Symbolic Computation, vol.68, p.71, 2015.
URL : https://hal.archives-ouvertes.fr/lirmm-01282077

R. Lebreton and É. Schost, A simple and fast online power series multiplication and its analysis, Journal of Symbolic Computation, vol.72, p.71, 2016.
URL : https://hal.archives-ouvertes.fr/lirmm-00867279

, The development of the number field sieve, vol.1554, p.1, 1993.

R. Lidl, G. Mullen, and G. Turnwald, Dickson polynomials. Pitman monographs and surveys in pure and applied mathematics. Longman Scientific & Technical, 1993 (cit, p.38

A. Lincoln, V. Williams, J. R. Wang, and R. R. Williams, Deterministic Time-Space Trade-Offs for k-SUM". In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016, vol.55, p.36, 2016.

D. Lucas, V. Neiger, C. Pernet, D. S. Roche, and J. Rosenkilde, Interactive Certificates for Polynomial Matrices with Sub-Linear Communication, vol.83, p.73, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01829139

V. Lyubashevsky, C. Peikert, and O. Regev, On Ideal Lattices and Learning with Errors over Rings, Advances in Cryptology -EU-ROCRYPT 2010, p.85, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00921792

V. Lyubashevsky, C. Peikert, and O. Regev, A Toolkit for Ring-LWE Cryptography, Advances in Cryptology -EUROCRYPT 2013, p.85, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00864284

J. C. Mason and D. C. Handscomb, Chebyshev polynomials, p.37, 2002.

J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Inf. Theory, vol.15, p.3, 1969.

P. K. Mishra and V. Dimitrov, Efficient Quintuple Formulas for Elliptic Curves and Efficient Scalar Multiplication Using Multibase Number Representation, p.14, 2007.

R. Moenck and A. Borodin, Fast modular transforms via division, 13th Annual Symposium on Switching and Automata Theory (swat 1972), p.7, 1972.

P. L. Montgomery, Modular Multiplication Without Trial Division, Mathematics of Computation, vol.44, pp.519-521, 1985.

P. L. Montgomery and R. D. Silverman, An FFT Extension to the P -1 Factoring Algorithm, Mathematics of Computation -Math

. Comput, , vol.54, p.66, 1990.

T. Mulders, On Short Multiplications and Divisions, In: Applicable Algebra in Engineering, Communication and Computing, vol.11, p.17, 2000.

C. Negre, Multiplication in Finite Fields and Elliptic Curves". Habilitation à diriger des recherches, p.44, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01385034

V. Neiger, Bases of relations in one or several variables: fast algorithms and applications, vol.82, p.68, 2016.
URL : https://hal.archives-ouvertes.fr/tel-01431413

V. Neiger, Fast Computation of Shifted Popov Forms of Polynomial Matrices via Systems of Modular Polynomial Equations, Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation. ISSAC '16, pp.365-372, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01266014

V. Neiger, J. Rosenkilde, and G. Solomatov, Computing Popov and Hermite Forms of Rectangular Polynomial Matrices, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. ISSAC '18, pp.295-302, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01701867

C. Pernet, High Performance and Reliable Algebraic Computing". Habilitation à diriger des recherches, Université Joseph Fourier, Grenoble, vol.1, 2014.
URL : https://hal.archives-ouvertes.fr/tel-01094212

C. Pernet and A. Storjohann, Faster Algorithms for the Characteristic Polynomial, Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. ISSAC '07. Waterloo, Ontario, p.61, 2007.

J. M. Pollard, The fast Fourier transform in a finite field, Mathematics of Computation, vol.25, p.55, 1971.

D. Potts, G. Steidl, and M. Tasche, Fast algorithms for discrete polynomial transforms, Mathematics of Computation, vol.67, p.37, 1998.

O. Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography, Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05, p.85, 2005.

R. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, vol.21, issue.2, pp.120-126, 1978.

D. S. Roche, Space-and Time-efficient Polynomial Multiplication, Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation. ISSAC '09, pp.295-302, 2009.

D. S. Roche, What Can (and Can'T) We Do with Sparse Polynomials?, In: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. ISSAC '18, p.85, 2018.

K. Sakiyama, M. Knezevic, J. Fan, B. Preneel, and I. Verbauwhede, Tripartite modular multiplication, Press, Corrected Proof, vol.47, p.45, 2011.

B. D. Saunders, A. Storjohann, and G. Villard, Matrix Rank Certification, The Electronic Journal of Linear Algebra, vol.11, pp.16-23, 2004.
URL : https://hal.archives-ouvertes.fr/hal-02102007

A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inf, pp.139-144, 1971.

A. Schönhage, Fast multiplication of polynomials over fields of characteristic 2, Acta Inform, vol.7, pp.395-398, 1977.

A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, In: Computing, vol.7, pp.281-292, 1971.

J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, J. ACM, vol.27, p.20, 1980.

A. P. Shenoy and R. Kumaresan, Fast base extension using a redundant modulus in RNS, IEEE Transactions on Computers, vol.38, p.66, 1989.

N. P. Smart and D. Page, Parallel Cryptographic Arithmetic Using a Redundant Montgomery Representation, IEEE Transactions on Computers, vol.53, p.47, 2004.

C. Soulé, Perfects forms and the Vandiver conjecture, J. reine angew. Math, vol.517, pp.209-221, 1999.

A. Storjohann, Algorithms for Matrix Canonical Forms, p.67, 2000.

A. Storjohann, High-order lifting and integrality certification, J. Symbolic Comput, vol.36, pp.613-648, 2003.

A. Storjohann, Notes on computing minimal approximant bases, Challenges in Symbolic Computation Software. Dagstuhl Seminar Proceedings, p.68, 2006.

A. Storjohann and G. Villard, Computing the Rank and a Small Nullspace Basis of a Polynomial Matrix, ISSAC'05, pp.309-316, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00004832

A. Storjohann, The Shifted Number System for Fast Linear Algebra on Integer Matrices, J. Complex, vol.21, p.5, 2005.

V. Strassen, Gaussian elimination is not optimal, English. In: Numerische Mathematik, vol.13, pp.59-61, 1969.

N. S. Szabo and R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology, p.65, 1967.

J. Thaler, Time-Optimal Interactive Proofs for Circuit Evaluation, Advances in Cryptology -CRYPTO 2013, pp.71-89, 2013.

E. Thomé, Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann Algorithm, J. Symbolic Comput, vol.33, pp.757-775, 2002.

E. Thomé, Karatsuba multiplication with temporary space of size ? n, vol.29, p.25

A. L. Toom, The complexity of a scheme of functional elements realizing the multiplication of integers, Soviet Math, vol.3, pp.714-716, 1963.

C. Tran, Symbolic computing with the basis of Chebyshev's monic polynomials, p.38, 2015.

W. J. Turner, A Block Wiedemann Rank Algorithm, Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation. ISSAC '06, pp.332-339, 2006.

M. Van-barel and A. Bultheel, A general module theoretic framework for vector M-Padé and matrix rational interpolation, Numer. Algorithms, vol.3, p.76, 1992.

V. Williams, On some fine-grained questions in algorithms and complexity, Proceedings ICM, vol.3, p.36, 2018.

G. Villard, Further Analysis of Coppersmith's Block Wiedemann Algorithm for the Solution of Sparse Linear Systems (Extended Abstract), Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation. ISSAC '97, pp.32-39, 1997.

G. Villard, A study of Coppersmith's block Wiedemann algorithm using matrix polynomials, 1997.

G. Villard, Algorithmique en algèbre linéaire exacte". Habilitation à diriger des recherches, Université Claude Bernard Lyon, vol.1, 2003.

R. Vuduc, J. W. Demmel, and K. A. Yelick, OSKI: A library of automatically tuned sparse matrix kernels, Journal of Physics: Conference Series, vol.16, p.14, 2005.

R. C. Whaley, A. Petitet, and J. J. Dongarra, Automated empirical optimizations of software and the ATLAS project, Parallel Computing, vol.27, p.61, 2001.

D. H. Wiedemann, Solving Sparse Linear Equations Over Finite Fields, IEEE Transactions on Information Theory, vol.32, issue.1, p.1, 1986.

S. Winograd, On multiplication of 2×2 matrices, Linear Algebra and its Applications, vol.4, p.60, 1971.

W. Zhou, Fast Order Basis and Kernel Basis Computation and Related Problems, 2012.

W. Zhou and G. Labahn, Efficient Algorithms for Order Basis Computation, J. Symbolic Comput, vol.47, p.68, 2012.

W. Zhou, G. Labahn, and A. Storjohann, Computing Minimal Nullspace Bases, ISSAC'12, pp.366-373, 2012.

W. Zhou, G. Labahn, and A. Storjohann, A deterministic algorithm for inverting a polynomial matrix, J. Complexity, vol.31, pp.162-173, 2015.

R. Zippel, Probabilistic Algorithms for Sparse Polynomials, Symbolic and Algebraic Computation, vol.72, pp.216-226, 1979.