Previous work established the set of square-free integers with at least one factorization for which and produce 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 . 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.
Un travail antérieur décrit l’ensemble des entiers sans facteur carré admettant au moins une factorisation pour laquelle et produisent des clés RSA valides, qu’ils soient premiers ou non. Ces entiers sont exactement ceux jouissant de la propriété que , où est la fonction de Carmichael. Nous appelons ces entiers idempotents, parce que pour tout entier positif . 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.
Revised:
Published online:
Barry S. Fagin 1
@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 mathématiques de Besançon. Algèbre et thé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 mathématiques de Besançon. Algèbre et thé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 mathématiques de Besançon. Algèbre et théorie des nombres (2024), pp. 7-21. doi : 10.5802/pmb.53. https://pmb.centre-mersenne.org/articles/10.5802/pmb.53/
[1] 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] Composite Numbers That Give Valid RSA Key Pairs For Any Coprime p, Information, Volume 9 (2018) no. 9, 216 | DOI
[3] Idempotent Factorizations of Square-Free Integers, Information, Volume 10 (2019) no. 7, 232 | DOI
[4] 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] Search Heuristics and Constructive Algorithms for Maximally Idempotent Integers, Information, Volume 12 (2021) no. 8, 305 | DOI
[6] Smallest number for the th square-free number that forms a pure idempotent product, 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A325945)
[7] Squarefree with fully composite idempotent factorizations, 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A306508)
[8] Strong impostors , 2018 (The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A318555)
[9] On Using Primes for Public Key Encryption Systems, Appl. Math. Lett., Volume 1 (1988) no. 3, pp. 225-227 | DOI | MR | Zbl
[10] Two Notes on Notation, Am. Math. Mon., Volume 99 (1992) no. 5, pp. 403-422 | DOI | MR | Zbl
[11] 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] The Carmichael Numbers up to , 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] A Method for Obtaining Digital Signatures and Public-Key Cryptosystem, Commun. ACM, Volume 21 (1978) no. 2, pp. 120-126 | DOI | MR | Zbl
Cited by Sources: