{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T17:01:37Z","timestamp":1761238897043,"version":"build-2065373602"},"reference-count":7,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T00:00:00Z","timestamp":1627516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>Previous work established the set of square-free integers n with at least one factorization n=p\u00afq\u00af for which p\u00af and q\u00af are valid RSA keys, whether they are prime or composite. These integers are exactly those with the property \u03bb(n)\u2223(p\u00af\u22121)(q\u00af\u22121), where \u03bb is the Carmichael totient function. We refer to these integers as idempotent, because \u2200a\u2208Zn,ak(p\u00af\u22121)(q\u00af\u22121)+1\u2261na for any positive integer k. This set was initially known to contain only the semiprimes, and later expanded to include some of the Carmichael numbers. Recent work by the author gave the explicit formulation for the set, showing that the set includes numbers that are neither semiprimes nor Carmichael numbers. Numbers in this last category had not been previously analyzed in the literature. While only the semiprimes have useful cryptographic properties, idempotent integers are deserving of study in their own right as they lie at the border of hard problems in number theory and computer science. Some idempotent integers, the maximally idempotent integers, have the property that all their factorizations are idempotent. We discuss their structure here, heuristics to assist in finding them, and algorithms from graph theory that can be used to construct examples of arbitrary size.<\/jats:p>","DOI":"10.3390\/info12080305","type":"journal-article","created":{"date-parts":[[2021,7,29]],"date-time":"2021-07-29T10:47:46Z","timestamp":1627555666000},"page":"305","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5940-2598","authenticated-orcid":false,"given":"Barry","family":"Fagin","sequence":"first","affiliation":[{"name":"Department of Computer Science, US Air Force Academy, El Paso County, CO 80840, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key Cryptosystem","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0893-9659(88)90081-X","article-title":"On Using Primes for Public Key Encryption Systems","volume":"1","author":"Warndof","year":"1988","journal-title":"Appl. Math Lett."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Fagin, B. (2019). Idempotent Factorizations of Square-Free Integers. Information, 10.","DOI":"10.20944\/preprints201906.0208.v1"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Pinch, R. (1997, January 17\u201319). On Using Carmichael Numbers for Public Key Encryption Systems. Proceedings of the International Conference on Cryptography and Coding, Cirencester, UK.","DOI":"10.1007\/BFb0024472"},{"key":"ref_5","unstructured":"Fagin, B., and OEIS Foundation Inc. (2021, July 28). The On-Line Encyclopedia of Integer Sequences. Squarefree n with Fully Composite Idempotent Factorizations. Available online: http:\/\/oeis.org\/A306508."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","article-title":"Probabalistic Algorithm for Testing Primality","volume":"12","author":"Rabin","year":"1980","journal-title":"J. Number Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/07468342.2020.1724495","article-title":"Idempotent Factorizations in the Classroom","volume":"51","author":"Fagin","year":"2020","journal-title":"Coll. Math. J."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/8\/305\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:36:47Z","timestamp":1760164607000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/8\/305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,29]]},"references-count":7,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["info12080305"],"URL":"https:\/\/doi.org\/10.3390\/info12080305","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2021,7,29]]}}}