P System Design for Integer Factorization
Membrane computing is a natural computing branch inspired by the structure of biological cells. The mathematical abstract model of a membrane computing system is called a P System, which is one of the main topics in membrane computing research for the design and verification of a P System. Integer f...
Main Authors: | , , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2023-08-01
|
Series: | Applied Sciences |
Subjects: | |
Online Access: | https://www.mdpi.com/2076-3417/13/15/8910 |
_version_ | 1797586997176434688 |
---|---|
author | Hai Nan Zhijian Xue Chaoyue Li Mingqiang Zhou Xiaoyang Liu |
author_facet | Hai Nan Zhijian Xue Chaoyue Li Mingqiang Zhou Xiaoyang Liu |
author_sort | Hai Nan |
collection | DOAJ |
description | Membrane computing is a natural computing branch inspired by the structure of biological cells. The mathematical abstract model of a membrane computing system is called a P System, which is one of the main topics in membrane computing research for the design and verification of a P System. Integer factorization is still a world-class problem and a very important research direction. If a fast method can be found to solve the integer factorization problem, several important cryptographic systems including the RSA public key algorithm will be broken. The aim of this paper is to design a P System capable of implementing integer decomposition, taking advantage of the characteristics of parallelism of P Systems. We construct a process with a main goal to study the modal exponential function <i>f</i>(<i>x</i>) = <i>a<sup>x</sup></i> mod <i>N</i> and explore the possible periodic behavior for different values of <i>a</i>. We attempt to compute nontrivial prime factors by the period found and constrain the operation of the P System in polynomial time. |
first_indexed | 2024-03-11T00:31:01Z |
format | Article |
id | doaj.art-1723c4e4b38e490bbda409f32f53a924 |
institution | Directory Open Access Journal |
issn | 2076-3417 |
language | English |
last_indexed | 2024-03-11T00:31:01Z |
publishDate | 2023-08-01 |
publisher | MDPI AG |
record_format | Article |
series | Applied Sciences |
spelling | doaj.art-1723c4e4b38e490bbda409f32f53a9242023-11-18T22:39:10ZengMDPI AGApplied Sciences2076-34172023-08-011315891010.3390/app13158910P System Design for Integer FactorizationHai Nan0Zhijian Xue1Chaoyue Li2Mingqiang Zhou3Xiaoyang Liu4College of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaCollege of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaCollege of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaCollege of Computer Science, Chongqing University, Chongqing 400044, ChinaCollege of Computer Science and Engineering, Chongqing University of Technology, Chongqing 400054, ChinaMembrane computing is a natural computing branch inspired by the structure of biological cells. The mathematical abstract model of a membrane computing system is called a P System, which is one of the main topics in membrane computing research for the design and verification of a P System. Integer factorization is still a world-class problem and a very important research direction. If a fast method can be found to solve the integer factorization problem, several important cryptographic systems including the RSA public key algorithm will be broken. The aim of this paper is to design a P System capable of implementing integer decomposition, taking advantage of the characteristics of parallelism of P Systems. We construct a process with a main goal to study the modal exponential function <i>f</i>(<i>x</i>) = <i>a<sup>x</sup></i> mod <i>N</i> and explore the possible periodic behavior for different values of <i>a</i>. We attempt to compute nontrivial prime factors by the period found and constrain the operation of the P System in polynomial time.https://www.mdpi.com/2076-3417/13/15/8910natural computingP systeminteger factorizationperiodic problems |
spellingShingle | Hai Nan Zhijian Xue Chaoyue Li Mingqiang Zhou Xiaoyang Liu P System Design for Integer Factorization Applied Sciences natural computing P system integer factorization periodic problems |
title | P System Design for Integer Factorization |
title_full | P System Design for Integer Factorization |
title_fullStr | P System Design for Integer Factorization |
title_full_unstemmed | P System Design for Integer Factorization |
title_short | P System Design for Integer Factorization |
title_sort | p system design for integer factorization |
topic | natural computing P system integer factorization periodic problems |
url | https://www.mdpi.com/2076-3417/13/15/8910 |
work_keys_str_mv | AT hainan psystemdesignforintegerfactorization AT zhijianxue psystemdesignforintegerfactorization AT chaoyueli psystemdesignforintegerfactorization AT mingqiangzhou psystemdesignforintegerfactorization AT xiaoyangliu psystemdesignforintegerfactorization |