# P System Design for Integer Factorization
## 1 Introduction  
Membrane computing is a computational model abstracted from the function and structure of biological cells and is formally defined as a P system, first proposed by [PERSON] in 1998 [1]. It is a novel and efficient parallel computing model based on the observation and abstraction of biological cell properties and their internal biochemical reactions. Membrane computation models are divided into three categories: the cell-like P system [2, 3], the tissue P system [4], and the neural P system [5]. Cell-like P systems are the most fundamental membrane systems and the first P systems to be proposed. The Cell-like P system is a computational model that simulates the structure and function of cells with parallel and non-deterministic characteristics and it is widely used in the research of computational theory and related fields. The tissue-type P system is a computational model inspired by protein channels that have intercellular communication, which processes symbols in a network of cells in a multiset rewriting fashion. Each cell has a finite state memory, handles multiple sets of symbolic pulses, and can send pulses (\"excitation\") to neighboring cells. This network of cells proved to be quite powerful; even when using a small number of cells, they could simulate a Turing machine. Neural P systems are a class of pulsatile neural P systems (referred to as SN P systems) based on the idea of spiking neurons in neurobiology, in which time (when a neuron fires and/or spikes) plays an important role. For example, the result of the calculation is the time between the moments when the specified neuron discharges spikes. Membrane computing has been shown to be theoretically Turing-complete [6], i.e., it can be used to solve any Turing-computable problem. The advantage of membrane computing is that it is highly parallel, fault-tolerant, and scalable [7] and can be applied to various fields such as biology, mathematics, and computer science. In the paper [8],a membrane computing framework based on biological systems was proposed, and the proposed framework was simulated and evaluated to verify the superiority of membrane computing methods. The literature [9] combined cell-like P Systems with particle swarm optimization algorithms and used them for solving Sudoku problems. Integer factorization, also known as prime factorization, is a classical mathematical problem that aims to represent a positive integer as a product of prime factors. Given two large prime factors, it is easy to find their product, but it is hard to get a result in the opposite task. This is one of the key problems of modern cryptographic systems. If a fast solution to the integer decomposition problem could be found, several important cryptosystems would be broken, including the RSA Public-Key Cryptosystems [10] and the Blum Blum Shub random number generator. Researchers have been making related attempts, such as GNFS [11] and Fermat factorization [12]. The use of a P system for integer decomposition was studied by [PERSON] [13] et al., who proposed three P systems for arithmetic operations. The first P system implements the addition operation to compute two m-bit binary numbers in \(O(m)\) steps, and the second P system completes the multiplication operation to compute two m-bit binary numbers in \(O(m\text{log}\ m)\) steps. The third P system implements the first two P systems as subsystems to complete the factorization of m-bit natural numbers in \(O(m\text{log}\ m)\) steps. [PERSON] [14] et al. considered asynchronous parallelism in membrane computation and proposed an asynchronous P system that performs two basic arithmetic operations and factorization. [PERSON] [15] proposed a P system with an active membrane that is capable of polynomial time to solve integer factorization problems. In addition, [PERSON] [16] et al. provided a linear time P system for the prime factorization problem in the framework of a tissue P system with cell division. [PERSON] [17] et al.