Factoring Polynomials Using Elliptic Curves

  • Authors

    • A. Uma Maheswari
    • Prabha Durairaj
    2018-10-02
    https://doi.org/10.14419/ijet.v7i4.10.20819
  • Elliptic curve, polynomial factorization over finite fields, irreducible polynomial.

  • Abstract

    This paper presents a probabilistic algorithm to factor polynomials over finite fields using elliptic curves. The success of the algorithm depends on the initial choice of elliptic curve parameters. The algorithm is illustrated through numerical examples.

     

  • References

    1. [1] Rudolf Lidl and Harald Niederreiter, “Introduction to Finite fields and their applications,†Cambridge University Press, 1986, pp 299.

      [2] B.Chor and R.Rivest, “A knapsack-type public key cryptosystem based on arithmetic in finite fields,†Advances in Cryptology- Crypto’84, Springer-Verlag 1985, 54-65; revised version in IEEE Transactions on Information Theory IT-34 ,1988, 901-909.

      [3] A.M Odlyzko, “Discrete logarithms in finite fields and their cryptographic significance,†Advances in cryptology- Eurocrypt 1984, Lecture Notes in Comput. Sci. vol.209, Springer-verlag, Berlin 1985, 224-314.

      [4] E.R.Berlekamp, “Factoring polynomials over Large Finite fields,†Mathematics of computation, volume 24, Number 111, July 1970, 713-733.

      [5] Cantor, D.G and Zassenhaus H, “A new Algorithm for factoring polynomials over finite fields,†Mathematics of Computation, 36, 1981, 587-592 .

      [6] Berlekamp, E.R, “Algebraic Coding Theory,†Mc-Graw Hill, New York, 1968.

      [7] Knuth, D.E, “The Art of Computer Programming,†vol.2, Seminumerical Algorithms, edition, Addison-Wesley, Reading, Mass., 1981.

      [8] McEliece, “R.J, Factorization of polynomials over finite fields,†Math.comp.23, 1969, 861-867.

      [9] Rabin, M.O, “Probabilistic Algorithms in finite fields,†SIAM J. Computing, 9, 1980, 273-280.

      [10] Zassenhaus, H, “On Hensel factorization I,†J.Number Theory 1, 1969, 291-311.

      [11] H.W.Lenstra, Jr. “Factoring Integers with Elliptic Curvesâ€, The Annals of Mathematics, Second series, Volume 126, Issue 3 (Nov. 1987), 649-673.

      [12] Lawrence C. Washington, “Elliptic Curves, Number Theory and Cryptography,†Second Edition, 2008, Taylor Francis group, pp 65-71.

      [13] H.W.Lenstra, Jr. ‘Elliptic Curves and Number Theoretic Algorithms,†Proceedings of the International Congress of Mathematicians, vol.1,2 (Berkley, Califn, 1986), pp 99-120.

      [14] J.H. Silverman, “The Arithmetic of Elliptic curves, Graduate Texts in Mathematics, vol.106, Springer-verlag, New York, 1986.

      [15] Lawrence C. Washington, “Elliptic Curves, Number Theory and Cryptography,†Second Edition, 2008, Taylor & Francis group, pp 70.

      [16] Neal Koblitz “A Course in Number Theory and Cryptography,†Second edition, Springer, 1994, pp 193-195.

  • Downloads

  • How to Cite

    Uma Maheswari, A., & Durairaj, P. (2018). Factoring Polynomials Using Elliptic Curves. International Journal of Engineering & Technology, 7(4.10), 112-117. https://doi.org/10.14419/ijet.v7i4.10.20819

    Received date: 2018-10-03

    Accepted date: 2018-10-03

    Published date: 2018-10-02