International Journal of Theoretical and Applied Mathematics

| Peer-Reviewed |

New Pragmatic Algorithms to Improve Factoring of Large Numbers

Received: 28 September 2017    Accepted: 13 November 2017    Published: 05 December 2017
Views:       Downloads:

Share This Article

Abstract

Rivest, Shamir, Adleman, RSA algorithm is a popular public key cryptosystem and is known to be secure, however, this fact relies on the difficulty of factoring large numbers. No algorithm has been published that can factor all integers in polynomial time. This paper proposes a new function that can be used to improve the process of factoring integer numbers. It gets the factor faster than known methods. By making use of such proposed function, corresponding two algorithms are proposed and pseudocoded. The utilization of these algorithms along with the basics of the theory of numbers led to three other new factoring algorithms. The five algorithms are implemented and verified using Python Language. The tabulated results that represent the time of factorization versus the number of digits of the large number have indicated the applicability of the last three algorithms.

DOI 10.11648/j.ijtam.20170306.14
Published in International Journal of Theoretical and Applied Mathematics (Volume 3, Issue 6, December 2017)
Page(s) 199-202
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

RSA, Large Number Factorization, Number Field Sieve, Greatest Common Divisor (GCD)

References
[1] Mohammed Z. Abd El-Mageed and Hassan M. H. Hussein, An Effective GA Fitness Function To Guide Heuristic Search Integer Factorization, Paper Accepted for GJTAMS Paper Code: 5183.
[2] Song Y. Yan, Computational Number Theory, Higher Education Press, WILY, 2013.
[3] R. L. Rivest, A. Shamir, L. Adleman: A method for obtaining digital signatures and public-key cryptosystems. Communications of the Association for Computing Machinery, 21 (1978).
[4] H. Cohen, A Course in Computational Algebraic Number Theory, Springer-Verlag, Berlin, Heidelberg, New-York, 1996.
[5] A. K. Lenstra and H. W. Lenstra, Algorithms in Number Ttheory, Handbook of theoretical computer science, J. Van Leeuwen, A. Mayer, M. Nivat, M. Patterson and D. Perrin (eds.), Elsevier, 1990.
[6] Song Y. Yan, Cryptanalytic Attacks on RSA, Springer Science+Business Media, 2008.
[7] Song Y. Yan, computational number theory, Higher Education Press, WILY, 2013.
[8] A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349.
[9] J. Chu, The beginning of the end for encryption schemes, MIT News, March, 2016.
[10] L. Zyga, Quantum physics offers new way to factor numbers, Phys.org, November, 2016.
[11] R. Dridia and H. Alghassib, Prime factorization using quantum annealing and computational algebraic geometry, NCBI, 2017.
Author Information
  • Department of Computer Since, Faculty of Engineering, Al-Zahra University, Cairo Egypt

  • Research Development Center, National Defense Council, Cairo, Egypt

Cite This Article
  • APA Style

    Mohamed Zaki Abd El-Mageed, Hassan Hussein. (2017). New Pragmatic Algorithms to Improve Factoring of Large Numbers. International Journal of Theoretical and Applied Mathematics, 3(6), 199-202. https://doi.org/10.11648/j.ijtam.20170306.14

    Copy | Download

    ACS Style

    Mohamed Zaki Abd El-Mageed; Hassan Hussein. New Pragmatic Algorithms to Improve Factoring of Large Numbers. Int. J. Theor. Appl. Math. 2017, 3(6), 199-202. doi: 10.11648/j.ijtam.20170306.14

    Copy | Download

    AMA Style

    Mohamed Zaki Abd El-Mageed, Hassan Hussein. New Pragmatic Algorithms to Improve Factoring of Large Numbers. Int J Theor Appl Math. 2017;3(6):199-202. doi: 10.11648/j.ijtam.20170306.14

    Copy | Download

  • @article{10.11648/j.ijtam.20170306.14,
      author = {Mohamed Zaki Abd El-Mageed and Hassan Hussein},
      title = {New Pragmatic Algorithms to Improve Factoring of Large Numbers},
      journal = {International Journal of Theoretical and Applied Mathematics},
      volume = {3},
      number = {6},
      pages = {199-202},
      doi = {10.11648/j.ijtam.20170306.14},
      url = {https://doi.org/10.11648/j.ijtam.20170306.14},
      eprint = {https://download.sciencepg.com/pdf/10.11648.j.ijtam.20170306.14},
      abstract = {Rivest, Shamir, Adleman, RSA algorithm is a popular public key cryptosystem and is known to be secure, however, this fact relies on the difficulty of factoring large numbers. No algorithm has been published that can factor all integers in polynomial time. This paper proposes a new function that can be used to improve the process of factoring integer numbers. It gets the factor faster than known methods. By making use of such proposed function, corresponding two algorithms are proposed and pseudocoded. The utilization of these algorithms along with the basics of the theory of numbers led to three other new factoring algorithms. The five algorithms are implemented and verified using Python Language. The tabulated results that represent the time of factorization versus the number of digits of the large number have indicated the applicability of the last three algorithms.},
     year = {2017}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - New Pragmatic Algorithms to Improve Factoring of Large Numbers
    AU  - Mohamed Zaki Abd El-Mageed
    AU  - Hassan Hussein
    Y1  - 2017/12/05
    PY  - 2017
    N1  - https://doi.org/10.11648/j.ijtam.20170306.14
    DO  - 10.11648/j.ijtam.20170306.14
    T2  - International Journal of Theoretical and Applied Mathematics
    JF  - International Journal of Theoretical and Applied Mathematics
    JO  - International Journal of Theoretical and Applied Mathematics
    SP  - 199
    EP  - 202
    PB  - Science Publishing Group
    SN  - 2575-5080
    UR  - https://doi.org/10.11648/j.ijtam.20170306.14
    AB  - Rivest, Shamir, Adleman, RSA algorithm is a popular public key cryptosystem and is known to be secure, however, this fact relies on the difficulty of factoring large numbers. No algorithm has been published that can factor all integers in polynomial time. This paper proposes a new function that can be used to improve the process of factoring integer numbers. It gets the factor faster than known methods. By making use of such proposed function, corresponding two algorithms are proposed and pseudocoded. The utilization of these algorithms along with the basics of the theory of numbers led to three other new factoring algorithms. The five algorithms are implemented and verified using Python Language. The tabulated results that represent the time of factorization versus the number of digits of the large number have indicated the applicability of the last three algorithms.
    VL  - 3
    IS  - 6
    ER  - 

    Copy | Download

  • Sections