The Factorization Problem: A New Approach Through Membrane Systems

The factorization problem (given a natural number which is the product of two prime numbers, find its decomposition) is conjectured to be intractable and for that it has been used as the key to have secure current cryptosystems. Due to its relevance, this problem has been studied in various computational paradigms, in particular in membrane computing. In this framework, recognizer P systems were introduced to deal with decision problems, that is, problems whose solution/answer is either "yes" or "no". The factorization problem is a search problem (also called function problem), where the question is to identify/find one solution to the set of possible solutions associated with each instance. In this work, membrane systems computing partial functions are shown to (e