Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers
Open Access
- 29 July 2021
- journal article
- research article
- Published by MDPI AG in Information
- Vol. 12 (8), 305
- https://doi.org/10.3390/info12080305
Abstract
Previous work established the set of square-free integers n with at least one factorization for which and are valid RSA keys, whether they are prime or composite. These integers are exactly those with the property , where is the Carmichael totient function. We refer to these integers as idempotent, because 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.
Keywords
This publication has 5 references indexed in Scilit:
- Idempotent Factorizations in the Cryptography ClassroomThe College Mathematics Journal, 2020
- Idempotent Factorizations of Square-Free IntegersInformation, 2019
- On using primes for public key encryption systemsApplied Mathematics Letters, 1988
- Probabilistic algorithm for testing primalityJournal of Number Theory, 1980
- A method for obtaining digital signatures and public-key cryptosystemsCommunications of the ACM, 1978