49 3.2.1 Nature des coefficients, p.51 ,
calculer les n termes additifs prend O(n(2n ? 1)k 2 ) ,
Le système MRS, aussi connu sous le nom de bases de Cantor, est un système de représentation de nombres à numération de position ,
m n ) et un entier x, la représentation MRS de x est la liste (r 1 , r 2 , . . . , r n ) telle que x = r 1 + r 2 m 1 + r 3 m 2 m 1 + · · · + r n m n?1 m n?2 ,
A Subexponential Algorithm for Discrete Logarithms over All Finite Fields Function Field Sieve Method for Discrete Logarithms over Finite Fields, Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology -CRYPTO '93, pp.147-158, 1994. ,
Computing Discrete Logarithms in F 3 6 * 137 and F 3 6 * 163 Using Magma A subexponential algorithm for the discrete logarithm problem with applications to cryptography, 20th Annual Symposium on Foundations of Computer Science (FOCS '79), pp.3-22, 1979. ,
Finding ECM-friendly curves through a study of Galois properties ANTS-X 10th ,
Romine, and H. Van der Vorst. Templates for the Solution of Linear Systems : Building Blocks for Iterative Methods, Algorithmic Number Theory Symposium, p.68, 1994. ,
The relationship between some guy and cryptography. ECC2012 rump session talk (humoristic), pp.2012-119 ,
Discrete logarithm in GF(2 809 ) with FFS. E-mail to the NM- BRTHRY mailing list, p.119, 2013. ,
Exact Sparse Matrix-Vector Multiplication on GPU's and Multicore Architectures, Discrete logarithm in GF(2 809 ) with FFS. PKC 2014 Bajard, L-S. Didier, and P. Kornerup. An RNS Montgomery Modular Multiplication Algorithm. IEEE TRANSACTIONS ON COMPUTERS, pp.221-238, 1998. ,
A New Euclidean Division Algorithm for Residue Number Systems Journal of VLSI signal processing systems for signal, image and video technology Identity-Based Encryption from the Weil Pairing Advances in Cryptology ? CRYPTO, Lecture Notes in Computer Science, vol.2139, issue.73, pp.167-178, 1998. ,
? 160 digits. E-mail to the NMBRTHRY mailing list Discrete logarithms in GF(p 2 ) ? 160 digits. E-mail to the NMBRTHRY mailing list ; http://listserv. nodak.edu/archives/nmbrthry.html Improving NFS for the discrete logarithm problem in non-prime finite fields Discrete logarithms in GF(p) ? 180 digits. E-mail to the NMBRTHRY mailing list A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic Fast solution of toeplitz systems of equations and computation of Padé approximants, Discrete logarithms in GF 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lecture Notes in Computer Sciences Advances in Cryptology ? EUROCRYPT 2014, pp.27-28, 1980. ,
Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, p.73, 1993. ,
A Uniform Approach for the Fast Computation of Matrix-Type Pad?? Approximants, Boneh, B. Lynn, and H. Shacham. Short Signatures from the Weil Pairing. Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security : Advances in Cryptology, pp.804-823, 1994. ,
DOI : 10.1137/S0895479892230031
Abstract, LMS Journal of Computation and Mathematics, vol.17, issue.A, pp.147-168, 2014. ,
DOI : 10.1017/CBO9781139856065
Algorithms of discrete logarithm in finite fields, p.120, 1920. ,
Selecting polynomials for the Function Field Sieve, p.120, 1303. ,
Algebraic coding theory Multidigit modular multiplication with the explicit chinese remainder theorem, pp.55-97, 1968. ,
The Filtering Step of Discrete Logarithm and Integer Factorization Algorithms, pp.48-120 ,
CADO-NFS : Crible Algébrique : Distribution, Optimisation -Number Field Sieve, pp.69-71 ,
CUDA Programming Guide Version 6.5. http://docs. nvidia.com/cuda/cuda-c-programming-guide, p.103, 2014. ,
On the number field sieve integer factorization algorithm Fast evaluation of logarithms in fields of characteristic two Information Theory Block Lanczos Algorithm. Linear Algebra and its Applications Pairing-based cryptography : A survey, Cusp : Generic Parallel Algorithms for Sparse Matrix and Graph ComputationsCop94] D. Coppersmith. Solving Homogeneous Linear Equations over GF(2) via Block Wiedemann Algorithm. Mathematics of ComputationDGV13] J. Detrey, P. Gaudry, and M. Videau. Relation Collection for the Function Field Sieve. Computer Arithmetic (ARITH), 2013 21st IEEE Symposium on Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, pp.73-121, 1869. ,
A minimal realization algorithm for matrix sequences. Automatic Control, IEEE Transactions on, vol.19, issue.1, pp.31-38, 1974. ,
A floating-point technique for extending the available precision ,
On the discrete logarithm problem in elliptic curves On Randomized Lanczos Algorithms Performance Evaluation of Sparse Matrix Multiplication Kernels on Intel Xeon Phi A public-key cryptosystem and a signature scheme based on discrete logarithms, Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation - ISSAC '97, pp.75-104, 1985. ,
FFLAS-FFPACK : Finite Field Linear Algebra Subroutines / Package. v2.0.0, http://linalg.org/projects/fflas-ffpack, 2014, pp.69-53, 1967. ,
A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves, Mathematics of computation, pp.865-874, 1994. ,
Whitepaper NVIDIA's Next Generation CUDA Compute Architecture : Fermi Nondeterministic Algorithms Some Computer Organizations and Their Effectiveness, Journal ACM IEEE Transactions on Computers, vol.1421, issue.9, pp.27-636, 1967. ,
On the Function Field Sieve and the Impact of Higher Splitting Probabilities, Advances in Cryptology ? CRYPTO 2013, pp.109-128, 2013. ,
DOI : 10.1007/978-3-642-40084-1_7
Performance evaluation of the sparse matrix-vector multiplication on modern architectures, The Journal of Supercomputing, vol.41, issue.6, pp.36-77, 2009. ,
DOI : 10.1007/s11227-008-0251-8
Generating Optimized Sparse Matrix Vector Product over Finite Fields New approach to integer division in residue number systems, Proc. ICMS 2014 : Fourth International Congress on Mathematical Software IEEE Symposium on Computer Arithmetic The Residue Number System. Papers Presented at the the Discrete logarithms in gf(p) using the number field sieve. SIAM J. Discrete Math, pp.44-685, 1959. ,
Integer division in residue number systems, IEEE Transactions on Computers, vol.44, issue.8, pp.983-989, 1952. ,
DOI : 10.1109/12.403714
Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the gaussian integer method, Mathematics of Computation, vol.72, issue.242 ,
DOI : 10.1090/S0025-5718-02-01482-5
URL : https://hal.archives-ouvertes.fr/hal-01102016
Discrete logarithms in GF(2 607 ) and GF(2 613 ) Email to the NMBRTHRY mailing list ; http://listserv.nodak.edu/archives/ nmbrthry.html Joux and C. Pierrot. The Special Number Field Sieve in F p n , Application to Pairing-Friendly Constructions, Joux and C. Pierrot. Discrete logarithm record in characteristic 3, GF(3 5×479 ) a 3796-bit field. E-mail to the NMBRTHRY mailing list, pp.953-967, 1922. ,
Accelerating Iterative SpMV for Discrete Logarithm Problem Using GPUs, WAIFI, vol.2014, issue.89, pp.25-44, 2014. ,
Resolution of Linear Algebra for the Discrete Logarithm Problem Using GPU and Multi-core Architectures. Euro-Par 2014 Parallel Processing A one round protocol for tripartite Diffie-Hellman A One Round Protocol for Tripartite Diffie-Hellman, Proceedings of the 4th International Symposium on Algorithmic Number TheoryJou12] A. Joux. Discrete Logarithms in a 1175-bit Finite Field. E-mail to the NMBRTHRY mailing list, pp.764-775, 1922. ,
Faster Index Calculus for the Medium Prime Case Application to 1175-bit and 1425-bit Finite Fields, Advances in Cryptology ? EUROCRYPT 2013, pp.177-193, 2013. ,
A New Index Calculus Algorithm with Complexity, )) in Small Characteristic. Selected Areas in Cryptography ? SAC 2013, pp.355-379, 2014. ,
257 ) 24 )]. E-mail to the NM- BRTHRY mailing list ; http://listserv.nodak.edu/archives/nmbrthry.html Discrete Logarithms in a 1425-bit Finite Field. E-mail to the NM- BRTHRY mailing list, Discrete logarithms in GF(2 6168 ) [=GF Parallel Modular Multiplication Algorithm in Residue Number System. Parallel Processing and Applied Mathematics, pp.1028-1033, 2004. ,
Whitepaper NVIDIA's Next Generation CUDA Compute Architecture : Fermi. http://www.nvidia.com/content/PDF/kepler/ NVIDIA-kepler-GK110-Architecture-Whitepaper Discrete logarithms in GF(p) ? 160 digits. E-mail to the NM- BRTHRY mailing list, p.127, 2007. ,
Polynomial Selection. CADO workshop on integer factorization, p.127, 2008. ,
Discrete Logarithms in GF E-mail to the NMBRTHRY mailing list, p.127, 1279. ,
The analysis of algorithms An Introduction to CUDA-Aware MPI. Post in NVI- DIA Developer Zone, http://devblogs.nvidia.com/parallelforall/ introduction-cuda-aware-mpi, Proc. International Congress of MathematiciansKra13b] J. Kraus. Benchmarking CUDA-Aware MPI. Post in NVI- DIA Developer Zone Lu and J. S. Chiang. A Novel Division Algorithm for the Residue Number System, pp.269-274, 1970. ,
Basic linear algebra subprograms for FORTRAN usage Solving large sparse linear systems over finite fields Advances in Cryptology -CRYPTO '90, ACM Transactions on Mathematical Software, vol.5, issue.537, pp.308-323, 1979. ,
CUDA Warps and Occupancy, GPU Computing Webinar, p.37, 2011. ,
Efficient Sparse Matrix-vector Multiplication on x86-based Many-core Processors, Proceedings of the 27th International ACM Conference on International Conference on Supercomputing -ICS '13, pp.273-282, 2013. ,
Solution of Systems of Linear Equations by Minimized Iterations ,
Factoring Integers with Elliptic Curves, The Annals of Mathematics, vol.126, issue.3, pp.33-53, 1952. ,
DOI : 10.2307/1971363
Exact computational linear algebra Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Transactions on Information Theory, pp.69-163, 1993. ,
A new traitor tracing, IEICE Trans. Fundamentals, issue.2, pp.481-484, 2002. ,
A Fully Asynchronous Multifrontal Solver Using Distributed Dynamic Scheduling, SIAM Journal on Matrix Analysis and Applications, vol.23, issue.1, pp.15-41, 2001. ,
Hybrid scheduling for the parallel solution of linear systems, Maurer and S. Wolf. Diffie-Hellman Oracles. Advances in Cryptology - CRYPTO 96, pp.136-156, 1996. ,
DOI : 10.1016/j.parco.2005.07.004
URL : https://hal.archives-ouvertes.fr/hal-00358623
Shift-register synthesis and BCH decoding, Mau94] U. M. Maurer. Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms. Advances in Cryptology -CRYPTO 94, pp.122-127, 1969. ,
Improving digital computer performance using residue number theory, IEEE Transactions on Electronic Computers, EC, vol.13, issue.2, pp.93-101, 0100. ,
A Block Lanczos Algorithm for Finding Dependencies over GF(2) Advances in Cryptology ? EUROCRYPT '95, Pages 106-120, p.55, 1995. ,
Scalable Parallel Programming with CUDA. Queue [Nec94] V. I. Nechaev. Complexity of a determinate algorithm for the discrete logarithm, Mathematical Notes, vol.55, issue.2 11, pp.40-53, 1994. ,
An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, vol.27, pp.24106-110, 1978. ,
Efficient Inter-node MPI Communication Using GPUDirect RDMA for InfiniBand Clusters with NVIDIA GPU, 42nd International Conference on Parallel Processing (ICPP), pp.80-89, 2013. ,
Modulo Reduction in Residue Number Systems. IIG- Report-Series : Institute für Informationsverarbeitung Reduction of Huge, Sparse Matrices over Finite Fields via Created Catastrophes, Experimental Mathematics, pp.97-89, 1992. ,
Numerical Recipes in C : The Art of Scientific Computing, p.53, 1992. ,
36 [PTXb] NVIDIA Corporation Inline PTX Assembly in CUDA. http://docs.nvidia. com/cuda/pdf/Inline_PTX_Assembly.pdf A monte carlo method for factorization Monte Carlo methods for Index Computation (mod p) The lattice sieve. The development of the number field sieve Analysis and comparison of some integer factoring algorithms, BIT Numerical Mathematics Mathematics of Computation, vol.36, issue.12, pp.331-334, 1975. ,
14 [Pom84] C. Pomerance. The quadratic sieve factoring algorithm Advances in Cryptology Hybrid Parallel Programming Hybrid MPI and OpenMP Parallel Programming. Tutorial at SC13, http://openmp.org/ sc13/HybridPP_Slides.pdf, Mathematisch Centrum Computational Methods in Number Theory Proceedings of Eurocrypt 84 Aribowo, and H-V. Dang. Iterative Sparse Matrix-Vector Multiplication for Integer Factorization on GPUs. Euro-Par 2011 Parallel Processing, pp.89-139, 1982. ,
Scan Primitives for GPU Computing. Graphics Hardware, p.73, 2007. ,
CUDA by Example : An Introduction to General- Purpose GPU Programming Fast Base Extension Using a Redundant Modulus in RNS Cryptosystems based on pairings. SICS. Symposium on cryptography and information security Discrete logarithms : The effectiveness of the index calculus method Algorithmic Number Theory, IEEE Transactions on Computers, issue.11SWD96, pp.27-292, 1989. ,
Peer-to-Peer & Unified Virtual Addressing, CUDA Webinar, pp.1267-1283, 2000. ,
Special Prime Numbers and Discrete Logs in Finite Prime Fields ,
Lower bounds for discrete logarithms and related problems Advances in Cryptology ? EUROCRYPT '97 Efficient method for magnitude comparison in rns based on two pairs of conjugate moduli Algorithmes de Calcul de Logarithmes Discrets dans les Corps Finis, Proceedings of the 18th IEEE Symposium on Computer ArithmeticTho02] E. Thomé. Subquadratic Computation of Vector Generating Polynomials and Improvement of the Block Wiedemann AlgorithmTho12a] E. Thomé. Block Wiedemann implementation in CADO-NFS. Exposé dans le séminaire Efficient Linear Algebra for Gröbner Basis Computations, pp.363-377, 1969. ,
The sparse matrix vector product on GPU A study of Coppersmith's block Wiedemann algorithm using matrix polynomials Better Performance at Lower Occupancy, LMC-IMAG, vol.71, issue.36, pp.77-56, 1997. ,
Optimization of Sparse Matrix-vector Multiplication on Emerging Multicore Platforms, Proceedings of the 2007 ACM/IEEE Conference on Supercomputing -SC '07, pp.1-3812, 2007. ,
A Handbook of Numerical Matrix Inversion and Solution of Linear Equations, p.53, 1968. ,
Solving Sparse Linear Equations over Finite Fields, IEEE Transactions on Information Theory, vol.53, pp.54-62, 1986. ,