# P System Design for Integer Factorization
## 2 Foundation
### Extended P System
Since the final exponent used to compute the greatest common divisor is \(a^{r/2}\) instead of \(a^{r}\), there are two additional rules: \(d{\rightarrow}\ e\ |\ {\rightarrow}z\); and \(z_{1}{\rightarrow}\ y\ y_{2}\ |_{c};z{\rightarrow}\ v\ z_{2}\ |_{c};e{ \rightarrow}\ c\); which are used to obtain ar along with \(a^{r/2}\), avoiding the need to do additional root operations in future phases of the submembrane. Moreover, it will transform the object \(z\) all into the object \(v\), thus, serving as the flag object for the next stage. Once we have obtained the iconic object \(c\) and object \(v\), we can perform the first modulo determination operation, which is accomplished by three rules, rule \(v\ c{\rightarrow}p\ f\),1 and rule \(v{\rightarrow}\lambda\),2, and rule \(v{\rightarrow}i\ f\)3. In the \(3^{x}\) mod 25 arithmetic of this example, this set of rules performs an integer multiples \(|N|\) divisor computation of \(3^{x}-1\), with the final remainder represented by object \(i\). The final remainder is denoted by object \(i\). If the count of object \(i\) is 0, it means that \(3^{x}\)mod 25 = 1, which satisfies the determination of \(f(0)=f(x_{1})=1\), and it can be submitted to the \(GCD\) membrane for calculating prime factors. If the count of object \(i\) is not 0, it means that the arithmetic is not satisfied and it goes to the next round of exponential iteration. The new round of exponential iteration is jointly accomplished by six rules, namely rules \(f{\rightarrow}z_{1}\ |_{i}\); \(p{\rightarrow}g\ h\ |_{i}\); \(y{\rightarrow}y_{1}\ |_{i}\); \(i{\rightarrow}\lambda\); rules \(z_{1}{\rightarrow}z_{2}\ |_{1}z_{2}\); \(g\ z_{2}{\rightarrow}g\ q_{1}\), 1; and rules \(y_{1}{\rightarrow}y\ y_{1}\ |_{y2}\); \(h\ y_{2}{\rightarrow}h\ q_{2}\), 1; rules \(g{\rightarrow}w\ r^{2}\), 2; \(h{\rightarrow}\lambda\), 2; rules \(z{\rightarrow}v\ |_{w}\); \(q_{1}{\rightarrow}z_{2}\ |_{w}\); \(z_{1}{\rightarrow}\lambda\ |_{w}\); and rules \(q_{2}{\rightarrow}y_{2}\ |_{w}\); \(y_{1}{\rightarrow}\lambda\ |_{w}\); \(w{\rightarrow}c\) are composed. These six rules continue to iterate over the object \(|z\ |=3^{2}\) and the object \(|y\ |=3^{1}\), creating \(3^{2+2}\) new objects \(z\) and \(3^{1}\) new objects \(y\). At the end of this set of rules, we obtained the flag object \(c\) and the flag object \(v\) again, and then performed a modulo judgment. For this reason, we made the complete process of splitting the membrane and computing the submembrane under the standard execution process into a calculation table based on timing and rounds. For more information, refer to Tables 1 and 2. ## 5 Cases and Experiments

### Instance of UPLanguage

The UP Simulator [22] simulator uses a new universal P system description language, UPLanguage, which is a superset of the standard P system rules. Based on UPLanguage, we developed a complete experimental code for integer decomposition P systems and wrote a set of UPLanguage rules for handling the highest common divisors. UPLanguage provides some very useful mechanisms, and when writing the experimental code, without destroying the integrity of the partitioning process, we adapted some of the rules, confusing object naming and the design for optimization and compatibility purposes. The rules adopted in this section are described using UPLanguage, which is specially used for the implementation of simulation. You can find this complete usage case at [[https://github.com/CqNatural/p-system-integer-factorization](https://github.com/CqNatural/p-system-integer-factorization)]([https://github.com/CqNatural/p-system-integer-factorization](https://github.com/CqNatural/p-system-integer-factorization)) (accessed on 20 July 2023). ### Cases

To better understand the rules in Section 4, we rewrite our rules using UPLanguage and simulate them using UPS Simulator. Next, we show the process of integer factorization in detail using \(N=15\) as an example. At \(\text{T}_{0}\), as shown in Figure 5a, the only objects in the membrane are \(a\ d^{2}\)_ReleaseFlag_\(N^{15}\).