{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:38:08Z","timestamp":1760240288765,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T00:00:00Z","timestamp":1556496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>The AKS algorithm is an important breakthrough in showing that primality testing of an integer can be done in polynomial time. In this paper, we study the optimization of its runtime. Namely, given a finite cardinality set of alphabets of a deterministic polynomial runtime Turing machine and the number of strings of an arbitrary input integer whose primality is to be tested as the system parameters, we consider the randomized AKS primality testing function as the objective function. Under randomization of the system parameters, we have shown that there are definite signatures of the local and global instabilities in the AKS algorithm. We observe that instabilities occur at the extreme limits of the parameters. It is worth mentioning that Fermat\u2019s little theorem and Chinese remaindering help with the determination of the underlying stability domains. On the other hand, in the realm of the randomization theory, our study offers fluctuation theory structures of the AKS primality testing of an integer through its maximum number of irreducible factors. Finally, our optimization theory analysis anticipates a class of real-world applications for future research and developments, including optimal online security, system optimization and its performance improvements, (de)randomization techniques, and beyond, e.g., polynomial time primality testing, identity testing, machine learning, scientific computing, coding theory, and other stimulating optimization problems in a random environment.<\/jats:p>","DOI":"10.3390\/cryptography3020012","type":"journal-article","created":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T07:01:22Z","timestamp":1556521282000},"page":"12","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimized AKS Primality Testing: A Fluctuation Theory Perspective"],"prefix":"10.3390","volume":"3","author":[{"given":"Bhupendra","family":"Tiwari","sequence":"first","affiliation":[{"name":"Faculty of Computer Science and Engineering, University of Information Science and Technology, St. Paul the Apostle, Partizanska bb, 6000 Ohrid, Republic of Macedonia"},{"name":"INFN-Laboratori Nazionali di Frascati, Via E. Fermi, 40-I-00044 Rome, Italy"}]},{"given":"Jude","family":"Kuipo","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science and Engineering, University of Information Science and Technology, St. Paul the Apostle, Partizanska bb, 6000 Ohrid, Republic of Macedonia"}]},{"given":"Joshua","family":"Adeegbe","sequence":"additional","affiliation":[{"name":"Faculty of Communication Networks and Security, University of Information Science and Technology, St. Paul the Apostle, Partizanska bb, 6000 Ohrid, Republic of Macedonia"}]},{"given":"Ninoslav","family":"Marina","sequence":"additional","affiliation":[{"name":"Faculty of Communication Networks and Security, University of Information Science and Technology, St. Paul the Apostle, Partizanska bb, 6000 Ohrid, Republic of Macedonia"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in P","volume":"160","author":"Agrawal","year":"2004","journal-title":"Ann. Math."},{"key":"ref_2","unstructured":"Savu, L. (2011, January 14\u201317). Cryptography role in information security. Proceedings of the 5th WSEAS International Conference on Communications and Information Technology (CIT11), Corfu Island, Greece."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Knudsen, L.R., and Matthew, J.B.R. (2011). The Block Cipher Companion, Springer.","DOI":"10.1007\/978-3-642-17342-4"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1093\/comjnl\/35.5.478","article-title":"Protocol design and implementation using formal methods","volume":"35","author":"Pires","year":"1992","journal-title":"Comput. J."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Sharp, R. (2008). Principles of Protocol Design, Springer.","DOI":"10.1007\/978-3-540-77541-6"},{"key":"ref_6","unstructured":"Clark, K. (2019, April 20). An Algorithm that Decides PRIMES in Polynomial Time. Available online: https:\/\/sites.math.washington.edu\/~morrow\/336_11\/papers\/kevin.pdf."},{"key":"ref_7","unstructured":"Carlson, J., Carlson, J.A., Jaffe, A., and Wiles, A. (2006). The P versus NP problem. The Millennium Prize Problems, American Mathematical Society."},{"key":"ref_8","unstructured":"Fortnow, L., and Homer, S. (2003). A Short History of Computational Complexity, Boston University Computer Science Department. Computer Science: Technical Reports, 2003-10-02."},{"key":"ref_9","unstructured":"Sudan, M. (2019, April 20). The P vs. NP problem. Available online: http:\/\/madhu.seas.harvard.edu\/papers\/2010\/pnp.pdf."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., and Sudan, M. (2001). Complexity Classifications of Boolean Constraint Satisfaction Problems, SIAM.","DOI":"10.1137\/1.9780898718546"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","article-title":"Primality and identity testing via Chinese remaindering","volume":"50","author":"Agrawal","year":"2003","journal-title":"J. ACM (JACM)"},{"key":"ref_12","unstructured":"Sudan, M. (2019, April 20). Algebra and Computation, Lecture 12. Available online: http:\/\/people.csail.mit.edu\/madhu\/ST12\/scribe\/lect12.pdf."},{"key":"ref_13","unstructured":"Kopparty, S. (2019, April 20). Primality Testing, Lecture 14, Algorithmic Number Theory. Available online: http:\/\/www.math.rutgers.edu\/~sk1233\/courses\/ANT-F14\/lec14.pdf."},{"key":"ref_14","unstructured":"Hansen, P.B. (2019, April 20). Primality Testing. Available online: http:\/\/surface.syr.edu\/eecs_techreports\/169\/."},{"key":"ref_15","unstructured":"Smart, N.P. (2003). Cryptography: An Introduction, Mcgraw-Hill. [3rd ed.]."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Hardy, G.H., and Wright, E.M. (2008). Introduction to the Theory of Numbers, Oxford University Press. [6th ed.].","DOI":"10.1093\/oso\/9780199219858.001.0001"},{"key":"ref_17","unstructured":"Sudan, M. (2019, April 20). Primality Testing, Lecture 12, Algebra and Computation. Available online: http:\/\/people.csail.mit.edu\/madhu\/ST12\/scribe\/lect12.pdf."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1112\/plms\/s2-42.1.230","article-title":"On computable numbers, with an application to the Entscheidungsproblem","volume":"2","author":"Turing","year":"1937","journal-title":"Proc. Lond. Math. Soc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1103\/RevModPhys.67.605","article-title":"Riemannian geometry in thermodynamic fluctuation theory","volume":"67","author":"Ruppeiner","year":"1995","journal-title":"Rev. Mod. Phys."},{"key":"ref_20","unstructured":"Tiwari, B.N. (2011). Geometric perspective of entropy function: Embedding, spectrum and convexity. arXiv."},{"key":"ref_21","unstructured":"Tiwari, B.N., Adeegbe, J.M., and Kibind\u00e9, J.K. (2018). Randomized Cunningham Numbers in Cryptography: Randomization theory, Cryptanalysis, RSA cryptosystem, Primality testing, Cunningham numbers, Optimization theory, LAP LAMBERT Academic Publishing."},{"key":"ref_22","unstructured":"Rosen, K.H. (1998). Discrete Mathematics and Its Applications, McGraw-Hill Pub. [7th ed.]."},{"key":"ref_23","unstructured":"Atiyah, M.F., and MacDonald, I.G. (1994). Introduction to Commutative Algebra, CRC Press."},{"key":"ref_24","unstructured":"Borwein, J., and Borwein, P.B. (1987). Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity, Wiley."},{"key":"ref_25","unstructured":"Conrad, K. (2019, April 20). The Miller\u2013Rabin Test. Available online: http:\/\/www.math.uconn.edu\/~kconrad\/blurbs\/ugradnumthy\/millerrabin.pdf."},{"key":"ref_26","unstructured":"Conrad, K. (2019, April 20). The Solovay\u2013Strassen Test. Available online: http:\/\/www.math.uconn.edu\/~kconrad\/blurbs\/ugradnumthy\/solovaystrassen.pdf."},{"key":"ref_27","first-page":"1","article-title":"Exact Complexity and Satisfiability","volume":"8246","author":"Gutin","year":"2013","journal-title":"Parameterized and Exact Computation, Proceedings of the International Symposium on Parameterized and Exact Computation, IPEC 2013, Sophia Antipolis, France, 4\u20136 September 2013"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1090\/S0273-0979-01-00934-X","article-title":"The Octonions","volume":"39","author":"Baez","year":"2002","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1145","DOI":"10.1093\/logcom\/exr012","article-title":"Complexity Classifications for Propositional Abduction in Post\u2019s Framework","volume":"22","author":"Creignou","year":"2012","journal-title":"J. Logic Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1109\/TCYB.2017.2653223","article-title":"Discovering the relationship between generalization and uncertainty by incorporating complexity of classification","volume":"48","author":"Wang","year":"2018","journal-title":"IEEE Trans. Cybern."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/3\/2\/12\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:47:57Z","timestamp":1760186877000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/3\/2\/12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,29]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,6]]}},"alternative-id":["cryptography3020012"],"URL":"https:\/\/doi.org\/10.3390\/cryptography3020012","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2019,4,29]]}}}