# P System Design for Integer Factorization
## 2 Foundation
### Extended P System
Then, at time T\({}_{23}\), the rules \(P\)\(\mathit{rFlag}\to cFlag\) and \(T\to\) (V, out) are executed, and the generated \(V^{4}\) is sent to the parent membrane, as shown in Figure 7. Then, at time T\({}_{24}\), as shown in Figure 7, the rule \(\mathit{cFlag}\to\mathit{GCDFlag}\) CalculateFactor:cf1[_I_] \(\mid_{\mathit{1}}\)\(\mid_{\mathit{1}}\)\(\mid_{\mathit{1}}\)\(\mid_{\mathit{GCDFlag}}\)\(\mid_{\mathit{2}}\) and the rule \(I\to V\), 1 in the _CalculateFactor_ membrane class are executed, as shown in Figure 7. At T\({}_{26}\), the rule \(\mathit{GCDFlag}\)\(\mid_{\mathit{2}}\)\(\mid_{\mathit{GCDFlag}}\)\(\mid_{\mathit{2}}\)\(\mid_{



However, we found through experiments that the UPS Simulator is prone to overflow problems when dealing with numbers to be decomposed with \(N>39\), which affects the final accuracy. From the simulator's point of view, we re-audited the source code part of UPS Simulator and found that this is due to a flaw in the initial design of UPS Simulator, which did not consider the support for extra-long integer numbers in the data structure. In the P system we designed, the number to be decomposed is represented by the count of the compound object \(N\), which is \(\mid\!\!N\!\mid\). This is caused by the fact that the system may produce intermediate number results with long digits when computing the periodic functions, and our P system does not create a new exponential order problem. Figure 8: Partial membrane structure diagram of T\({}_{27}\) toT\({}_{43}\). We examined some algorithms that already existed and the comparison results are shown in Table 3. Due to the parallel nature of P systems, the algorithm designed for our P system can ideally perform the task of periodization of modal exponential functions in parallel. By theoretical calculations, our algorithm has \(O(n\text{log}\,n)\) in time complexity, \(O(1)\) in the best case, and unknown in the worst case in space complexity. It is important to note that the polynomial demand of time implies an exponential demand of space, and the membrane structure in the P system consumes additional space while executing in parallel. In the current laboratory situation, biocomputing experiments based on P systems remains impossible, so while we have obtained an exciting result, it will remain a threat to asymmetric cryptography in its current form for quite some time to come. Figure 9: Partial membrane structure diagram of T\({}_{44}\) to end. ## 6 Conclusions

The factorization problem is not \"tricky\" because it is neither a decision problem nor an optimization problem. It seems to be difficult because no one has been able to find polynomial-time algorithms to solve it so far. That is, no deterministic (or even probabilistic) polynomial-time algorithm is known that can be executed on a Turing machine to solve every possible case. For this reason, factorization is used in many cryptographic applications, the most famous of which is, of course, the public-key cryptosystem RSA. In this research, we propose a cell-like P system solution \(\Pi_{\text{IF}}\) for the factorization problem. We imitate the periodic processing of the modular exponentiation function \(f(x)=a^{x}\bmod N\) in the Shor algorithm. Specify a number to be decomposed \(N=p\times q\), and the P system \(\Pi_{\text{IF}}\) will target different values of \(a\) in the modular exponentiation function and divide to a different submembrane. A submembrane will try increasing the value of \(x\), and see if \(f(x)\) achieves a period \(r\). If a submembrane of the system calculates the period \(r\), then the periodicization of the system is completed, and the process of dividing the submembrane ends. In the last part of the P system, the greatest common divisor will be calculated through the confirmed period \(r\), and the obtained two numbers \(\gcd(a^{\frac{r}{2}}+1,\)\(N)\) and \(\gcd(a^{\frac{r}{2}}-1,\)\(N)\) are the final two prime factors \(p\) and \(q\) for \(N\).