On the Number of Regular Integers Modulo $n$ and Its Significance for Cryptography
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918165199454208 |
|---|---|
| author | Dohmen, Klaus Lange-Geisler, Mandy |
| author_facet | Dohmen, Klaus Lange-Geisler, Mandy |
| contents | We present four combinatorial proofs of Morgado's formula for the number $\varrho(n)$ of non-congruent regular integers modulo $n$, corresponding to sequence A055653 in the On-Line Encyclopedia of Integer Sequences (OEIS), where an integer $m$ is said to be regular modulo $n$ if the congruence $m^2 x \equiv m \pmod{n}$ has a solution $x\in\mathbb{Z}$. To illustrate the significance of the sequence and Morgado's formula, we relate them to a recent multi prime, multi-power generalization of the RSA cryptosystem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_02471 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Number of Regular Integers Modulo $n$ and Its Significance for Cryptography Dohmen, Klaus Lange-Geisler, Mandy Combinatorics Group Theory Number Theory (Primary) 11B83 (Secondary) 05A15, 11A25, 11T71 We present four combinatorial proofs of Morgado's formula for the number $\varrho(n)$ of non-congruent regular integers modulo $n$, corresponding to sequence A055653 in the On-Line Encyclopedia of Integer Sequences (OEIS), where an integer $m$ is said to be regular modulo $n$ if the congruence $m^2 x \equiv m \pmod{n}$ has a solution $x\in\mathbb{Z}$. To illustrate the significance of the sequence and Morgado's formula, we relate them to a recent multi prime, multi-power generalization of the RSA cryptosystem. |
| title | On the Number of Regular Integers Modulo $n$ and Its Significance for Cryptography |
| topic | Combinatorics Group Theory Number Theory (Primary) 11B83 (Secondary) 05A15, 11A25, 11T71 |
| url | https://arxiv.org/abs/2304.02471 |