# P System Design for Integer Factorization
## 2 Foundation
### Extended P System
(**a**): The first stage splits the process of computing the sub-task membranes of the different values of \(a\); (**b**): The second stage shows the execution flow of calculating the membrane corresponding to a certain \(a\). The value of \(N\) in \(\xi^{N}\) is the number to decompose, not the exponential order. The value of \(a\) in \(z^{a-1}\) will not be greater than \(N\) itself (the number of digits to be decomposed \(N\)). The \({}^{*}\) in the figure represents a random sample of the generated Com membranes. We refer to this process as the life cycle of the flag object during the loop. The flag object's lifecycle approximates the structure of the loop in the algorithm's design. We use this feature cautiously to ensure that no more than one layer of nested loops occurs, introducing a new exponential time consumption. #### 4.2.3 Splitting and Calculation Process

As shown in Figure 4, in the initial stage of the system, there is only one initial \(Com\) membrane in the \(Skin\) membrane that serves as the basis for membrane division. The \(Com\) membrane holds the objects \(a\), \(d^{2}\), and \(\xi^{N}\), where the object \(a\) can control the splitting process, the object \(d\) is responsible for counting, and the count of the object \(\xi\) is used as the number to be factored (e.g., if the number to be factored is 25, the number represented by \(N\) in \(\xi^{N}\) is 25). The initial \(Com\) membrane holds the object \(a\) as the flag object of the splitting process (i.e., it has the ability to split), and subsequently splits into two daughter

Figure 4: Steps for solving a large number of decompositions using the P system. membranes by rule \(a{\rightarrow}[b]_{\text{Com}}[c\ r^{2}]_{\text{Com}}\), where the former will be reduced to an initial membrane with the ability to split by rule \(b\to a\ d\), and will achieve an additional object \(d\) than its parent. The latter will be transformed into a computational membrane by rule \(d\to z\) into a computational membrane, where the count \(|z|\) of the object \(z\) is the value of a taken in the current modal index \(a^{x}\) mod \(N\). This means that each time a computational submembrane is split out, the initial membrane is restored and receives an increase in count, which is reflected in the object size of the computational submembrane produced at the next split. Take for example the computational submembrane responsible for computing the modal index \(3^{x}\)mod 25 (i.e., \(N=25\), \(a=3\)). After the appearance of object \(c\) in the computational submembrane, it proceeds to the next process to compute the value associated with the modal index, which is split by the initial membrane holding objects \(c\), \(r^{2}\), \(z^{3}\), and \(N^{25}\). Objects \(c\) and \(r\) have a fixed number (i.e., 1 object c and 2 objects r), and they are the flagged objects controlling the computational process. The number of objects \(z\ |z\ |\) is used to indicate the bottom number in the current arithmetic. In the current calculation, the base number is 3, for which 3 objects \(z\) produce equal copies under the rule \(z{\rightarrow}z_{1}\ z_{2}\ |_{c}c{\rightarrow}d\), that is, 3 objects \(z_{1}\) and 3 objects \(z_{2}\), as well as 1 additional object \(d\). To implement the exponential calculation, we use some tricks; that is, the rule \(z_{1}{\rightarrow}z\ z_{1}\ |_{2}\); \(d\ z_{2}{\rightarrow}d\); which, under the action of this rule, will produce \(|z_{2}|\) rounds of computation based on the number of objects \(z_{2}\), the object \(d\) produced in the previous rule is used to ensure that each round of computation will consume 1 and only 1 object \(z_{2}\) and produce \(|z_{1}|\) object \(z\). That is, after all, the objects \(z_{2}\) are consumed, the submembrane will be computed to obtain \(|z_{1}|\ \times|z_{2}|\) object \(z\); that is, a multiplicative computation is completed, and the number is indicated by the newly produced object \(z^{\prime}\)s count \(|z\ |\) denoted by the number of newly generated objects \(z\). In this example, \(|z\ |=3^{2}=9\).