Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers
Previous work established the set of square-free integers <i>n</i> with at least one factorization <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo>&l...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-07-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/12/8/305 |
| _version_ | 1797523516824748032 |
|---|---|
| author | Barry Fagin |
| author_facet | Barry Fagin |
| author_sort | Barry Fagin |
| collection | DOAJ |
| description | Previous work established the set of square-free integers <i>n</i> with at least one factorization <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover></mrow></semantics></math></inline-formula> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover></semantics></math></inline-formula> are valid RSA keys, whether they are prime or composite. These integers are exactly those with the property <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow><mo>∣</mo><mrow><mo>(</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>λ</mi></semantics></math></inline-formula> is the Carmichael totient function. We refer to these integers as <i>idempotent</i>, because <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>∀</mo><mi>a</mi><mo>∈</mo><msub><mi>Z</mi><mi>n</mi></msub><mo>,</mo><msup><mi>a</mi><mrow><mi>k</mi><mrow><mo>(</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mo>+</mo><mn>1</mn></mrow></msup><munder><mo>≡</mo><mi>n</mi></munder><mi>a</mi></mrow></semantics></math></inline-formula> for any positive integer <i>k</i>. 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 <i>maximally idempotent</i> 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. |
| first_indexed | 2024-03-10T08:44:06Z |
| format | Article |
| id | doaj.art-9fbbb87b59d4478a8e8665e15cef3902 |
| institution | Directory Open Access Journal |
| issn | 2078-2489 |
| language | English |
| last_indexed | 2024-03-10T08:44:06Z |
| publishDate | 2021-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj.art-9fbbb87b59d4478a8e8665e15cef39022023-11-22T08:05:51ZengMDPI AGInformation2078-24892021-07-0112830510.3390/info12080305Search Heuristics and Constructive Algorithms for Maximally Idempotent IntegersBarry Fagin0Department of Computer Science, US Air Force Academy, El Paso County, CO 80840, USAPrevious work established the set of square-free integers <i>n</i> with at least one factorization <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>=</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover></mrow></semantics></math></inline-formula> for which <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover></semantics></math></inline-formula> are valid RSA keys, whether they are prime or composite. These integers are exactly those with the property <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>λ</mi><mrow><mo>(</mo><mi>n</mi><mo>)</mo></mrow><mo>∣</mo><mrow><mo>(</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>λ</mi></semantics></math></inline-formula> is the Carmichael totient function. We refer to these integers as <i>idempotent</i>, because <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>∀</mo><mi>a</mi><mo>∈</mo><msub><mi>Z</mi><mi>n</mi></msub><mo>,</mo><msup><mi>a</mi><mrow><mi>k</mi><mrow><mo>(</mo><mover accent="true"><mi>p</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mover accent="true"><mi>q</mi><mo stretchy="false">¯</mo></mover><mo>−</mo><mn>1</mn><mo>)</mo></mrow><mo>+</mo><mn>1</mn></mrow></msup><munder><mo>≡</mo><mi>n</mi></munder><mi>a</mi></mrow></semantics></math></inline-formula> for any positive integer <i>k</i>. 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 <i>maximally idempotent</i> 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.https://www.mdpi.com/2078-2489/12/8/305carmichael totient functionnumber theoryRSAcomputational number theoryfactorizations |
| spellingShingle | Barry Fagin Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers Information carmichael totient function number theory RSA computational number theory factorizations |
| title | Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers |
| title_full | Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers |
| title_fullStr | Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers |
| title_full_unstemmed | Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers |
| title_short | Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers |
| title_sort | search heuristics and constructive algorithms for maximally idempotent integers |
| topic | carmichael totient function number theory RSA computational number theory factorizations |
| url | https://www.mdpi.com/2078-2489/12/8/305 |
| work_keys_str_mv | AT barryfagin searchheuristicsandconstructivealgorithmsformaximallyidempotentintegers |