Abstract
There are presented deterministic P systems with active membranes which are able to solve the Integer Factorization Problem in a polynomial time, which is the main result of the paper. There is introduced a class of programs for the description and correct implementation of algorithms of elementary number theory in nonstandard computing systems, especially in P systems with active membranes. By using some of these programs there is achieved the main result.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Brainerd, W. S., Landweber, L. H. (1974): Theory of Computation. New York
Koblitz, N. (1998): Algebraic Aspects of Cryptography. Berlin
Lenstra, A. K., Lenstra, H. W., Jr. (1993): The Development of the Number Field Sieve. Lecture Notes in Mathematics, 1554, Berlin
Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996): Handbook of Applied Cryptography. CRC Press, Boca Raton
Meyer, A. R., Ritchie, D. M. (1967): The complexity of loop programs. Proceedings of the ACM National Meeting, ACM Pub. P-67, 465–469
Papadimitriou, Ch. P. (1994): Computational Complexity. Reading, Massachusetts
Păun, Gh. (2000a): P-Systems with Active Membranes: Attacking NP Complete Problems. Journal of Automata, Languages and Combinatorics, 6 (2000), 75–90
Păun, Gh. (2000b): Computing with Membranes. Journal of Computer and System Sciences, 61 (2000) 108–143
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Obtułowicz, A. (2001). On P Systems with Active Membranes Solving the Integer Factorization Problem in a Polynomial Time. In: Calude, C.S., PĂun, G., Rozenberg, G., Salomaa, A. (eds) Multiset Processing. WMC 2000. Lecture Notes in Computer Science, vol 2235. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45523-X_14
Download citation
DOI: https://doi.org/10.1007/3-540-45523-X_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43063-6
Online ISBN: 978-3-540-45523-3
eBook Packages: Springer Book Archive