New Pragmatic Algorithms to Improve Factoring of Large Numbers

Mohamed Zaki Abd El-Mageed; Hassan Hussein

doi:doi:10.11648/j.ijtam.20170306.14

| Peer-Reviewed

New Pragmatic Algorithms to Improve Factoring of Large Numbers

Mohamed Zaki Abd El-Mageed, Hassan Hussein

Published in International Journal of Theoretical and Applied Mathematics (Volume 3, Issue 6)

Received: 28 September 2017 Accepted: 13 November 2017 Published: 5 December 2017

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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.

Published in	International Journal of Theoretical and Applied Mathematics (Volume 3, Issue 6)
DOI	10.11648/j.ijtam.20170306.14
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), 2017. 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.

Cite This Article

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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

Author Information

Mohamed Zaki Abd El-Mageed

Department of Computer Since, Faculty of Engineering, Al-Zahra University, Cairo Egypt
Hassan Hussein

Research Development Center, National Defense Council, Cairo, Egypt

Download PDF

Sections

Plain Text BibTeX RIS

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://article.sciencepublishinggroup.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