Linear Algebra on Parallel Structures Using Wiedemann Algorithm to Solve Discrete Logarithm Problem

References

• E. Kalton, “Analysis of coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems,” Math. Comput., Vol. 64, pp. 777–806, 1995.
   Web of Science ®Google Scholar
• W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. Inf. Theory, Vol. 22, no. 6, pp. 644–54, 1976. doi: 10.1109/TIT.1976.1055638
   Web of Science ®Google Scholar
• T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inf. Theory, Vol. 31, no. 4, pp. 469–72, 1985. doi: 10.1109/TIT.1985.1057074
   Web of Science ®Google Scholar
• Digital Signature Standard (DSS), “Federal Inf. Process. Stds. (NIST FIPS),” NIST, Supercedes Publication, Gaithersburg, MD, Rep. 186-4, 1994.
   Google Scholar
• D. Shanks, “Class number, a theory of factorization and general,” Proc. Symp. Pure Math, AMS, Vol. 20, pp. 415–40, 1971. doi: 10.1090/pspum/020/0316385
   Google Scholar
• S. Pohlig and M. Hellman, “An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,” IEEE Trans. Inf. Theory, Vol. 24, pp. 106–110, 1978. doi: 10.1109/TIT.1978.1055817
   Web of Science ®Google Scholar
• J. M. Pollard, “Monte carlo methods for index computation mod p,” Math. Comput., Vol. 32, no. 143, pp. 918–24, 1978.
   Web of Science ®Google Scholar
• A. M. Odlyzko, “Discrete logarithms in finite fields and their cryptographic significance,” Adv. Cryptol.-Euro. LNCS, Vol. 209, pp. 224–314, 1984. doi: 10.1007/3-540-39757-4_20
   Google Scholar
• A. Joux, “A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic,” in International Conference on Selected Areas in Cryptography, LNCS, 2013, pp. 355–79.
   Google Scholar
• R. Barbulescu, P. Gaudry, A. Joux and E. Thom, “A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic,” Preprint, 2014. Available: http://hal.inria.fr/hal-00835446.
   Google Scholar
• L. M. Adleman, “The function field sieve,” ANTS 2002, Vol. 877, pp. 108–121, 2002.
   Google Scholar
• A. Joux and R. Lercier, “Discrete logarithms in GF(p) (120 decimal digits),” 2001. Available: http://listserv.nodak.edu/archives/nmbrthry.html.
   Google Scholar
• A. Joux and R. Lercier, “The function field sieve is quite special,” ANTS, 2002, Vol. 2369, pp. 431–45, 2002.
   Google Scholar
• A. Joux and R. Lercier, “Discrete logarithms in GF(2607) and GF(2613),” 2005. Available: http://listserv.nodak.edu/archives/nmbrthry.html.
   Google Scholar
• R. Barbulescu, et al. “The relationship between some guy and cryptography,” Rump session of ECC, 2012. Available: http://ecc.2012.rump.cr.yp.to/.
   Google Scholar
• R. Barbulescu, “Discrete Logarithm in GF(2809) with FFS,” Public-Key Cryptography – PKC 2014. Lecture Notes in Computer Science, Vol. 8383, 2014.
   Google Scholar
• R. Barbulescu, “Selecting polynomials for the function field sieve,” Math. Comp., Vol. 84, pp. 2987–3012, 2015. doi: 10.1090/S0025-5718-2015-02940-8
   Web of Science ®Google Scholar
• J. Detrey, P. Gaudry and M. Videau, “Relation collection for the function field sieve,” in Proceedings of ARITH-21, 2013, pp. 201–10.
   Google Scholar
• C. Bouvier, “The Filtering step of discrete logarithm and integer factorization algorithms,” Preprint, 2013. Available: http://hal.inria.fr/hal-00734654.
   Google Scholar
• A. Joux and C. Pierrot, “Nearly sparse linear algebra and application to discrete logarithms computation,” preprint, Contemporary Developments in Finite Fields and Applications, 2016.
   Google Scholar
• B. A. LaMacchia and A. M. Odlyzko, “Solving large sparse linear systems over finite fields,” in Advances in cryptology-CRYPTO, LNCS, Vol. 537, A. Menezes and S. A. Vanstone, Eds. CA, 1990, pp. 109–133.
   Google Scholar
• D. Coppersmith, “Solving linear equation over GF(2): block lanczos algorithm,” Linear Algebra Appl., Vol. 192, pp. 33–60, 1993. doi: 10.1016/0024-3795(93)90235-G
   Web of Science ®Google Scholar
• C. Lanczos, “An iteration method for the solution of the eigenvalue problem of linear differential and integral operators,” J. Res. Natl. Bur. Stand., Vol. 45, pp. 255–82, 1950. doi: 10.6028/jres.045.026
   Google Scholar
• P. L. Montgomery, “A block lanczos algorithm for finding dependencies over GF(2),” Adv. Cryptol.-Euro. LNCS, Vol. 921, pp. 106–20, 1995. doi: 10.1007/3-540-49264-X_9
   Google Scholar
• D. Wiedemann, “Solving sparse linear equations over finite fields,” IEEE Tran. Inf. Theory, Vol. 32, no. 1, pp. 54–62, 1986. doi: 10.1109/TIT.1986.1057137
   Web of Science ®Google Scholar
• D. Coppersmith, “Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm,” Math. Comput., Vol. 62, no. 205, pp. 333–50, 1994.
   Web of Science ®Google Scholar
• O. Penninga, “Finding column dependencies in sparse systems over F2 by block Wiedemann,” Master's thesis, Centrum voor Wiskunde en Informatica, Amsterdam, 1998.
   Google Scholar
• A. Lobo, “Matrix free Linear System solving and applications to symbolic computation,” PhD thesis, Dept. of Comp. Sc., Rensselaer Polytech. Institute, Troy, NY, 1995.
   Google Scholar
• B. Beckermann and G. Labahn, “A uniform approach for hermite pad and simultaneous pad approximants and their matrix-type generalizations,” Numer. Algorithms., Vol. 3, pp. 45–54, 1992. doi: 10.1007/BF02141914
   Google Scholar
• H. Jeljeli, “Accelerating iterative SpMV for the discrete logarithm problem using GPUs,” LNCS, Vol. 9061, pp. 25–44, 2014.
   Google Scholar
• D. Page, “Parallel solution of sparse linear systems defined over GF(p),” University of Bristol, Bristol, 2004, Technical Report CSTR-05-003.
   Google Scholar
• L. T. Yang and R. P. Brent, “The parallel improved Lanczos method for integer factorization over finite fields for public key cryptosystems,” in ICPP Workshops, 2001, pp. 106–114.
   Google Scholar
• M. Peterson, “Parallel block Lanczos for solving large binary system” Master's thesis, Dept. of Mathematics, Texas Tech University, Lubbock, August 2006.
   Google Scholar
• R. P. Brent, “Vector and parallel algorithms for integer factorization,” in Third Australian Supercomputer Conference, 1990.
   Google Scholar
• R. P. Brent, “Parallel algorithms for integer factorization,” in Number Theory and Cryptography, Cambridge: Cambridge University Press, pp. 26–37, 1990.
   Google Scholar
• B. Schmidt, H. Aribowo and H. Dang, “Iterative sparse vector-matrix multiplication for integer factorization on GPU's,” in European Conference on Parallel Processing, 2011, pp. 413–24.
   Google Scholar
• L. T. Yang and R. P. Brent, “The parallel improved lanczos method for integer factorization over finite fields for public key cryptosystems,” in International Workshops on Parallel Processing, Manchester, 2001, pp. 106–114.
   Google Scholar
• G. H. Golub and C. F. van Loan, Matrix computations. chap. 9, Mathematical Sciences, The John Hopkins University Press, 1989.
   Google Scholar
• E. R. Berlekamp, “Nonbinary BCH decoding (Abstr.),” IEEE Trans. Inf. Theory, Vol. 14, no. 2, pp. 242, 1968. doi: 10.1109/TIT.1968.1054109
   Web of Science ®Google Scholar
• J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, Vol. 15, no. 1, pp. 122–27, 1969. doi: 10.1109/TIT.1969.1054260
   Web of Science ®Google Scholar
• J. Brillhart, et al. “Factorizations of bn±1, b = 2, 3, 5, 6, 7, 10, 11, 12 upto high powers,” in Contemporary Mathematics, 3rd ed. Vol. 22, AMS, 2002.
   Google Scholar
• CADO-NFS Library. Available: http://cado-nfs.gforge.inria.fr/.
   Google Scholar