P System Design for Integer Factorization
Source abstract
Abstract
Membrane computing is a natural computing branch inspired by the structure of biological cells. The mathematical abstract model of a membrane computing system is called a P System, which is one of the main topics in membrane computing research for the design and verification of a P System. Integer factorization is still a world-class problem and a very important research direction. If a fast method can be found to solve the integer factorization problem, several important cryptographic systems including the RSA public key algorithm will be broken. The aim of this paper is to design a P System capable of implementing integer decomposition, taking advantage of the characteristics of parallelism of P Systems. We construct a process with a main goal to study the modal exponential function f(x) = ax mod N and explore the possible periodic behavior for different values of a. We attempt to compute nontrivial prime factors by the period found and constrain the operation of the P System in polynomial time.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: DNA and Biological Computing · Advanced biosensing and bioanalysis techniques · semigroups and automata theory
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, China
College of Computer Science, Chongqing University, Chongqing 400044, China
Funding
Action Plan for High-quality Development of Postgraduate Education of Chongqing University of Technology · Humanities and Social Sciences Research Key Project of Chongqing Municipal Education Commission
References (24)
Show source-provided references
1. Computing with Membranes10.1006/jcss.1999.1693 ↗
2. Cell-like Spiking Neural P Systems10.1016/j.tcs.2015.12.038 ↗
3. Ciobanu, G., Păun, G., and Pérez-Jiménez, M.J. (2005). Applications of Membrane Computing, Springer.10.1007/3-540-29937-8 ↗
4. Tissue P Systems10.1016/S0304-3975(02)00659-X ↗
5. Spiking Neural P Systems
6. Universality Results for P Systems Based on Brane Calculi Operations10.1016/j.tcs.2006.10.016 ↗
7. Ibarra, O.H., and Paun, G. (2006). Membrane Computing: A General View. Ann Eur Acad Sci. EAS, 83–101. Available online: https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=9095c58d493590de047aa4af8f4ceeba8043dca2.
8. Modeling Framework for Membrane Computing in Biological Systems: Evaluation with a Case Study10.1016/j.jocs.2013.12.004 ↗
9. A New Membrane Algorithm Using the Rules of Particle Swarm Optimization Incorporated within the Framework of Cell-like P Systems to Solve Sudoku10.1016/j.asoc.2016.03.020 ↗
10. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems10.1145/359340.359342 ↗
11. Briggs, M.E. (1998). An Introduction to the General Number Field Sieve. [Ph.D. Thesis, Virginia Tech]. Available online: http://hdl.handle.net/10919/36618.
12. Gupta, S., and Paul, G. (2009). Revisiting Fermat’s Factorization for the RSA Modulus. arXiv.
13. Solving the Factorization Problem with P Systems10.1080/10020070708541025 ↗
14. Arithmetic Operations and Factorization Using Asynchronous P Systems10.15803/ijnc.2.2_217 ↗
15. Calude, C.S., Păun, G., Rozenberg, G., and Salomaa, A. (2001). Proceedings of the Multiset Processing, Springer.10.1007/3-540-45523-X ↗
16. Zhang, X., Niu, Y., Pan, L., and Pérez-Jiménez, M.J. (2014). Linear Time Solution to Prime Factorization by Tissue P Systems with Cell Division. Nat. Comput. Simul. Knowl. Discov., 207–220.10.4018/978-1-4666-4253-9.ch014 ↗
17. A Uniform Solution to Integer Factorization Using Time-Free Spiking Neural P System10.1007/s00521-014-1799-2 ↗
18. Shor, P.W. (1994, January 20–22). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA.
19. Computing with Membranes (P Systems): A Variant10.1142/S0129054100000090 ↗
20. Membrane Systems with Promoters/Inhibitors10.1007/s00236-002-0090-7 ↗
21. Is the Euclidean Algorithm Optimal Among Its Peers?10.2178/bsl/1102022663 ↗
22. UPSimulator: A General P System Simulator10.1016/j.knosys.2019.01.013 ↗
23. Li, Z., and Gasarch, W. (2021). An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm. arXiv.
24. The Space Complexity Analysis in the General Number Field Sieve Integer Factorization10.1016/j.tcs.2016.03.028 ↗