Minimal idempotency, partial idempotency, search heuristics and constructive algorithms for idempotent integers

Barry S. Fagin

doi:10.5802/pmb.53

Barry S. Fagin ¹

¹ Dept of Computer Science, 2354 Fairchild Drive, US Air Force Academy, Colorado Springs CO 80840

Publications mathématiques de Besançon. Algèbre et théorie des nombres (2024), pp. 7-21.

Résumé
Abstract

Un travail antérieur décrit l’ensemble des entiers $n$ sans facteur carré admettant au moins une factorisation $n = \bar{p} \bar{q}$ pour laquelle $\bar{p}$ et $\bar{q}$ produisent des clés RSA valides, qu’ils soient premiers ou non. Ces entiers sont exactement ceux jouissant de la propriété que $λ (n = \bar{p} \bar{q}) ∣ (\bar{p} - 1) (\bar{q} - 1)$ , où $λ$ est la fonction de Carmichael. Nous appelons ces entiers idempotents, parce que $\forall a \in Z_{n}, a^{k (\bar{p} - 1) (\bar{q} - 1) + 1} \equiv_{n} a$ pour tout entier positif $k$ . Cet ensemble inclut les nombres semi-premiers et les nombres de Carmichael, mais n’est pas seulement composé de ceux-ci. Les nombres de cette dernière catégorie n’ont pas encore été analysés dans la littérature.

Dans cet article nous discutons la structure des entiers idempotents et présentons des heuristiques pour aider à les trouver. Nous introduisons les notions de partiellement idempotent et d’idempotence minimale, en donnons des définitions appropriées et présentons des résultats préliminaires.

Previous work established the set of square-free integers $n$ with at least one factorization $n = \bar{p} \bar{q}$ for which $\bar{p}$ and $\bar{q}$ produce valid RSA keys, whether they are prime or composite. These integers are exactly those with the property $λ (n = \bar{p} \bar{q}) ∣ (\bar{p} - 1) (\bar{q} - 1)$ , where $λ$ is the Carmichael totient function. We refer to these integers as idempotent, because $\forall a \in Z_{n}, a^{k (\bar{p} - 1) (\bar{q} - 1) + 1} \equiv_{n} a$ for any positive integer $k$ . This set includes the semiprimes and the Carmichael numbers, but is not limited to them. Numbers in this last category have not been previously analyzed in the literature.

We discuss the structure of idempotent integers here, and present heuristics to assist in finding them. We introduce the notions of partial idempotency and minimal idempotency, give appropriate definitions for them, and present preliminary results.

Reçu le : 2021-11-28
Révisé le : 2022-04-19
Publié le : 2024-04-22

DOI : 10.5802/pmb.53

Affiliations des auteurs :

Barry S. Fagin ¹

¹ Dept of Computer Science, 2354 Fairchild Drive, US Air Force Academy, Colorado Springs CO 80840

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{PMB_2024____7_0,
     author = {Barry S. Fagin},
     title = {Minimal idempotency, partial idempotency, search heuristics and constructive algorithms for idempotent integers},
     journal = {Publications math\'ematiques de Besan\c{c}on. Alg\`ebre et th\'eorie des nombres},
     pages = {7--21},
     publisher = {Presses universitaires de Franche-Comt\'e},
     year = {2024},
     doi = {10.5802/pmb.53},
     language = {en},
     url = {https://pmb.centre-mersenne.org/articles/10.5802/pmb.53/}
}

TY  - JOUR
AU  - Barry S. Fagin
TI  - Minimal idempotency, partial idempotency, search heuristics and constructive algorithms for idempotent integers
JO  - Publications mathématiques de Besançon. Algèbre et théorie des nombres
PY  - 2024
SP  - 7
EP  - 21
PB  - Presses universitaires de Franche-Comté
UR  - https://pmb.centre-mersenne.org/articles/10.5802/pmb.53/
DO  - 10.5802/pmb.53
LA  - en
ID  - PMB_2024____7_0
ER  -

%0 Journal Article
%A Barry S. Fagin
%T Minimal idempotency, partial idempotency, search heuristics and constructive algorithms for idempotent integers
%J Publications mathématiques de Besançon. Algèbre et théorie des nombres
%D 2024
%P 7-21
%I Presses universitaires de Franche-Comté
%U https://pmb.centre-mersenne.org/articles/10.5802/pmb.53/
%R 10.5802/pmb.53
%G en
%F PMB_2024____7_0

Barry S. Fagin. Minimal idempotency, partial idempotency, search heuristics and constructive algorithms for idempotent integers. Publications mathématiques de Besançon. Algèbre et théorie des nombres (2024), pp. 7-21. doi : 10.5802/pmb.53. https://pmb.centre-mersenne.org/articles/10.5802/pmb.53/

Bibliographie
Cité par

[1] Paul Erdős; Florian Luca; Carl Pomerance On the Proportion of Numbers Coprime to a Given Integer, Anatomy of integers (CRM Proceedings & Lecture Notes), Volume 46, American Mathematical Society, 2008, pp. 47-64 | DOI | MR | Zbl

[2] Barry Fagin Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p, Information, Volume 9 (2018) no. 9, 216 | DOI

[3] Barry Fagin Idempotent Factorizations of Square-Free Integers, Information, Volume 10 (2019) no. 7, 232 | DOI

[4] Barry Fagin Idempotent Integers: The complete class of numbers that work correctly in RSA, Géométrie algébrique, Théorie des nombres et Applications 2021, 2021, pp. 16-20

[5] Barry Fagin Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers, Information, Volume 12 (2021) no. 8, 305 | DOI

[6] Barry Fagin; OEIS Foundation Smallest number for the $n$ th square-free number that forms a pure idempotent product, 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A325945)

[7] Barry Fagin; OEIS Foundation Squarefree $n$ with fully composite idempotent factorizations, 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A306508)

[8] Barry Fagin; OEIS Foundation Strong impostors $\neq 0 (mod 4)$ , 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A318555)

[9] E. Dennis Huthnance; Joe Warndof On Using Primes for Public Key Encryption Systems, Appl. Math. Lett., Volume 1 (1988) no. 3, pp. 225-227 | DOI | MR | Zbl

[10] Donald E. Knuth Two Notes on Notation, Am. Math. Mon., Volume 99 (1992) no. 5, pp. 403-422 | DOI | MR | Zbl

[11] Richard Pinch On Using Carmichael Numbers for Public Key Encryption Systems, Cryptography and coding. 6th IMA international conference (Cirencester, 1997) (Lecture Notes in Computer Science), Volume 1355, Springer, 1997, pp. 265-269 | Zbl

[12] Richard Pinch The Carmichael Numbers up to $10^{21}$ , Proceedings of the Conference on Algorithmic Number Theory 2007 (TUCS General Publication), Turku Centre for Computer Science, 2007, pp. 129-131 (http://www.s369624816.websitehome.co.uk/rgep/cartable.html)

[13] R. Rivest; A. Shamir; L. Adleman A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, Commun. ACM, Volume 21 (1978) no. 2, pp. 120-126 | DOI | MR | Zbl

Cité par Sources :

Publications Mathématiques de Besançon

Algèbre et Théorie des Nombres