Linear Time Solution to Prime Factorization by Tissue P Systems with Cell Division

Linear Time Solution to Prime Factorization by Tissue P Systems with Cell Division Xingyi Zhang1, Yunyun Niu2, Linqiang Pan2, Mario J. P´erez-Jim´enez3 1School of Computer Science and Technology Anhui University, 230039 Hefei, China [email protected] 2Key Laboratory of Image Processing and Intelligent Control Department of Control Science and Engineering Huazhong University of Science and Technology, 430074 Wuhan, China [email protected], [email protected] 3Department of Computer Science and Artificial Intelligence University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Summary. Prime factorization is useful and crucial for public-key cryptography, and its application in public-key cryptography is possible only because prime factorization has been presumed to be difficult. A polynomial-time algorithm for prime factorization on a quantum computer is given by P. W. Shor in 1997. In this work, a linear-time solution for prime factorization is given on a kind of biochemical computational devices – tissue P systems with cell division, instead of physical computational devices. 1 Introduction In math, prime factorization is the breaking down of a composite number into smaller primes, which when multiplied together equal the original integer. Currently, though the prime factorization problem is not known to be NP-hand, no efficient algorithm is publicly known. It is generally considered intractable. The presumed computational hardness of this problem is at the heart of several algorithms in cryptography such as RSA [15]. Many areas of mathematics and computer science have been brought to bear on the prime factorization problem, including elliptic curves, algebraic number theory, and quantum computing. A polynomial-time algorithm for prime factorization on a quantum computer is given by P. W. Shor in 1997 [16]. This will have significant implications for cryptography if a large quantum computer is ever built. However, before a practical quantum computer appears, it is still of interest to find any reasonable computational devices for solving prime factorization problem. In this work, we shall give a linear-time solution to prime factorization on a class of 356 X. Zhang et al. biochemical computational devices – tissue P systems with cell division, instead of physical computational devices. Tissue P systems with cell division is a class of computational devices in membrane computing. Membrane computing is an emergent branch of natural computing, which is inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. The devices in membrane computing, called P systems, provide distributed parallel and non-deterministic computing models. Since Gh. P˘aun introduced the first P system in [12], this area is heavily investigated. Please refer to [13] for an introduction of membrane computing, and refer to [17] for further bibliography. Informally, a P system consists of a membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous, non-deterministic, maximally parallel manner. Tissue P systems are a class of P systems, where membranes are placed in the nodes of a graph. It is a net of processors dealing with symbols and communicating these symbols along channels specified in advance. The communication among cells is based on symport/antiport rules, which was introduced to P systems in [11]. Symport rules move objects across a membrane together in one direction, whereas antiport rules move objects across a membrane in opposite directions. This model has two biological inspirations (see [9]): intercellular communication and cooperation between neurons. In [14], tissue P systems are endowed with the ability of getting new cells based on the mitosis or cellular division, thus obtaining the ability of generating an exponential amount of workspace in polynomial time. Such variant of tissue P systems is called tissue P systems with cell division. Tissue P systems with cell division were widely investigated for solving NPcomplete problems. Some of them deal with non-numerical NP-complete decision problems, such as SAT problem [14], 3-coloring problem [2], vertex cover [4]. Others deal with numerical NP-complete decision problems, that is, decision problems whose instances consist of sets or sequences of integer numbers, such as subset sum [3], partition problem [5]. Although prime factorization we shall consider is a numerical problem, it is neither a decision problem nor an optimization problem. In this work, we shall construct a family of tissue P systems with cell division, which can decompose integer numbers in a linear time with respect to the length of binary representation of the integer to be factored. As a result of computation, a prime number is sent to a prefixed output membrane, instead of yes or no. Up to now, besides there are two polynomial-time solutions to prime factorization by P systems with active membranes [6, 10], one well known polynomial algorithm that solves factorization problem is based on quantum computer [16]. As the case of quantum computer, the solution given in this work indicates how powerful tissue P systems with cell division can be, although at this moment nobody knows how to build a biochemical computer. The paper is organized as follows. In Section 2, some preliminaries are recalled. The formal definition of tissue P systems with cell division is given in Section 3. A family of tissue P systems that uniformly solve the factorization problem is Factorization by Tissue P Systems with Cell Division 357 presented in Section 4, with a short overview of the computation and the necessary resources. Conclusions and comments are presented in Section 5. 2 Preliminaries An alphabet Σis a non-empty set, whose elements are called symbols. An ordered sequence of symbols is a string. The number of symbols in a string uis the length of the string, and it is denoted by |u|. As usual, the empty string (with length 0) will be denoted by λ. The set of strings of length nbuilt with symbols from the alphabet Σis denoted by Σnand Σ∗=∪n≥0Σn. A language over Σis a subset from Σ∗. Amultiset mover a set Ais a pair (A, f), where f:A→Nis a mapping. If m= (A, f) is a multiset, then its support is defined as supp(m) = {x∈A|f(x)> 0}and its size is defined as Px∈Af(x). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). If m= (A, f) is a finite multiset over A, and supp(m) = {a1, . . . , ak}, then it will be denoted as m={{af(a1) 1, . . . , af(ak) k}}. That is, superscripts indicate the multiplicity of each element. If f(x) = 0 for any x∈A, then this element is omitted. 3 Tissue P Systems with Cell Division In [8, 9], the first definition of the model of tissue P systems was proposed, where the membrane structure did not change along the computation. We now shall introduce a model of tissue P systems with cell division based on the cell-like model of P systems with membranes division [14]. The biological inspiration of this model is clear: alive tissues are not static network of cells, since new cells are generated by membrane fission in a natural way. The main features of this model, from the computational point of view, are that cells are not polarized (the contrary holds in the cell-like model of P systems with active membranes, see [13]); the cells obtained by division have the same labels as the original cell and if a cell is divided, its interaction with other cells or with the environment is blocked during the division process. In some sense, this means that while a cell is dividing it closes its communication channels with other cells and with the environment. Formally, a (function) computing tissue P system with cell division of degree q≥1 and order (m, n), m≥1, n ≥1, is a tuple of the form Π= (Γ, Σ, Λ, w1, . . . , wq,E,R, iin, iout), where: 1. Γis the alphabet of objects; 358 X. Zhang et al. 2. Σ={a1, . . . , am}is an ordered input alphabet strictly contained in Γ; 3. Λ={b1, . . . , bn}is an ordered output alphabet contained in Γ; 4. w1, . . . , wqare strings over Γ, describing the initial multisets of objects placed in the cells of the system at the beginning of the computation; 5. E ⊆ Γis the set of objects in the environment in arbitrarily copies each; 6. Ris a finite set of rules of the following forms: (a) (i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i 6=j,u, v ∈Γ∗; Communication rules; 1,2,· · · , q identify the cells of the system, 0 is the environment; when applying a rule (i, u/v, j), the objects of the multiset represented by uare sent from region ito region jand simultaneously the objects of the multiset vare sent from region jto region i(|u|+|v|is called the length of the communication rule (i, u/v, j)); (b) [a]i→[b]i[c]i, where i∈ {1,2, . . . , q},a, b, c ∈Γ, and i6=iout; Division rules; in reaction with an object a, the cell is divided into two cells with the same label; all the objects in the original cells are replicated and copies of them are placed in each of the new cells, with the exception of the object a, which is replaced by the object bin the first new cell and by cin the second one; the output cell cannot be divided; 7. iin ∈ {1,2, . . . , q}is the input cell; 8. iout ∈ {0,1,2, . . . , q}is the output cell. The rules of a system as above are used in the non-deterministic maximally parallel manner. In each step, all cells which can evolve must evolve in a maximally parallel way (in each step we apply a multiset of rules which is maximal, no further rule can be added). This way of applying rules has only one restriction when a cell is divided, the division rule is the only one which is applied for that cell in that step; the objects inside that cell do not evolve by means of communication rules. Their labels precisely identify the rules which can be applied to them. A configuration of tissue P system with cell division is described by all multisets of objects over Γassociated with all the cells present in the system and the multiset of objects over Γ− E associated with environment. The initial configuration of the system Πwith input w∈Σ∗is the tuple (w1, w2, . . . , wiin w, . . . , wq; ∅); that is, the corresponding configuration after adding the multiset wto the content of the input cell iin. The computation starts from the initial configuration and proceeds as defined above. When there is no rule can be applied, the computation stops. Only halting computations give a result. If C={Ci}i<r is a halting computation, where Ciare configurations, then the result of computation Output(C)=(Cr−1 b1(iout), Cr−1 b2(iout), . . . , Cr−1 bn(iout)), where Cr−1 bj(iout), 1≤j≤n, is the multiplicity of object bjin the region iout in the halting configuration Cr−1. For a function f, we denote the domain of fby D(f) and the range of fby R(f). For a tissue P system with cell division Πhaving ordered input alphabet Σ={a1, a2, . . . , am}and ordered output alphabet Λ={b1, b2, . . . , bn}, and partial function f:Nm→Nn, function fis encoded in a unary notation in the following Factorization by Tissue P Systems with Cell Division 359 way: (α1, . . . , αm)∈D(f) is expressed by aα1 1aα2 2. . . aαm m; (β1, . . . , βn)∈R(f) is expressed by bβ1 1bβ2 2. . . bβn n. Definition 1. We say that a partial function f:Nm→Nnis computed in polynomial time by a family Π={Π(t)|t∈N}of tissue P systems with cell division in unary encoding if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(t)from t∈N. •There exist a polynomial-time computable function sover the domain D(f)of function fsuch that: −for each u= (α1, . . . , αm)∈D(f),s(u)is a natural number and aα1 1. . . aαm m is an input multiset of the system Π(s(u)); −the family Πis polynomially bounded with regard to (f, s), that is, there exists a polynomial function p, such that for each u= (α1, . . . , αm)∈D(f) every computation of Π(s(u)) with input aα1 1. . . aαm mis halting and, moreover, it performs at most p(|u|)steps; −the family Πis sound with regard to (f, s), that is, for each u= (α1, . . . , αm)∈D(f), if there exists a computation Cof Π(s(u)) with input aα1 1. . . aαm msuch that Output(C) = (β1, . . . , βn), then f(u) = (β1,···, βn); −the family Πis complete with regard to (f, s), that is, for each u= (α1, . . . , αm)∈D(f), if f(u)=(β1,· · · , βn), then every computation Cof Π(s(u)) with input aα1 1. . . aαm mhas Output(C) = {β1, . . . , βn}. In the Definition 1, the input and output are encoded in unary notation. However, in classical complexity theory, based upon Turing machine, switching from binary to unary encoding generally corresponds to simplify the problem. In this work, binary encoding is used for integer factorization problem. In what follows, we will give the definition that a function is computed by a family of P systems with cell division in binary encoding. In the case of binary encoding, the input alphabet is not asked to be ordered, and no output alphabet is fixed. A(function) computing tissue P system with cell division with input of degree q≥1 is a tuple of the form Π= (Γ, Σ, w1, . . . , wq,E,R, iin, iout), where: 1. Γis the alphabet of objects; 2. Σis an (un-ordered) input alphabet strictly contained in Γ; 3. w1, . . . , wqare strings over Γ, describing the initial multisets of objects placed in the cells of the system at the beginning of the computation; 4. E ⊆ Γis the set of objects in the environment in arbitrarily copies each; 5. Ris a finite set of rules of the following forms: (a) (i, u/v, j), for i, j ∈ {0,1,2, . . . , q}, i 6=j,u, v ∈Γ∗; 360 X. Zhang et al. (b) [a]i→[b]i[c]i, where i∈ {1,2, . . . , q},a, b, c ∈Γ, and i6=iout; 6. iin ∈ {1,2, . . . , q}is the input cell; 7. iout ∈ {0,1,2, . . . , q}is the output cell. In semantics, P systems having un-ordered alphabets is the same with P systems with ordered input and output alphabets except for the way of encoding input and output. In the unary encoding, the sizes of ordered input and output alphabets are related with the dimensions of domain and range of function that is computed. Specifically, an ordered input alphabet {a1, . . . , am}and an ordered output alphabet {b1, . . . , bn}can encode each function whose domain (resp. range) is a subset of Nm0(m0≤m) (resp. Nn0(n0≤n)). In the binary encoding, the size of alphabet is related with both input value and output value. For example, for the function f(x)=22x(x∈N) and an input n, the length of input nin binary expression is blg nc+ 1, and the length of output f(n) in binary expressions is 2n+ 1, which is an exponential function with respect to blg nc+ 1. For functions such as f(x) = 22x, maybe, we need exponential (with respect to the input size) large alphabet to encode the function in P systems, hence we cannot construct a family of P systems with cell division in polynomial time by Turing machine to compute functions such as f(x)=22x. It depends on the property of function whether a function can be computed by tissue P systems with cell division in binary encoding. For prime factorization problem, the factors are less than the integer to be factored. In fact enables us to find a reasonable binary encoding for prime factorization problem. Specifically, we shall use the method from [7] to encode binary numbers by multisets of objects. Let xk−1,· · · , x1, x0(with k≥1) be the binary representation of integer x≥0, that is, x=Pk−1 i=0 xi2i. We use the objects from the following alphabet Ak, for k≥1: Ak={hb, ji | b∈ {0,1}, j ∈ {1,2,· · · , k}}. Objects hb, jiis used to represent bit bin position jin the binary encoding of an integer number. Hence, to represent the above number xwe will use the following multiset (actually, a set) of objects: hxk−1, k −1i,· · · ,hx1,1i,hx0,0i. Let us remark that the alphabet Akdepends on the length of the binary representation of the number x. Moreover, it is clear that with Akwe can represent all integer numbers in the range 0,1,· · · ,2k−1. In order to distinguish between the objects that represent the bits of different integers Aand B, a leading label A, B are used to mark each element in the multiset. To this aim, the alphabet Akis modified as follows: A0 k={hl, b, ji | l∈ {A, B}, b ∈ {0,1}, j ∈ {1,2,· · · , k}}. In this way, the i-th bit of A(that is, ai) and the j-th bit of B(that is, bj) are represented by the objects hA, ai, iiand hB, bj, ji, respectively. Factorization by Tissue P Systems with Cell Division 361 In general, we give the following definition that a function is computed by P systems with cell division in binary encoding. Definition 2. We say that a partial function f:N→Nis computed in polynomial time by a family Π={Π(t)|t∈N}of tissue P systems with cell division in binary encoding if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(t)from t∈N. •There exists a pair (cod, s)of polynomial-time computable functions over the domain D(f)of function fsuch that: −for each u∈D(f),s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)); −the family Πis polynomially bounded with regard to (f, cod, s), that is, there exists a polynomial function p, such that for each u∈D(f)every computation of Π(s(u)) with input cod(u)is halting and, moreover, it performs at most p(|u|)steps; −the family Πis sound with regard to (f, cod, s), that is, for each u∈D(f), if there exists a computation Cof Π(s(u)) with input cod(u)and the objects in region iout in the last configuration of Cencode (β1,· · · , βq)∈Nq, then f(u) = (β1,· · · , βq); −the family Πis complete with regard to (f, cod, s), that is, for each u∈ D(f), if f(u)=(β1,· · · , βq)∈Nq, then in every computation of Π(s(u)) with input cod(u), the objects in region iout in the last configuration encode (β1,· · · , βq). 4 A Linear Time Solution to the Factorization Problem When we discuss the prime factorization problem, it is necessary to distinguish two different versions of the problem: decision problem version and function problem version. The decision problem version of prime factorization can be formulated as “is na composite number?” (or equivalently: “is na prime number?”). This version is natural and useful because most well-studied complexity classes are defined as classes of decision problems, not function problems. But the decision problem version of prime factorization is much easier than the problem of finding the factors of n. Specifically, it can be solved in polynomial time (with respect to the number of digits of n) with the AKS primality test [1]. The function problem version of prime factorization: given an integer n, find an integer dwith 1 < d < n that divides n(or conclude that nis prime). It is trivially in the class FNP, but we do not known whether it lies in class FP or not. This version is generally considered intractable, which means that no polynomialtime (with respect to the instance size) algorithm is known that solves it on every 362 X. Zhang et al. instance; and it is the version solved by most practical implementations. In this work, we shall consider a restricted version of prime factorization problem, based on the following two facts. (1) Given an algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm. (2) Not all numbers of a given length are equally hard to factor. Semiprimes (the product of two prime numbers) are believed as the hardest instances of integer factorization for currently known techniques. Problem 1. NAME: factorization. – INSTANCE: a positive integer number which is the product of two prime numbers. – OUTPUT: the prime factor that is not greater than another one. Next, we shall construct a family {Π(k)}k∈Nof tissue P systems with cell division to factor integers, where each system Π(k) can decompose all numbers of length kin binary form, provided that an appropriate input multiset is given. The resolution is a brute force algorithm, which consists of the following stages: •Generation Stage: By division, all the possible pairs of integer numbers of length kin binary form are produced (one pair for each membrane with label 2). •Pre-checking Stage: In this stage, the product of each pair of integer numbers of length kis calculated. •Checking Stage: The system checks whether or not there exists a pair of integer numbers such that their product equals to the number nto be composed. •Output Stage: The system sends to the output region a prime number. For each k∈N, Π(k) = (Γ(k), Σ(k), w1, w2,R(k),E(k), iin, iout), with the following components: •Γ(k) = Σ(k)∪ {ai, bi,hX, 0, ii, fi, gi|0≤i≤k−1}∪ {hA, j, ii,hB, j, ii,hA0, j, ii,hB0, j, ii | 0≤i≤k−1,0≤j≤1}∪ {hAj, l, ii,hBj, l, ii | 0≤i≤k−1,0≤j≤ dlg ke+ 1,0≤l≤1}∪ {ci|0≤i≤4k+dlg 2ke+dlg ke+ 5}∪{c0 i|1≤i≤ dlg ke+ 2k+ 3}∪ {hC, 0, ii,hC, 1, ii | 0≤i≤2k−1} ∪ {hi, ji | 0≤i, j ≤k−1}∪ {di| −1≤i≤k−2}∪{ei| −1≤i≤k−1}∪{z}. •Σ(k) = {hn, 0, ii,hn, 1, ii | 0≤i≤k−1}. •w1={{c0}}. •w2={{a0a1· · · ak−1b0b1···bk−1z}} ∪ {{hi, ji | 0≤i, j ≤k−1}}. • R(k) is the set of rules: 1. Division rule: r1,i ≡[ai]2→[hA, 0, ii]2[hA, 1, ii]2, for 0 ≤i≤k−1; r2,i ≡[bi]2→[hB, 0, ii]2[hB, 1, ii]2, for 0 ≤i≤k−1. Factorization by Tissue P Systems with Cell Division 363 2. Communication rules: r3,i ≡(1, ci/c2 i+1,0), for 0 ≤i≤2k−1; r4≡(1, c2k/z, 2); r5,i ≡(2, c2k+i/c2 2k+i+1,0), for 0 ≤i≤ dlg 2ke − 1; r6,i,j ≡(2, c2k+dlg 2kehA, j, ii/c2k+dlg 2ke+1hA0, j, ii,0), for 0 ≤i≤k−1, 0 ≤j≤1; r7,i,j ≡(2, c2k+dlg 2kehB, j, ii/c2k+dlg 2ke+1hB0, j, ii,0), for 0 ≤i≤k−1, 0 ≤j≤1; r8≡(2, c2k+dlg 2ke+1/c0 1c2k+dlg 2ke+2,0); r9,i ≡(2, c2k+dlg 2ke+i/c2k+dlg 2ke+i+1,0), for 2 ≤i≤ dlg ke+ 2k+ 4; r10,i ≡(2, c0 i/c0 i+1,0), for 1 ≤i≤ dlg ke+ 2k+ 2; r11,i,j,l ≡(2,hAj, l, ii/hAj+1, l, ii2,0), for 0 ≤i≤k−1, 0 ≤j≤ dlg ke, 0 ≤l≤1; r12,i,j,l ≡(2,hBj, l, ii/hBj+1, l, ii2,0), for 0 ≤i≤k−1, 0 ≤j≤ dlg ke, 0 ≤l≤1; r13,i,j ≡(2,hAdlg ke+1,0, iihBdlg ke+1,0, jihi, ji/hC, 0, i +ji,0), for 0 ≤i, j ≤k−1; r14,i,j ≡(2,hAdlg ke+1,0, iihBdlg ke+1,1, jihi, ji/hC, 0, i +ji,0), for 0 ≤i, j ≤k−1; r15,i,j ≡(2,hAdlg ke+1,1, iihBdlg ke+1,0, jihi, ji/hC, 0, i +ji,0), for 0 ≤i, j ≤k−1; r16,i,j ≡(2,hAdlg ke+1,1, iihBdlg ke+1,1, jihi, ji/hC, 1, i +ji,0), for 0 ≤i, j ≤k−1; r17,i ≡(2,hC, 0, iihC, 0, ii/hC, 0, ii,0), for 0 ≤i≤2k−2; r18,i ≡(2,hC, 0, iihC, 1, ii/hC, 1, ii,0), for 0 ≤i≤2k−2; r19,i ≡(2,hC, 1, iihC, 1, ii/hC, 0, iihC, 1, i + 1i,0), for 0 ≤i≤2k−2; r20,i,j ≡(2, c0 dlg ke+2k+3hC, 1, iihn, j, k −1i/λ, 0), for k≤i≤2k−2, 0 ≤j≤1; r21,i,j ≡(2, c4k+dlg 2ke+dlg ke+5hC, j, iihn, j, ii/hX, 0, ii,0), for 0 ≤i≤k−1, 0 ≤j≤1; r22 ≡(2,hX, 0, k −1i/dk−2,0); r23,i ≡(2, dihX, 0, ii/di−1,0), for 0 ≤i≤k−2; r24 ≡(2, d−1/ek−1,0); r25,i,j ≡(2,hAdlg ke+1, j, iihBdlg ke+1, j, iiei/hAdlg ke+1, j, ii hBdlg ke+1, j, iiei−1,0), for 0 ≤i≤k−1, 0 ≤j≤1; r26 ≡(2, e−1/f0,0); r27,i ≡(2,hAdlg ke+1,1, iihBdlg ke+1,0, iiei/hAdlg ke+1,1, ii hBdlg ke+1,0, iif0,0), for 0 ≤i≤k−1; r28,i,j ≡(2, fihBdlg ke+1, j, ii/fi+1hB0, j, ii,0), for 0 ≤i≤k−2, 0 ≤j≤1; r29,j ≡(2, fk−1hBdlg ke+1, j, k −1i/hB0, j, k −1i,0), for 0 ≤j≤1; r30,i,j ≡(2,hB0, j, ii/λ, 3), for 0 ≤i≤k−1, 0 ≤j≤1; r31,i ≡(2,hAdlg ke+1,0, iihBdlg ke+1,1, iiei/hAdlg ke+1,0, ii hBdlg ke+1,1, iig0,0), for 0 ≤i≤k−1; r32,i,j ≡(2, gihAdlg ke+1, j, ii/gi+1hA0, j, ii,0), for 0 ≤i≤k−2, 0 ≤j≤1; 370 X. Zhang et al. 1 z 16 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 1, 1 〉 〈 X , 0, 0 〉 〈 A 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 1, 0 〉 2 〈 A 2, 0,1 〉 2 〈 A 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 2 c 16 3 〈 C , 0,1 〉〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 1,1 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 1, 1 〉 〈 X , 0, 0 〉 〈 A 2, 0,0 〉 2 2 c 16 4 〈 C , 1,0 〉 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 1, 1 〉 〈 n, 0,0 〉 〈 A 2, 0,1 〉 2 〈 A 2, 0,1 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 2 〈 C , 0,2 〉 〈 X , 0, 1 〉〈 X , 0,0 〉 〈 A 2, 1, 1 〉 2 2 c 16 3 〈 C ,0,2 〉 〈 X , 0, 1 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 3 〈 C , 0,2 〉 〈 X , 0, 0 〉 〈 A 2, 0,1 〉 2 2 c 16 2 〈 C , 0,2 〉 〈 X , 0, 1 〉 〈 X , 0, 0 〉 〈 A 2, 0,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 X , 0,0 〉 〈 A 2, 1, 1 〉 2 2 c 16 3 〈 C , 1,1 〉 〈 X , 0, 0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 0,1 〉 2 2 c 16 3 〈 C , 1,0 〉 〈 C , 0,2 〉 〈 X , 0, 1 〉 〈 n, 0,0 〉 〈 A 2, 0,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 3 〈 C , 1,1 〉 〈 X , 0,0 〉 〈 A 2, 1, 1 〉 2 2 c 16 4 〈 C , 1,0 〉 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 0, 0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 〈 C ,1,0 〉 〈 n, 0,0 〉 〈 C , 0,1 〉 〈 n , 1, 1 〉 c ' 8 Fig. 5. The configuration of system Π(2) for factoring integer number 2 at step 19 5 Conclusions and Comments Prime factorization problem is not in itself widely useful problem. It has become useful only because it has been found to be crucial for public-key cryptography, and this application is in turn possible only because they have been presumed to be difficult. Currently, no deterministic polynomial-time algorithm is known, which can be executed on Turing machines, that solves the problem for every possible instance. It is of interest to explore any possible and reasonable way to solve prime factorization problem because of its importance in public-key cryptography. Prime factorization problem is neither decision problem nor optimization problem. In this work, it is considered as a function problem, and in the framework of tissue P systems with cell division, a linear-time solution to prime factorization problem is given. The initial structure of the systems is very simple, which consists of three cells. The system is initialized with inputting into the fixed input cell the multiset that expresses the integer number nto be factored. After a linear time with respect to the size of n(i. e., blg kc+ 1), we can read out one factor of nin the output cell. Factorization by Tissue P Systems with Cell Division 371 1 z 16 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0, 0 〉 〈 A 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 1, 0 〉 2 〈 A 2, 0,1 〉 2 〈 A 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 1,1 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 0,1 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0, 0 〉 〈 A 2, 0,0 〉 2 2 c 16 4 〈 C , 1,0 〉 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 n, 0,0 〉 〈 A 2, 0,1 〉 2 〈 A 2, 0,1 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 2 〈 C , 0,2 〉 〈 A 2, 1, 1 〉 2 2 c 16 3 〈 C ,0,2 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 0,1 〉〈 B 2, 1, 0 〉〈 B 2, 0,1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 X , 0,0 〉 〈 A 2, 0,1 〉 2 2 c 16 2 〈 C , 0,2 〉 〈 A 2, 0,1 〉 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 〈 B 2, 1,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 X , 0, 0 〉 〈 A 2, 1, 1 〉 2 2 c 16 3 〈 C , 1,1 〉 〈 X , 0, 0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1,1 〉 2 〈 B 2, 0,0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 0,0 〉 2 2 c 16 3 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 〈 X , 0,0 〉 〈 A 2, 0,1 〉 2 2 c 16 3 〈 C , 1,0 〉 〈 C , 0,2 〉 〈 n, 0,0 〉 〈 A 2, 0,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 2 c 16 3 〈 C , 1,1 〉 〈 X , 0,0 〉 〈 A 2, 1, 1 〉 2 2 c 16 4 〈 C , 1,0 〉 〈 C , 0,1 〉 〈 C , 0,2 〉 〈 n , 0, 0 〉 〈 A 2, 1,1 〉 2 〈 A 2, 0,0 〉 2 〈 A 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 〈 B 2, 1, 1 〉 2 〈 B 2, 1, 0 〉 2 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 c ' 8 d 0 d 0 〈 C ,1,0 〉 〈 n, 0,0 〉 〈 B' , 0,1 〉 〈 B' , 1, 0 〉 〈 A' , 0,1 〉〈 A' , 1, 0 〉 〈 C , 0,2 〉 〈 n, 1, 1 〉 c ' 8 Fig. 6. The configuration of system Π(2) for factoring integer number 2 at step 25 P system is a highly distributed parallel model of computation. Currently, nobody knows how to build a biochemical computer/an artificial tissue-like computer. P systems may be implemented using molecules, cells or a large computer network such as the Internet. Although it goes beyond the scope of this work to discuss the implementation of P systems, clearly, it is of particular interest and it is a big challenging topic. Acknowledgements The work was supported by National Natural Science Foundation of China (61033003, 61003038 and 30870826), Ph.D. Programs Foundation of Ministry of Education of China (20100142110072), Fundamental Research Funds for the Central Universities (2010ZD001), and Natural Science Foundation of Hubei Province (2008CDB113 and 2008CDB180). Mario J. P´erez-Jim´enez also acknowledges the support of the project TIN2009-13192 of the Ministerio de Ciencia e Innovaci´on of Spain, cofinanced by FEDER funds, and the “Proyecto de Excelencia con Investigador de Reconocida Val´ıa” of the Junta de Andaluc´ıa under grant P08-TIC04200. 372 X. Zhang et al. References 1. M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P, Annals of Mathematics 160(2) (2004) 781–793. 2. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.A. P´erez-Jim´enez, A. Riscos-N´u˜nez, A uniform family of tissue P system with cell division solving 3-COL in a linear time, Theoretical Computer Science 404 (2008) 76–87. 3. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.A. P´erez-Jim´enez, A. Riscos-N´u˜nez, Solving subset sum in linear time by using tissue P system with cell division, in: Lecture Notes in Computer Science, vol. 4527, 2007, pp. 170–179. 4. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.A. P´erez-Jim´enez, A. Riscos-N´u˜nez, Computational efficiency of cellular division in tissue-like membrane systems, Romanian Journal of Information Science and Technology 11 (3) (2008) 229–241. 5. D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.A. P´erez-Jim´enez, A. Riscos-N´u˜nez, Solving the partition problem by using tissue-like P systems with cell division, in: D. Kearney, V. Nguyen, G. Gioiosa, T. Hendtlass (Eds.), Third International Conference on Bio-Inspired Computing: Theories and Applications, Adelaide, 2008, pp. 43-48. 6. A. Leporati, C. Zandron, G. Mauri, Solving the factorization problem with P systems, Progress in Natural Science, 17 (4) (2007) 471–478. 7. A. Leporati, C. Zandron, M.A. Guti´errez-Naranjo, P systems with input in binary form, International Journal of Foundation of Computer Science, 17(1) (2006) 127– 146. 8. C. Mart´ın Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez Pat´on, A new class of symbolic abstract neural nets: tissue P systems, in: Lecture Notes in Computer Science, vol. 2387, 2002, pp. 290–299. 9. C. Mart´ın Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez Pat´on, Tissue P systems, Theoretical Computer Science 296 (2003) 295–326. 10. A. Obtulowicz, On P systems with active membranes solving the integer factorization problem in a polynomial time, in: Lecture Notes in Computer Science, vol. 2235, 2001, pp. 267–285. 11. A. P˘aun, Gh. P˘aun, The power of communication: P systems with symport/antiport, New Generation Computing 20 (3) (2002) 295–305. 12. Gh. P˘aun, Computing with membranes, Journal of Computer and System Sciences 61(1) (2000) 108–143. 13. Gh. P˘aun, Membrane Computing. An Introduction, Springer–Verlag, Berlin, 2002. 14. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, Tissue P system with cell division, International Journal of Computers, Communications &Control III (3) (2008) 295– 302 15. R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comunications of the ACM 21 (2) (2006) 120–126. 16. P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26 (5) (1997) 1484– 1509 17. P systems web page http://ppage.psystems.eu/